19365번 - Matrix Recurrence 다국어

문제

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}$.

제한

힌트