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 AA consists of NN elements.
You have to perform QQ queries on the array.

  • Update P Y\texttt{Update P Y}:
    For this type of queries, you have to set APA_P = YY. Here, PP is an index of array AA.

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

Input

The first line contains two integers NN and QQ (3N,Q5×1053 \le N, Q \le 5 \times 10^5) represents the size of array AA and number of queries to perform respectively.

The next line contains NN space separated integers AiA_i (1Ai1091 \le A_i \le 10^9).

The next QQ lines consists of one of two types of queries.

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

Output

For the second type of query print the minimum RR or 1-1 if it is impossible to find such RR 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


    75% Solution Ratio

    mh755628Earliest, 8M ago

    Ahasan_1999Fastest, 0.2s

    moursalinmeLightest, 9.4 MB

    MursaleenShortest, 921B

    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

    Toph uses cookies. By continuing you agree to our Cookie Policy.