Description

There are $n=3^m$ people playing rock-paper-scissors. There are a total of $t$ rounds, and in each round there are $m$ games of rock-paper-scissors.

Within the $m$ games of the same round, each person’s decisions must be fixed in advance. That is, they cannot use a randomized strategy, and they cannot decide the next game based on the results of previous games. Therefore, there are clearly $n=3^m$ possible strategies.

These $n=3^m$ people will all use pairwise different strategies. For convenience, for person $x$ ($0 \le x < n$), convert $x$ to base $3$ to get an $m$-digit number, where $0$ means scissors, $1$ means rock, and $2$ means paper. This gives the strategy used by person $x$.

Since the indices are fixed, in the $m$ games of each round, everyone will always use the same set of decisions across different rounds.

Person $x$ initially has a score $f_{0,x}$.

In round $i$, he will play $m$ games of rock-paper-scissors against another person $y$.

Let $W(x,y)$ be the number of wins of $x$ against $y$ in these $m$ games. Let $L(x,y)$ be the number of losses of $x$ against $y$.

After round $i$ ends, person $x$’s score is:

where $u=W(x,y)=L(y,x)$ and $v=L(x,y)=W(y,x)$. Draws are not counted; $b_{u,v}$ is a given scoring array.

Note that even if $y$ is the same as $x$ (transitioning from oneself to oneself), it will still be multiplied by a coefficient $b_{0,0}$ (because playing against oneself results in all draws).

Obviously, as the number of rounds increases, the scores will grow larger. This scoring system, like computers in daily use, can overflow. When a score $f$ to be stored is greater than or equal to $p$, it becomes $f \bmod p$.

Mr. B wants to know everyone’s scores after $t$ rounds, i.e., $f_{t,0}, f_{t,1}, \ldots, f_{t,n-1}$.

Mr. G: “Hey, I found that this number $p$ has a special property! There do not exist two positive integers such that the sum of their reciprocals equals $3/p$!”

Mr. B: “Mr. G is amazing! But how do we solve this problem?”

Input Format

The first line contains three integers $m, t, p$.

The second line contains $n=3^m$ integers, representing $f_{0,0}, f_{0,1}, \ldots, f_{0,n-1}$. It is guaranteed that $0 \le f_{0,i} < p$.

The following part is an array $b$: the 1st line has $m+1$ numbers, the 2nd line has $m$ numbers, ..., and the $(m+1)$-th line has $1$ number.

The $j$-th number in the $i$-th line is $b_{i-1,j-1}$ ($i,j \ge 1, i+j-2 \le m$). It is guaranteed that $0 \le b_{i,j} < p$.

There do not exist two positive integers such that the sum of their reciprocals equals $3/p$. That is, there do not exist positive integers $x,y>0$ such that $1/x+1/y=3/p$.

Output Format

Output $n=3^m$ lines, each containing one integer, representing each person’s final score.

The $i$-th line represents the $i$-th person’s score $f_{t,i}$.

1 1 10009
10 100 1000
2 3
4

4320
3240
2430

2 3 103
7 8 9 10 11 12 13 14 15
1 2 3
4 5
6

96
8
73
38
53
15
27
42
4

Hint

For all testdata, $0 \le m \le 12$, $0 \le t \le 10^9$, $1 \le p \le 10^9$.

Translated by ChatGPT 5