Define a matrix transformation $\mathcal F$ that transforms an $n \times n$ matrix $P$ into another $n \times n$ matrix $Q$: for each $1 \le i, j \le n$, the value of $Q_{i,j}$ is equal to the sum of all elements in the $i$-th row and the $j$-th column of matrix $P$.

Given an $n \times n$ matrix $P$, calculate the result of applying the transformation $\mathcal F$ to $P$ consecutively $t$ times. Output the result modulo $\mathrm{mod}$.

Input

The first line contains three integers $n, t, \mathrm{mod}$, representing the size of the matrix, the number of times the transformation $\mathcal F$ is applied, and the modulus, respectively.

The next $n$ lines each contain $n$ integers in the range $[0, \mathrm{mod}-1]$, representing the elements of the matrix.

Output

Output $n$ lines, each containing $n$ integers in the range $[0, \mathrm{mod}-1]$, representing the result.

For all data, $1 \le n \le 1000, 0 \le t \le 10^9, 2 \le \mathrm{mod} \le 10^9$.

Examples

Input 1

3 2 10
1 2 3
4 5 6
7 8 9

Output 1

4 3 2
1 0 9
8 7 6

Note 1

1. Initial matrix: $$ \begin{matrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{matrix} $$

2. After one transformation: $$ \begin{matrix} 8 &1 &4\\ 7 &0 &3\\ 6 &9& 2 \end{matrix} $$

3. After two transformations: $$ \begin{matrix} 4 &3& 2\\ 1 &0 &9\\ 8 &7 &6\\ \end{matrix} $$

Subtasks

Subtask 1 (17 points): $n \le 100, t \le 100$.

Subtask 2 (26 points): $\mathrm{mod} = 2$.

Subtask 3 (57 points): $n \le 1000, t \le 10^9, \mathrm{mod} \le 10^9$.