311158: CF1942F. Farmer John's Favorite Function

F. Farmer John's Favorite Functiontime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputΩΩ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 > 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.

ExamplesInput

5 6
0 14 0 7 6
1 4
1 3
2 15
4 1
5 2
5 8

Output

3
2
3
2
1
3

Input

15 10
3364 1623 5435 7 6232 245 7903 3880 9738 577 4598 1868 1112 8066 199
14 4284
14 8066
6 92
6 245
2 925
2 1623
5 176
5 6232
3 1157
3 5435

Output

16
17
16
17
16
17
16
17
16
17

Input

2 2
386056082462833225 923951085408043421
1 386056082462833225
1 386056082462833224

Output

961223744
961223743

Input

13 10
31487697732100 446330174221392699 283918145228010533 619870471872432389 11918456891794188 247842810542459080 140542974216802552 698742782599365547 533363381213535498 92488084424940128 401887157851719898 128798321287952855 137376848358184069
3 283918145228010532
3 283918145228010533
1 2183728930312
13 1000000000000000000
10 1000000000000000000
9 1000000000000000000
8 1000000000000000000
7 1000000000000000000
6 1000000000000000000
5 1000000000000000000

Output

370643829
370643830
370643829
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

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$.

**题目大意：**

农民约翰有一个长度为 $ n $ 的数组 $ a $。他还有一个函数 $ f $，其递归定义为：

- $ f(1) = \sqrt{a_1} $
- 对于所有 $ i > 1 $，$ f(i) = \sqrt{f(i-1) + a_i} $

注意 $ f(i) $ 不一定是整数。

他计划对数组进行 $ q $ 次更新。每次更新时，他会给你两个整数 $ k $ 和 $ x $，并希望您将 $ a_k $ 设置为 $ x $。在每次更新后，他想知道 $ \lfloor f(n) \rfloor $，其中 $ \lfloor t \rfloor $ 表示 $ t $ 向下取整到最近的整数。

**输入数据格式：**

第一行包含两个整数 $ n $ 和 $ q $ ($ 1 \leq n, q \leq 2 \cdot 10^5 $)，分别是数组 $ a $ 的长度和他将执行的更新次数。

第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ($ 0 \leq a_i \leq 10^{18} $)。

接下来的 $ q $ 行，每行包含两个整数 $ k $ 和 $ x $ ($ 1 \leq k \leq n $, $ 0 \leq x \leq 10^{18} $)，分别是更新的索引和他将替换 $ a_k $ 的元素。

**输出数据格式：**

对于每次更新，输出一个整数 $ \lfloor f(n) \rfloor $，每个答案占一行。**题目大意：** 农民约翰有一个长度为 $ n $ 的数组 $ a $。他还有一个函数 $ f $，其递归定义为： - $ f(1) = \sqrt{a_1} $ - 对于所有 $ i > 1 $，$ f(i) = \sqrt{f(i-1) + a_i} $ 注意 $ f(i) $ 不一定是整数。 他计划对数组进行 $ q $ 次更新。每次更新时，他会给你两个整数 $ k $ 和 $ x $，并希望您将 $ a_k $ 设置为 $ x $。在每次更新后，他想知道 $ \lfloor f(n) \rfloor $，其中 $ \lfloor t \rfloor $ 表示 $ t $ 向下取整到最近的整数。 **输入数据格式：** 第一行包含两个整数 $ n $ 和 $ q $ ($ 1 \leq n, q \leq 2 \cdot 10^5 $)，分别是数组 $ a $ 的长度和他将执行的更新次数。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ($ 0 \leq a_i \leq 10^{18} $)。 接下来的 $ q $ 行，每行包含两个整数 $ k $ 和 $ x $ ($ 1 \leq k \leq n $, $ 0 \leq x \leq 10^{18} $)，分别是更新的索引和他将替换 $ a_k $ 的元素。 **输出数据格式：** 对于每次更新，输出一个整数 $ \lfloor f(n) \rfloor $，每个答案占一行。