# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Shortest Sub-Array

By Peregrine_Falcon · Limits 1s, 256 MB

You are given an array $A$ consists of $N$ elements.
You have to perform $Q$ queries on the array.

• $\texttt{Update P Y}$:
For this type of queries, you have to set $A_P$ = $Y$. Here, $P$ is an index of array $A$.

• $\texttt{Query L X}$:
For this type of queries, you have to find the minimum $R$, so that $\sum_{i = L}^{R}$ $A_i$ $\geq$ $X$ or say is it impossible to find such $R$.

## Input

The first line contains two integers $N$ and $Q$ ($3 \le N, Q \le 5 \times 10^5$) represents the size of array $A$ and number of queries to perform respectively.

The next line contains $N$ space separated integers $A_i$ ($1 \le A_i \le 10^9$).

The next $Q$ lines consists of one of two types of queries.

• $\texttt{Update P Y}$: $1 ≤ P ≤ N, 1 ≤ Y ≤ 10^9$.
• $\texttt{Query L X}$: $1 ≤ L ≤ N, 1 ≤ X ≤ 10^{16}$.

## Output

For the second type of query print the minimum $R$ or $-1$ if it is impossible to find such $R$ in separate lines.

## Sample

InputOutput
5 5
1 5 3 2 4
Query 2 8
Update 3 1
Query 2 8
Query 4 1
Query 4 10

3
4
4
-1


### Statistics

75% Solution Ratio

mh755628Earliest, 8M ago

Ahasan_1999Fastest, 0.2s

moursalinmeLightest, 9.4 MB

MursaleenShortest, 921B