Description

给定一个大小为 $n \times m$ 的矩阵，矩阵元素为 $a_{i,j}$。

我们定义以点 $(x,y)$ 为起点、大小为 $k$ 的三角形为：从 $(x,y)$ 出发，通过向上或向右移动不超过 $k-1$ 步所能到达的所有点的集合。

对于每个满足 $(k \le x \le n, 1 \le y \le m-k+1)$ 的点 $(x,y)$，需要求出以下两个值：

• 以 $(x,y)$ 为起点的大小为 $k$ 的三角形中的最大值；
• 该最大值在三角形中出现的次数。

Input Format

第一行包含三个整数 $n$、$m$ 和 $k$ $(1 \le n,m \le 2\,000, 1 \le k \le \min(n,m))$ —— 分别表示矩阵的行数、列数和三角形的大小。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$ $(0 \le a_{i,j} \le 10^6)$ —— 表示矩阵的元素。

Output Format

输出两个大小为 $(n-k+1) \times (m-k+1)$ 的矩阵。

第一个矩阵的第 $(i,j)$ 个位置应包含以 $(i+k-1,j)$ 为起点的大小为 $k$ 的三角形中的最大值。

第二个矩阵的第 $(i,j)$ 个位置应包含该最大值在对应三角形中出现的次数。

4 4 2
1 2 6 14
12 3 13 5
11 4 7 8
10 16 9 15

12 13 13 
12 7 13 
16 16 15 
1 1 1 
1 1 1 
1 1 1 

Hint

• （$5$ 分）：$n,m \le 20$；
• （$10$ 分）：$n,m \le 100$；
• （$30$ 分）：$a_{i,j} \le 1$；
• （$35$ 分）：$n,m \le 1\,000$；
• （$20$ 分）：无额外限制。

翻译由 DeepSeek V3 完成