Shortest Sub-Array

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

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