Shortest Sub-Array

Peregrine_Falcon Criterion 2021 Round 9
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

Submit

Login to submit.

Statistics

75% Solution Ratio
mh755628Earliest, Feb '21
Ahasan_1999Fastest, 0.2s
moursalinmeLightest, 9.4 MB
MursaleenShortest, 921B
Toph uses cookies. By continuing you agree to our Cookie Policy.