cho.sh

Matrix Recurrence

아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

Bobo invents a new series of matrices M_0,M_1,…M_nM\_0, M\_1, \dots M\_n defined as follows:

  • M_0=AM\_0 = A,
  • M_i=(∏_j=c_ii−1M_j)×BM\_i = \left(\prod\limits\_{j = c\_i}^{i - 1} M\_j\right) \times B.

Given m×mm \times m matrices A,BA, B and integers c_1,c_2,…,c_nc\_1, c\_2, \dots, c\_n, compute M_nM\_n under Z_mod\mathbb{Z}\_{\mathrm{mod}} (that is, addition and multiplication of numbers are carried out modulo mod\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 nn, mm and mod\mathrm{mod} (1≤n≤1061 \leq n \leq 10^6, 1≤m≤51 \leq m \leq 5, 2≤mod≤1092 \leq \mathrm{mod} \leq 10^9). 

The ii-th of the next mm lines contains mm integers A_i,1,A_i,2,…,A_i,mA\_{i, 1}, A\_{i, 2}, \dots, A\_{i, m}, and the ii-th of the following mm lines contains mm integers B_i,1,B_i,2,…,B_i,mB\_{i, 1}, B\_{i, 2}, \dots, B\_{i, m} (0≤A_i,j,B_i,j<mod0 \leq A\_{i, j}, B\_{i, j} < \mathrm{mod}).

The last line contains nn integers c_1,c_2,…,c_nc\_1, c\_2, \dots, c\_n (0≤c_i<i0 \leq c\_i < i, c_1≤c_2≤⋯≤c_nc\_1 \leq c\_2 \leq \dots \leq c\_n).

It is guaranteed that the sum of nn does not exceed 10610^6.

출력

For each test case, output mm lines. On the ii-th line, output mm integers C_i,1,C_i,2,…,C_i,mC\_{i, 1}, C\_{i, 2}, \dots, C\_{i, m} where C_i,j=M_n,i,jC\_{i, j} = M\_{n, i, j}.