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$
.
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}$
.For the second type of query print the minimum $R$
or $-1$
if it is impossible to find such $R$
in separate lines.
Input | Output |
---|---|
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 |