给定一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \dots, A_N)$ 和 $Q$ 次查询。第 $i$ 次查询描述如下：

• 将 $A_{x_i}$ 修改为 $y_i$，然后根据更新后的序列 $A$ 计算以下问题的答案。

有两个盒子，一个白色，一个黑色，以及 $M$ 个编号从 $1$ 到 $M$ 的球。初始时，所有球都在白色盒子中。 你执行 $N$ 次以下操作： * 选择一个满足 $1 \le x \le M$ 的整数 $x$。将球 $x$ 从其当前所在的盒子移动到另一个盒子中。

在第 $i$ 次操作后，黑色盒子中所有球的编号必须小于或等于 $A_i$。计算满足此条件的可能操作序列的数量，结果对 $998244353$ 取模。

按顺序处理查询。

数据范围

• $1 \le N, Q \le 3 \times 10^4$
• $1 \le M \le 15$
• $1 \le x_i \le N$
• $1 \le A_i, y_i \le M$

输入格式

输入通过标准输入按以下格式给出：

$N \ M \ Q$ $A_1 \ A_2 \dots A_N$ $x_1 \ y_1$ $x_2 \ y_2$ $\vdots$ $x_Q \ y_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 次查询的答案。

样例

样例输入 1

3 3 2
1 3 1
3 2
1 3

样例输出 1

5
14

样例输入 2

6 8 1
3 8 7 7 1 6
1 4

样例输出 2

2100

样例输入 3

12 10 8
1 3 2 6 3 6 7 7 5 5 4 7
12 4
7 10
4 2
9 8
9 9
8 3
4 9
10 2

样例输出 3

2741280
3007680
1503840
1916160
1972800
728640
1821600
621440

说明

对于第一个样例： 对于第一次查询，$A = (1, 3, 2)$。在这种情况下，可能的操作序列包括，例如：

• 选择 $x = 1$。将球 $1$ 从白色盒子移动到黑色盒子。此时黑色盒子包含球 $1$。
• 选择 $x = 3$。将球 $3$ 从白色盒子移动到黑色盒子。此时黑色盒子包含球 $1$ 和 $3$。
• 选择 $x = 3$。将球 $1$ 从黑色盒子移回白色盒子。此时黑色盒子包含球 $1$。

其他可能的 $x$ 序列为 $(1, 1, 1), (1, 1, 2), (1, 2, 1)$ 和 $(1, 2, 2)$，总共还有 $4$ 种可能性。 因此，共有 $5$ 种可能的操作序列。