B-kun and G-kun are on a pedestrian overpass.

B-kun: "It's winter again. It's been over three years since we started university."

G-kun: "Indeed."

B-kun: "There are so many couples on the street. Thinking back to three years ago, I was just like that..."

G-kun: "??"

B-kun: "...watching couples from the overpass!"

G-kun: "Hmm."

B-kun: "But this time, you're here with me~"

G-kun: "..."

B-kun: "Hey, hey, I have a question for you~"

G-kun: "Ask away."

B-kun: "Suppose $n=3^m$ people are playing rock-paper-scissors together."

G-kun: "Huh? What is 'cei ding ke'?"

B-kun: "It's rock-paper-scissors~, we also call it 'ding gang chui'."

G-kun: "That's what you wanted to ask?"

B-kun: "Wait, I haven't finished yet."

Description

$n = 3^m$ people are playing rock-paper-scissors. There are $t$ rounds of the game, and each round consists of $m$ matches of rock-paper-scissors.

In the $m$ matches of a single round, each person's strategy must be determined in advance; that is, they cannot use a random strategy, nor can they decide their next move based on the results of previous matches. Thus, there are clearly $n = 3^m$ possible strategies.

These $n = 3^m$ people will each adopt a unique strategy. For convenience, for the $x$-th person ($0 \leq x < n$), we convert $x$ into a base-3 number of $m$ digits, where $0$ represents scissors, $1$ represents rock, and $2$ represents paper. This gives the strategy adopted by the $x$-th person.

Since the IDs are fixed, everyone uses the same strategy in every round.

The $x$-th person initially has a score $f_{0, x}$.

In the $i$-th round, they play $m$ matches of rock-paper-scissors against another person $y$.

We denote $W(x, y)$ as the number of times $x$ wins against $y$ in the $m$ matches, and $L(x, y)$ as the number of times $x$ loses against $y$ in the $m$ matches.

After the $i$-th round, the score of the $x$-th person is:

$$ f_{i, x} = \sum_{0 \leq y < n} f_{i-1, y} b_{u, v} $$

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

Note that even if $y$ is the same as $x$ (a person transitioning to themselves), they are multiplied by a coefficient $b_{0, 0}$ (since playing against oneself results in all ties).

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

B-kun wants to know the scores of everyone after $t$ rounds, i.e., $f_{t, 0}, f_{t, 1}, \ldots, f_{t, n - 1}$.

G-kun: "Hey, I noticed this number $p$ has a special property! There are no two positive integers such that the sum of their reciprocals equals $3/p$!"

B-kun: "G-kun is amazing! But how do we solve this problem?"

Input

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 \leq f_{0, i} < p$.

The following part is the array $b$. The 1st line contains $m + 1$ numbers, the 2nd line contains $m$ numbers... the $(m + 1)$-th line contains 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 \leq b_{i, j} < p$.

There are no two positive integers $x, y > 0$ such that $1/x + 1/y = 3/p$.

Output

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

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

Examples

Input 1

1 1 10009
10 100 1000
2 3
4

Output 1

4320
3240
2430

Input 2

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

Output 2

96
8
73
38
53
15
27
42
4

Constraints

For all data, $0 \leq m \leq 12$, $0 \leq t \leq 10^{9}$, $1 \leq p \leq 10^{9}$.