시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 67 | 13 | 9 | 24.324% |
Bobo invents a new series of matrices $M_0, M_1, \dots M_n$ defined as follows:
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}$.
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 2 0 1 1 0 0 1 1 1 0 1