Farmer John 有一个长度为 $$$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$$$。
示例
输入 #1
5 6 0 14 0 7 6 1 4 1 3 2 15 4 1 5 2 5 8
输出 #1
3 2 3 2 1 3
输入 #2
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
输出 #2
16 17 16 17 16 17 16 17 16 17
输入 #3
2 2 386056082462833225 923951085408043421 1 386056082462833225 1 386056082462833224
输出 #3
961223744 961223743
输入#4
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
输出#4
370643829 370643830 370643829 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
注意
在第一个测试用例中,第一次更新后的数组是$$$[4, 14, 0, 7, 6]$$$。 $$$f$$$ 的值为:
- $$$f(1)=2$$$;
- $$$f(2)=4$$$;
- $$$f(3)=2$$$;
- $$$f(4)=3$$$;
- $$$f(5)=3$$$。
由于 $$$\lfloor f(5) \rfloor = 3$$$,我们输出 $$$3$$$。
第二次更新后的数组为$$$[3, 14, 0, 7, 6]$$$。 $$$f$$$ 的值四舍五入到 $$$6$$$ 小数位,如下:
- $$$f(1)\约 1.732051$$$;
- $$$f(2)\约 3.966365$$$;
- $$$f(3)\约 1.991573$$$;
- $$$f(4)\约 2.998595$$$;
- $$$f(5)\约 2.999766$$$。
由于 $$$\lfloor f(5) \rfloor = 2$$$,我们输出 $$$2$$$。