23143번 - Sum 스페셜 저지다국어

문제

Given a rectangular array $a$ of size $n \times m$ and a prime number $p,ドル find two rectangular arrays, $b$ of size $K \times n$ and $c$ of size $K \times m,ドル such that:

1. 0ドル\le b_{i,j} < p$ ($\forall 1 \le i \le K, 1 \le j \le n$);
2. 0ドル\le c_{i,j} < p$ ($\forall 1 \le i \le K, 1 \le j \le m$);
3. $\sum_{j=1}^n b_{i,j} \ge 1$ ($\forall 1 \le i \le K$);
4. $\sum_{i=1}^m c_{i,j} \ge 1$ ($\forall 1 \le j \le K$);
5. $\sum_{l=1}^K b_{l,i} \cdot c_{l,j} \equiv a_{i,j} \pmod{p}$ ($\forall 1 \le i \le n, 1 \le j \le m$).

입력

The first line of input contains four positive integers $n,ドル $m,ドル $K,ドル $p$ (1ドル \le n \cdot m, K \cdot n, K \cdot m \le 10^5$; 2ドル \le p \le 10^9 + 7$; $p$ is prime).

The $i$-th of the following $n$ lines contains $m$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$ (0ドル \le a_{i,j} < p$).

출력

If there is no solution, output a line "No solution!".

Otherwise, output $K$ lines, $i$-th of which contains $n + m$ integers $b_{i,1}, b_{i,2}, \ldots, b_{i,n}, c_{i,1}, c_{i,2}, \ldots, c_{i,m}$.

If there are several possible answers, print any one of them.

제한

힌트