有 $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$。

各子任务的附加限制如下表所示：