Sum

Time limit3sMemory limit512 MB

Summary

Given an n by m matrix modulo a prime p, find K rank-one style pairs of vectors b and c whose sum of outer products equals the matrix, with nonzero row and column sums.

Level: Hard8 of 10
Topics: Matrix, Math, Implementation
Solved: No attempts yet

Statement

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:

$0 \le b_{i,j} < p$ ( $\forall 1 \le i \le K, 1 \le j \le n$ )
$0 \le c_{i,j} < p$ ( $\forall 1 \le i \le K, 1 \le j \le m$ )
$\sum_{j=1}^{n} b_{i,j} \ge 1$ ( $\forall 1 \le i \le K$ )
$\sum_{i=1}^{m} c_{i,j} \ge 1$ ( $\forall 1 \le j \le K$ )
$\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$ )

Input

The first line 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$ ).

Output

If there is no solution, print a line No solution!.

Otherwise, print $K$ lines. The $i$ -th line 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.

Examples2

Example 1
Input
```
1 1 1 97
0
```
Expected output
```
No solution!
```
Example 2
Input
```
3 3 1 97
1 2 3
2 4 6
3 6 9
```
Expected output
```
1 2 3 1 2 3
```