Bobo 发明了一系列新的矩阵 $M_0, M_1, \dots, M_n$，定义如下：

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

给定 $m \times m$ 的矩阵 $A, B$ 以及整数 $c_1, c_2, \dots, c_n$，计算 $\mathbb{Z}_{\text{mod}}$ 下的 $M_n$（即加法和乘法均在模 $\text{mod}$ 意义下进行）。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含三个整数 $n, m$ 和 $\text{mod}$ ($1 \le n \le 10^6, 1 \le m \le 5, 2 \le \text{mod} \le 10^9$)。

接下来的 $m$ 行中，第 $i$ 行包含 $m$ 个整数 $A_{i,1}, A_{i,2}, \dots, A_{i,m}$；随后的 $m$ 行中，第 $i$ 行包含 $m$ 个整数 $B_{i,1}, B_{i,2}, \dots, B_{i,m}$ ($0 \le A_{i,j}, B_{i,j} < \text{mod}$)。

最后一行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($0 \le c_i < i, c_1 \le c_2 \le \dots \le c_n$)。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出 $m$ 行。在第 $i$ 行，输出 $m$ 个整数 $C_{i,1}, C_{i,2}, \dots, C_{i,m}$，其中 $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