Migrated from Lutece 2772 下棋

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Alice 和 Bob 正在下棋。

棋盘的大小是 $n$ 行 $n$ 列，一共有 $n \times n$ 个格子。Alice 和 Bob 轮流放置棋子在棋盘的某一个格子里。放置棋子的规则如下：

1. 除去第一次放置棋子，每一次放置的棋子必须保证和上一次放置的棋子的曼哈顿距离大于 $m$。例如：上一次放置的棋子的位置是 $(x_1, y_1)$, 本次放置的棋子的位置是 $(x_2, y_2)$, 必须保证 $|x_2 - x_1| + |y_2 - y_1| > m$ 成立。
2. 棋子可以重叠放置。即使某一位置已经被放置过棋子，只要这个位置满足上面的规则，依然可以再次放置棋子。

$m$ 等于 $2$ 时，红色区域是下一步不能落子的位置。

棋盘上的每一个位置 $(x, y)$ 都有一个分数 $a_{x, y}$, 且分数之间互不相同。只要放置棋子在位置 $(x, y)$, 就可以得到分数 $a_{x, y}$, 即使重叠放置，也可以得到分数。棋局进行 $2 ^ {2022}$ 个回合后会终止，此时得分高的人获胜。

Alice 和 Bob 都很聪明，他们都会采用最优策略下棋。现在 Alice 想知道假如 Alice 先手下棋，他在棋盘上的哪些位置放置第一步棋会赢。

Input

第一行，两个整数 $n, m(3 \leq n \leq 2000, 1 \leq m \leq n - 2)$。 对于第一行之后的 $n$ 行，每一行有 $n$ 个整数。其中第 $i$ 行，第 $j$ 列的整数 $a_{i, j} (1 \leq a_{i, j} \leq n^{2})$ 表示在棋盘 $(i, j)$ 位置上的分数。分数之间互不相同。

Output

第一行，一个整数 $k$， 表示有 $k$ 个位置 Alice 放置第一步棋会赢。 下面 $k$ 行，每一行输出两个整数 $x, y$，表示 Alice 放置第一步棋会赢的位置的行和列。 $k$ 个位置需要按 $x$ 从小到大排序，如果 $x$ 相同，则按 $y$ 从小到大排序。

注意：本题不含 Special Judge，答案是唯一的。

Samples

3 1
1 2 3
4 5 6
7 8 9

2
3 2
3 3

Resources

2022 UESTC ICPC Training for Dynamic Programming