题目描述

你有 $k$ 件不同的家具，需要摆放在 $n$ 个不同的房间中。假设每个房间足够大，并且只考虑每件家具处于哪个房间（而不考虑房间内部如何摆放），那么总共有 $n^k$ 种不同的摆放方式（注意，不是 $k^n$）。

摆放家具也算一门学问了，至少不太好乱摆的吧？对于每种摆放方式，我们可以给这种方式打分。例如，某个方案把餐桌放到了卫生间，或是一个卧室放了两张床而另一个卧室没有床，就会获得比较低的分数。由于这个分数关于每件家具、每个房间不是独立的，我们会输入所有 $n^k$ 种摆放方式的分数。

你现在心血来潮，想换一换房间的布局。给出一种初始时的摆放方式，你会重复 $T$ 次下述操作：每次，你会任选一件家具，然后将这件家具移动到任意一个其他房间中。每一轮有 $k(n-1)$ 种决策（选择家具的方案数乘以选择另一个房间的方案数），所以总共有 $k^T(n-1)^T$ 种决策。你需要计算这每一种决策后的摆放方式的得分之和。

不仅如此，我们会给出 $q$ 次询问，每次输入初始时的摆放方式与 $T$，你需要在线地回答 $k^T(n-1)^T$ 种决策后的得分之和（取模）。详见输入与输出格式。

我们如下定义一种摆放方式的编号：

我们将家具用 0 到 $k-1$ 的不同整数编号，房间用 $0$ 到 $n-1$ 的不同整数编号。设在某种摆放方式下，第 $i$ 号家具被放在了 $p_i$ 号房间中，则定义这种摆放方式的编号为 $\sum_{i=0}^{k-1} p_i n^i$。可以发现，所有的 $n^k$ 种摆放方式的编号恰好是 $0$ 到 $n^k -1$ 的不同整数。

另外，设 $P=998244353$。

输入格式

第一行输入三个正整数 $n, k, q$。

接下来 $n^k$ 行，每行输入一个小于 $P$ 的正整数，依次表示编号为 $0, 1, \dots, n^k - 1$ 的摆放方式的得分。

接下来 $q$ 行，每行输入两个非负整数。设某行的输入为 $a, b$（保证 $0 \leq a < n^k, 0 \leq b < P$），则此次询问的初始摆放方式的编号为 $a$，而 $T=b \cdot r \bmod P$，其中 $r$ 是你上一个输出的数（对于第一次询问为 $1$）。

同一行内输入的相邻两个数之间以一个空格隔开。

保证 $n \geq 2$，$k \geq 1$；$n^k \leq 10^6$；$q \leq 5 \times 10^5$

输出格式

对于每次询问输出一行，包含一个非负整数，表示该询问的得分之和对 $P$ 取模的结果。

2 3 3
1
10
100
1000
998244245
100000
1000000
10000000
0 1
0 1
1 233

2
2202003
444957911

提示

样例解释

第一次询问中，初始摆放方式的编号为 $0$，$T=1$。

初始时，$0$ 号家具放在 $0$ 号房间，$1$ 号家具放在 $0$ 号房间，$2$ 号家具放在 $0$ 号房间。经过 $1$ 次操作后，可能的情况有：

• 将 $0$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $1$，得分为 $10$；
• 将 $1$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $2$，得分为 $100$；
• 将 $2$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $4$，得分为 $998244245$。

所以，所有情况的总得分为 $998244355$，对 $P$ 取模后为 $2$。

第二次询问中，初始摆放方式的编号为 $0$，$T=2$。

初始时，$0$ 号家具放在 $0$ 号房间，$1$ 号家具放在 $0$ 号房间，$2$ 号家具放在 $0$ 号房间。经过 $2$ 次操作后，可能的情况有：

• 将 $0$ 号家具移动到 $1$ 号房间，然后将 $0$ 号家具移动到 $0$ 号房间，此后的摆放方式编号为 $0$，得分为 $1$；
• 将 $0$ 号家具移动到 $1$ 号房间，然后将 $1$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $3$，得分为 $1000$；
• 将 $0$ 号家具移动到 $1$ 号房间，然后将 $2$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $5$，得分为 $100000$；
• 将 $1$ 号家具移动到 $1$ 号房间，然后将 $0$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $3$，得分为 $1000$；
• 将 $1$ 号家具移动到 $1$ 号房间，然后将 $1$ 号家具移动到 $0$ 号房间，此后的摆放方式编号为 $0$，得分为 $1$；
• 将 $1$ 号家具移动到 $1$ 号房间，然后将 $2$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $6$，得分为 $1000000$；
• 将 $2$ 号家具移动到 $1$ 号房间，然后将 $0$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $5$，得分为 $100000$；
• 将 $2$ 号家具移动到 $1$ 号房间，然后将 $1$ 号家具移动到 $1$ 号房间，此后的摆放方式编号为 $6$，得分为 $1000000$；
• 将 $2$ 号家具移动到 $1$ 号房间，然后将 $2$ 号家具移动到 $0$ 号房间，此后的摆放方式编号为 $0$，得分为 $1$。

所以，所有情况的总得分为 $2202003$，对 $P$ 取模后为 $2202003$。

第三次询问中，初始摆放方式的编号为 $1$，$T=513066699$。初始时，$0$ 号家具放在 $1$ 号房间，$1$ 号家具放在 $0$ 号房间，$2$ 号家具放在 $0$ 号房间。

……（省略至少 $3^{513066699}$ 行）

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。