有 $m$ 个球，编号为 $1\sim m$，每个球为黑色或白色。一开始，所有的球为白色。
接下来，你要做 $n$ 次操作，每次操作形如：将一个球的颜色翻转（从黑染白，或从白染黑）。
你还需要保证，在第 $i$ 次操作结束后，只有编号 $\le a_i$ 的球可能为黑色，编号 $> a_i$ 的球必须为白色。
你要求出有多少种不同的合法操作的方案，对 $998244353$ 取模。两种操作方案不同当且仅当在某次操作中，选中球的编号不同。
但是这还不够，你要处理 $q$ 次修改，每次修改形如：将 $a_{x_i}$ 改为 $y_i$，然后求出当前 $a$ 对应的答案。
输入格式
第一行输入 $n,m,q$。
第二行 $n$ 个整数，表示 $a_i$。
接下来 $q$ 行，每行两个数 $x_i,y_i$。
输出格式
输出 $q$ 行，每行一个答案。
样例输入 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
样例输入/输出 4~6
见下发文件。
数据范围
对于所有数据，$n,q\le 3\times 10^4,m\le 15,1\le a_i,y_i\le m,1\le x_i\le n$。
各子任务的附加限制如下表所示：
| 子任务编号 | $n\le$ | $m\le$ | $q\le$ | 得分 |
|---|---|---|---|---|
| $1$ | $5$ | $5$ | $10$ | $4$ |
| $2$ | $2000$ | $10$ | $1$ | $6$ |
| $3$ | $30000$ | $10$ | $1$ | $8$ |
| $4$ | $30000$ | $15$ | $1$ | $24$ |
| $5$ | $30000$ | $15$ | $10$ | $12$ |
| $6$ | $30000$ | $7$ | $30000$ | $14$ |
| $7$ | $30000$ | $10$ | $30000$ | $16$ |
| $8$ | $30000$ | $15$ | $30000$ | $16$ |