一个图共有 $2N$ 个顶点。在前 $N$ 个顶点之间没有边，在第 $N+1$ 个到第 $2N$ 个顶点之间也没有边。也就是说，给定的图是一个二分图。

给定一个正整数序列 $a_1, a_2, \dots, a_N$。对于满足 $1 \le i, j \le N$ 的任意对 $(i, j)$，顶点 $i$ 和 $N + j$ 相连的充要条件是 $j \le a_i$。

共给出 $Q$ 次询问。每次询问由两个整数 $v$ 和 $x$ 表示，表示 $a_v$ 的值将修改为 $a_v + x$。保证 $x = 1$ 或 $x = -1$。对于每次询问，你必须计算给定图中长度为 4 的环的数量。由于数量可能很大，请输出其对 $998\,244\,353$ 取模后的余数。如果组成两个环的边集不同，则认为这两个环是不同的。

输入格式

第一行包含两个正整数 $N$ 和 $Q$，用空格隔开。

第二行包含共 $N$ 个整数 $a_1, a_2, \dots, a_N$，用空格隔开。

接下来的 $Q$ 行，每行包含两个用空格隔开的整数 $v$ 和 $x$。第 $i$ 行的输入表示 $a_v$ 将修改为 $a_v + x$。

输出格式

在每次询问执行后，在新的一行输出长度为 4 的环的数量对 $998\,244\,353$ 取模后的余数。

数据范围

• $2 \le N \le 5 \cdot 10^5$，$1 \le Q \le 5 \cdot 10^5$
• 对于每次询问，$1 \le v \le N$ 且 $x \in \{-1, 1\}$。
• 在每次询问后，保证对于所有 $1 \le i \le N$，均有 $0 \le a_i \le N$。

样例

样例输入 1

10 10
8 6 1 3 0 0 6 9 6 1
6 1
10 -1
5 1
7 -1
7 -1
9 -1
8 -1
7 -1
7 -1
5 -1

样例输出 1

178
178
178
158
142
127
127
115
105
105

说明

图中的四个边组成的集合 $\{xy, yz, zw, wx\}$ 被认为是一个长度为 4 的环。