시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB6713924.324%

문제

Bobo invents a new series of matrices $M_0, M_1, \dots M_n$ defined as follows:

  • $M_0 = A$,
  • $M_i = \left(\prod\limits_{j = c_i}^{i - 1} M_j\right) \times B$.

Given $m \times m$ matrices $A, B$ and integers $c_1, c_2, \dots, c_n$, compute $M_n$ under $\mathbb{Z}_{\mathrm{mod}}$ (that is, addition and multiplication of numbers are carried out modulo $\mathrm{mod}$).

입력

The input contains zero or more test cases, and is terminated by end-of-file. For each test case:

The first line contains three integers $n$, $m$ and $\mathrm{mod}$ ($1 \leq n \leq 10^6$, $1 \leq m \leq 5$, $2 \leq \mathrm{mod} \leq 10^9$). 

The $i$-th of the next $m$ lines contains $m$ integers $A_{i, 1}, A_{i, 2}, \dots, A_{i, m}$, and the $i$-th of the following $m$ lines contains $m$ integers $B_{i, 1}, B_{i, 2}, \dots, B_{i, m}$ ($0 \leq A_{i, j}, B_{i, j} < \mathrm{mod}$).

The last line contains $n$ integers $c_1, c_2, \dots, c_n$ ($0 \leq c_i < i$, $c_1 \leq c_2 \leq \dots \leq c_n$).

It is guaranteed that the sum of $n$ does not exceed $10^6$.

출력

For each test case, output $m$ lines. On the $i$-th line, output $m$ integers $C_{i, 1}, C_{i, 2}, \dots, C_{i, m}$ where $C_{i, j} = M_{n, i, j}$.

예제 입력 1

2 2 1000000000
1 1
0 1
1 0
0 1
0 0
2 2 2
1 1
0 1
1 0
0 1
0 0
5 2 1000000000
1 1
0 1
1 0
0 1
0 1 2 3 4

예제 출력 1

1 2
0 1
1 0
0 1
1 1
0 1