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

    Discussion

    Statistics


    73% Solution Ratio

    mh755628Earliest, 4w ago

    Ahasan_1999Fastest, 0.2s

    fsshakkhorLightest, 9.6 MB

    ruhanhabib39Shortest, 999B

    Submit

    Login to submit

    Editorial

    If you know Square Root Decomposition algorithm, then this problem will be a piece of cake for you....

    Related Contests