给定一个大小为 $n \times m$ 的矩形数组 $a$ 和一个素数 $p$，请找到两个矩形数组 $b$（大小为 $K \times n$）和 $c$（大小为 $K \times m$），使得：

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_{j=1}^{m} c_{i,j} \ge 1$ ($\forall 1 \le i \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$)。

输入格式

第一行包含四个整数 $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$ 为素数)。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} < p$)。

输出格式

如果没有解，输出一行 “No solution!”。

否则，输出 $K$ 行，第 $i$ 行包含 $n + m$ 个整数 $b_{i,1}, b_{i,2}, \dots, b_{i,n}, c_{i,1}, c_{i,2}, \dots, c_{i,m}$。

如果存在多个可能的答案，输出其中任意一个即可。

样例

样例输入 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