Fenwick Tree Binary Search

Problem Description

You are given $n$ numbers $a_1, a_2, a_3, \dots, a_n$.

You must support $q$ operations:

1. 1 x d: set $a_x = d$.
2. 2 s: find the largest $T$ ($0 \le T \le n$) such that $\sum_{i=1}^{T} a_i \le s$.

Input Format

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The following $q$ lines each describe an operation of the form 1 x d or 2 s, with $1 \le x \le n$, $1 \le d \le 10^9$, and $1 \le s \le 10^{14}$.

Output Format

For each query, output one line containing the answer.

Sample Input

5 5
1 2 3 4 5
2 6
2 5
1 1 100
2 10
2 1000

Sample Output

3
2
0
5

Constraints

$1 \le n, q \le 2 \times 10^5$, $1 \le a_i, d \le 10^9$, $1 \le s \le 10^{14}$, $1 \le x \le n$.