Description

You have $k$ different pieces of furniture that need to be placed into $n$ different rooms. Assume each room is large enough, and we only care about which room each piece of furniture is in (not the exact position inside the room). Then there are $n^k$ different arrangements in total (note that it is not $k^n$).

Arranging furniture is also a kind of knowledge, and you cannot just place them randomly. For each arrangement, we can give it a score. For example, an arrangement that puts the dining table in the bathroom, or one bedroom has two beds while another bedroom has no bed, would get a relatively low score. Since the score is not independent across each piece of furniture and each room, we will input the scores for all $n^k$ arrangements.

Now you suddenly want to change the layout. Given an initial arrangement, you will repeat the following operation $T$ times: each time, you may choose any one piece of furniture and move it to any other room. In each round there are $k(n-1)$ choices (number of ways to choose the furniture times number of ways to choose another room), so in total there are $k^T(n-1)^T$ decision sequences. You need to compute the sum of the scores of the resulting arrangements after each decision sequence.

Moreover, we will give $q$ queries. In each query, you are given the initial arrangement and $T$, and you need to answer online the sum of scores after the $k^T(n-1)^T$ decision sequences (modulo). See the input and output formats for details.

We define the ID of an arrangement as follows:

We label the furniture with distinct integers from $0$ to $k-1$, and the rooms with distinct integers from $0$ to $n-1$. Suppose in an arrangement, the furniture $i$ is placed in room $p_i$. Then we define the ID of this arrangement as $\sum_{i=0}^{k-1} p_i n^i$. It can be seen that the IDs of all $n^k$ arrangements are exactly the distinct integers from $0$ to $n^k - 1$.

Also, let $P=998244353$.

Input Format

The first line contains three positive integers $n, k, q$.

In the next $n^k$ lines, each line contains a positive integer less than $P$, giving the scores of arrangements with IDs $0, 1, \dots, n^k - 1$ in order.

In the next $q$ lines, each line contains two non-negative integers. Suppose a line contains $a, b$ (guaranteed $0 \leq a < n^k, 0 \leq b < P$). Then in this query, the ID of the initial arrangement is $a$, and $T=b \cdot r \bmod P$, where $r$ is your previous output (for the first query, $r=1$).

Adjacent numbers on the same line are separated by one space.

Constraints: $n \geq 2$, $k \geq 1$; $n^k \leq 10^6$; $q \leq 5 \times 10^5$.

Output Format

For each query, output one line containing a non-negative integer, which is the sum of scores modulo $P$ for that query.

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

2
2202003
444957911

Hint

Sample Explanation

In the first query, the ID of the initial arrangement is $0$, and $T=1$.

Initially, furniture $0$ is in room $0$, furniture $1$ is in room $0$, and furniture $2$ is in room $0$. After $1$ operation, the possible cases are:

• Move furniture $0$ to room $1$. The resulting arrangement ID is $1$, and the score is $10$.
• Move furniture $1$ to room $1$. The resulting arrangement ID is $2$, and the score is $100$.
• Move furniture $2$ to room $1$. The resulting arrangement ID is $4$, and the score is $998244245$.

So, the total score over all cases is $998244355$, and modulo $P$ it is $2$.

In the second query, the ID of the initial arrangement is $0$, and $T=2$.

Initially, furniture $0$ is in room $0$, furniture $1$ is in room $0$, and furniture $2$ is in room $0$. After $2$ operations, the possible cases are:

• Move furniture $0$ to room $1$, then move furniture $0$ to room $0$. The resulting arrangement ID is $0$, and the score is $1$.
• Move furniture $0$ to room $1$, then move furniture $1$ to room $1$. The resulting arrangement ID is $3$, and the score is $1000$.
• Move furniture $0$ to room $1$, then move furniture $2$ to room $1$. The resulting arrangement ID is $5$, and the score is $100000$.
• Move furniture $1$ to room $1$, then move furniture $0$ to room $1$. The resulting arrangement ID is $3$, and the score is $1000$.
• Move furniture $1$ to room $1$, then move furniture $1$ to room $0$. The resulting arrangement ID is $0$, and the score is $1$.
• Move furniture $1$ to room $1$, then move furniture $2$ to room $1$. The resulting arrangement ID is $6$, and the score is $1000000$.
• Move furniture $2$ to room $1$, then move furniture $0$ to room $1$. The resulting arrangement ID is $5$, and the score is $100000$.
• Move furniture $2$ to room $1$, then move furniture $1$ to room $1$. The resulting arrangement ID is $6$, and the score is $1000000$.
• Move furniture $2$ to room $1$, then move furniture $2$ to room $0$. The resulting arrangement ID is $0$, and the score is $1$.

So, the total score over all cases is $2202003$, and modulo $P$ it is $2202003$.

In the third query, the ID of the initial arrangement is $1$, and $T=513066699$. Initially, furniture $0$ is in room $1$, furniture $1$ is in room $0$, and furniture $2$ is in room $0$.

... (at least $3^{513066699}$ lines omitted)

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Resources such as solutions can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5