问题陈述

给定一个正整数序列 $A = (A_1, A_2, \ldots, A_N)$ 和 $Q$ 个查询。第 $i$ 个查询如下所示：

• 给定整数 $x_i$ 和 $y_i$（其中 $1\leq x_i\leq N$），将 $A_{x_i}$ 改为 $y_i$。

每次查询改变序列时，找到对应问题的答案并对 $998244353$ 取模（参见注释）。

令 $f(n)$ 表示在 $A$ 上进行下列操作 $n$ 次时可以获得的最大总点数。

• 选择 $i, j$，使得 $A_i\leq A_j$，并选择 非负实数 $x$，满足 $A_i + 2x \leq A_j$。
• 将 $x$ 添加到 $A_i$ 中，并从 $A_j$ 中减去 $x$。
• 获得 $x$ 个点。

可以证明极限 $\\displaystyle \\lim_{n\\to\\infty} f(n)$ 存在。找到这个极限值。

注释

我们可以证明所讨论的极限始终是一个有理数。此外，在问题的约束条件下，当将该数表示为 $\\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数时，我们可以证明存在唯一的整数 $R$，满足 $R\\times Q\\equiv P\\pmod{998244353}$ 且 $0\\leq R < 998244353$。找到这个 $R$。

约束条件

• $2\leq N\leq 3\times 10^5$
• $1\leq Q\leq 3\times 10^5$
• $1\leq A_i \leq 10^9$
• $1\leq x_i\leq N$
• $1\leq y_i\leq 10^9$

输入

输入以以下格式从标准输入给出：

$N$ $Q$ $A_1$ $A_2$ $\ldots$ $A_N$ $x_1$ $y_1$ $\vdots$ $x_Q$ $y_Q$

输出

输出 $Q$ 行；第 $i$ 行应包含第 $i$ 次查询之后的问题的答案。

示例输入 1

3 4
7 5 5
1 5
2 6
1 7
3 5

示例输出 1

0
1
2
2

第一个查询将序列更改为 $(5, 5, 5)$。在这里，对于任何 $n$，我们都有 $f(n) = 0$，所以答案是 $0$。

第二个查询将序列更改为 $(5, 6, 5)$。下面是一种可能的操作方法：

• 选择 $(i,j,x) = (3,2,0.4)$，将序列更改为 $(5, 5.6, 5.4)$ 并获得 $0.4$ 个点。
• 选择 $(i,j,x) = (1,2,0.3)$，将序列更改为 $(5.3, 5.3, 5.4)$ 并获得 $0.3$ 个点。

以上两个操作共获得 $0.7$ 个点，从中我们可以看出 $f(2) \geq 0.7$。

我们可以证明总共不能获得超过 $1$ 个点，且通过最优的操作方法获得的点数在操作次数增加时趋于 $1$。因此，我们有 $\\displaystyle \\lim_{n\\to\\infty} f(n) = 1$。

示例输入 2

2 4
1 2
2 5
1 3
1 2
2 3

示例输出 2

2
1
499122178
499122177