#P18191. Two Box

Two Box

Two Box

给定长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N),以及 QQ 次修改。第 ii 次修改将 AxiA_{x_i} 改为 yiy_i,然后对修改后的序列回答下面的计数问题。各次对序列的修改会保留。

有一个白盒、一个黑盒,以及编号为 1,2,…,M1,2,\ldots,M 的 MM 个球。开始时所有球都在白盒中。

需要恰好执行 NN 次操作。每次选择一个编号 xx,1≤x≤M1\le x\le M,把球 xx 从当前的盒子移到另一个盒子。

要求:在第 ii 次操作完成后,黑盒中所有球的编号都不超过 AiA_i。黑盒为空时自然满足这一条件。

求满足全部条件的操作序列数量,对 998244353998244353 取模。操作序列由每次选择的球编号确定。

请依次回答每次修改后的结果。每次计数都假设从“所有球都在白盒”重新开始;这里只对 AA 累积修改,不在询问之间保留某次操作实验的球状态。最后一次操作结束时不要求黑盒为空。

输入格式

第一行三个整数 N,M,QN,M,Q。

第二行 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

接下来 QQ 行,第 ii 行两个整数 xi,yix_i,y_i,表示将 AxiA_{x_i} 修改为 yiy_i。

输出格式

输出 QQ 行,第 ii 行一个整数,表示第 ii 次修改后满足条件的操作序列数量对 998244353998244353 取模的结果。不输出修改前的答案。

数据范围

  • 1≤N,Q≤3×1041\le N,Q\le3\times10^4;
  • 1≤M≤151\le M\le15;
  • 1≤Ai,yi≤M1\le A_i,y_i\le M;
  • 1≤xi≤N1\le x_i\le N。

样例 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

样例说明

样例 1 第一次修改后 A=(1,3,2)A=(1,3,2),合法的选球序列恰好是

$$(1,1,1),\quad(1,1,2),\quad(1,2,1),\quad(1,2,2),\quad(1,3,3).$$

例如 (1,3,3)(1,3,3):先把球 11 移入黑盒,再把球 33 移入黑盒,最后把球 33 移回白盒,黑盒中只剩球 11,分别满足三个时刻的限制。

第二次修改是在第一次修改后的序列上进行,得到 A=(3,3,2)A=(3,3,2),答案为 1414。