# D.PT讨厌合数

## 题目描述

$\hspace{15pt}$对于给定的三个整数 $n,m,k$，你需要构造一个 $n$ 行 $m$ 列的网格，每一个格子中填入一个整数，满足以下所有条件：  
$\hspace{23pt}\bullet\,$格子中的所有数互不相同，且格子中的每个数在 $[1,k]$ 的区间内。  
$\hspace{23pt}\bullet\,$小牛要从网格左上角走到右下角，每次只能向下或向右移动一格，小牛在初始位置有个空集合 $\Bbb S$，记当前小牛位于的格子上的数字为 $a$，记小牛想移动到的下一个格子上的数字为 $b$，当满足 $\gcd(a,b)$ 的值为质数或者为 $1$，且没有在集合 $\Bbb S$ 中出现过，小牛才被允许走到此位置，然后将 $\gcd(a,b)$ 存入集合 $\Bbb S$ 中。
$\hspace{23pt}\bullet\,$遵循上述行走规则，至少存在一条路径可以使得小牛胜利到达终点。

$\hspace{15pt}$同时，您所构造的网格在满足以上条件的情况下，还需要保证格子中所有值的最大值要最小。  
$\hspace{15pt}$如果不存在符合条件的构造方案，直接输出 $-1$；否则，输出您所构造的网格方案，同时指出一条可以使得小牛胜利到达终点的路径。  

【名词解释】
$\hspace{15pt}$$\gcd$，即最大公因数，指两个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有 $1,2,3,6$，其中最大的约数是 $6$，因此 $\gcd(12,30)=6$。

## 输入描述

$\hspace{15pt}$在一行上输入三个整数 $n, m ,k \left(1 \leq n,m \leq 2 \times 10^3;\ 1 \leq k \leq 10^9\right)$ 代表方格的大小、方格值的选取范围。

## 输出描述

$\hspace{15pt}$如果不存在符合条件的构造方案，直接输出 $-1$。  
  
$\hspace{15pt}$否则，请参考下方的格式输出。  
$\hspace{15pt}$第一行输出一个整数 $p$ 代表方格中的最大值。  
$\hspace{15pt}$随后 $n$ 行，每行输出 $m$ 个整数，代表方格中的值。  
$\hspace{15pt}$随后 $n+m-1$ 行，每行输出两个整数 $x,y$ 代表一条满足条件的，从左上角移动到右下角的路径。  
  
$\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

## 样例

~~~text input:#1
1 2 2
~~~

~~~text output:#1
2
1 2
1 1
1 2
~~~

$\hspace{15pt}$在这个样例中，有且仅有两种矩阵的构造方式：$\begin{bmatrix}1 & 2\end{bmatrix}$ 和 $\begin{bmatrix}2 & 1\end{bmatrix}$。这两个方案均满足全部条件，输出任意一个即可。

~~~text input:#2
5 5 10
~~~

~~~text output:#2
-1
~~~

$\hspace{15pt}$在这个样例中，可以发现 $1$ 到 $10$ 以内的质数只有 $2,3,5,7$ 四个，不够用，所以输出 $-1$。

~~~text input:#3
4 4 100
~~~

~~~text output:#3
22
18 21 14 15
9 8 5 10
16 19 2 22
1 4 13 11
1 1
1 2
1 3
1 4
2 4
3 4
4 4
~~~

$\hspace{15pt}$在这个样例中，构造的矩阵如公式所示，其中，橙色的数字为路线经过的地方：$\begin{bmatrix}
{\color{orange}{18}} & {\color{orange}{21}} & {\color{orange}{14}} & {\color{orange}{15}}\\
9 & 8 & 5 & {\color{orange}{10}}\\
16 & 19 & 2 & {\color{orange}{22}}\\
1 & 4 & 13 & {\color{orange}{11}}
\end{bmatrix}$。  
$\hspace{15pt}$具体地：  
$\hspace{23pt}\bullet\,$当走到 $(1,2)$ 时，$\gcd(18,21)=3$，$\Bbb S = \{3\}$；  
$\hspace{23pt}\bullet\,$当走到 $(1,3)$ 时，$\gcd(21,14)=7$，$\Bbb S = \{3,7\}$；  
$\hspace{23pt}\bullet\,$当走到 $(1,4)$ 时，$\gcd(14,15)=1$，$\Bbb S = \{3,7,1\}$；  
$\hspace{23pt}\bullet\,$当走到 $(2,4)$ 时，$\gcd(15,10)=5$，$\Bbb S = \{3,7,1,5\}$；  
$\hspace{23pt}\bullet\,$当走到 $(3,4)$ 时，$\gcd(10,22)=2$，$\Bbb S = \{3,7,1,5,2\}$；  
$\hspace{23pt}\bullet\,$当走到 $(4,4)$ 时，$\gcd(22,11)=11$，$\Bbb S = \{3,7,1,5,2,11\}$。  
$\hspace{15pt}$综上，方案成立。