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.