시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB111100.000%

문제

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.

예제 입력 1

1 1 1 97
0

예제 출력 1

No solution!

예제 입력 2

3 3 1 97
1 2 3
2 4 6
3 6 9

예제 출력 2

1 2 3 1 2 3