ΩΩPARTS - Camellia⠀

Farmer John has an array $a$ of length $n$. He also has a function $f$ with the following recurrence:

• $f(1) = \sqrt{a_1}$;
• For all $i \gt 1$, $f(i) = \sqrt{f(i-1)+a_i}$.

Note that $f(i)$ is not necessarily an integer.

He plans to do $q$ updates to the array. Each update, he gives you two integers $k$ and $x$ and he wants you to set $a_k = x$. After each update, he wants to know $\lfloor f(n) \rfloor$, where $\lfloor t \rfloor$ denotes the value of $t$ rounded down to the nearest integer.

Input

The first line contains $n$ and $q$ ($1 \leq n, q \leq 2 \cdot 10^5$), the length of $a$ and the number of updates he will perform.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^{18}$).

The next $q$ lines each contain two integers $k$ and $x$ ($1 \leq k \leq n$, $0 \leq x \leq 10^{18}$), the index of the update and the element he will replace $a_k$ with.

Output

For each update, output an integer, $\lfloor f(n) \rfloor$, on a new line.

Note

In the first test case, the array after the first update is $[4, 14, 0, 7, 6]$. The values of $f$ are:

• $f(1)=2$;
• $f(2)=4$;
• $f(3)=2$;
• $f(4)=3$;
• $f(5)=3$.

Since $\lfloor f(5) \rfloor = 3$, we output $3$.

The array after the second update is $[3, 14, 0, 7, 6]$. The values of $f$, rounded to $6$ decimal places, are:

• $f(1)\approx 1.732051$;
• $f(2)\approx 3.966365$;
• $f(3)\approx 1.991573$;
• $f(4)\approx 2.998595$;
• $f(5)\approx 2.999766$.

Since $\lfloor f(5) \rfloor = 2$, we output $2$.