给你一个 $n \times n$ 的矩阵 $S$ 和一个整数 $k$（$2^k \le n$）。考虑以下矩阵递推式：

$$T_0 = (1)$$

$$T_{i+1} = \begin{pmatrix} T_i \cdot a_{00} & T_i \cdot a_{01} \\ T_i \cdot a_{10} & T_i \cdot a_{11} \end{pmatrix}$$

其中

$$A = \begin{pmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{pmatrix}$$

是一个常数 $2 \times 2$ 矩阵。

对于每个满足 $0 \le i \le k$ 的 $i$，求矩阵 $T_i$ 与 $S$ 的所有大小为 $2^i \times 2^i$ 的连续子矩阵的点积的最小值和最大值。

两个矩阵

$$\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{pmatrix} \quad \text{和} \quad \begin{pmatrix} b_{11} & b_{12} & \cdots & b_{1n} \\ b_{21} & b_{22} & \cdots & b_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{nn} \end{pmatrix}$$

的点积定义为 $\sum_{i=1}^n \sum_{j=1}^n a_{ij} \cdot b_{ij}$。

输入格式

第一行包含 $2$ 个整数 $n, k$（$1 \le n \le 1000, 1 \le 2^k \le n$）。

接下来的 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行的第 $j$ 个整数为 $S_{ij}$（$-10^9 \le S_{ij} \le 10^9$）。

接下来的 $2$ 行，每行包含 $2$ 个整数，格式相同，表示矩阵 $A$。$A$ 的元素的绝对值不超过 $2$。

输出格式

输出 $k + 1$ 行。第 $(i + 1)$ 行应包含 $2$ 个整数，分别表示 $S$ 的连续子矩阵与 $T_i$ 的点积的最小值和最大值。

样例

输入样例 1

3 1
9 -3 13
0 10 3
10 -10 0
1 -1
-1 1

输出样例 1

-10 13
-30 22