题目描述

Mirko 和 Slavko 正在玩一个游戏。

Mirko 把一个骑士棋子放在一个 $N \times N$ 的棋盘上，蒙住 Slavko 的眼睛，接下来将骑士移动 $T$ 步，每秒走一步。之后，Slavko 必须猜出骑士的最终位置才能获胜。

这个游戏中的棋盘是特别的，因为每个格子都有一部分时间被禁止通行。更准确地说，每个格子上都有一个为正整数的标记，标有数字 $K$ 的正方形只有在第 $0,K,K \times 2,K \times 3,...$ 秒内才是允许通行的，在其他时间这个格子都禁止通行。当然，骑士只能在某个格子允许通行时走到该格子。

游戏从第 $0$ 秒开始。每秒钟 Mirko 必须将骑士移动一步（根据国际象棋的规则，骑士走日字，类似中国象棋中的马）。请帮助 Slavko 写一个程序来计算出所有 $T$ 秒过后骑士可能位于的格子。

输入格式

输入的第一行包含两个正整数 $N,T$。

第二行包含两个正整数 $X,Y$，代表骑士的初始坐标。

接下来 $N$ 行，每行包含 $N$ 个不超过 $10^9$ 的正整数，描述这个棋盘。

输出格式

输出的第一行为一个非负整数 $M$，表示 $T$ 秒过后骑士可能位于的格子的数量。

接下来 $M$ 行，每行包含一个坐标，表示 $T$ 秒过后骑士可能位于的格子。输出的坐标按行数升序排序，如果行数相同按列数升序排序。

3 2
1 1
1 3 2
2 3 2
3 1 1

2
1 1
1 3

5 6
2 3
4 5 3 2 3
1 3 4 3 1
3 4 1 3 2
4 4 2 1 3
4 6 4 9 2

5
1 4
2 1
2 5
4 5
5 2

3 3
2 2
3 6 4
2 2 5
1 3 7

0

提示

【样例 1 解释】

棋盘的状态如下图所示。. 代表允许通行的格子，# 代表禁止通行的格子，K 代表骑士可能位于的格子。

【数据范围】

对于 $40\%$ 的数据，$T \le 5 \times 10^4$。

对于 $100\%$ 的数据，$3 \le N \le 30$，$1 \le T \le 10^6$。

【说明】

本题分值按 COCI 原题设置，满分 $160$。

题目译自 COCI2011-2012 CONTEST #1 T6 SKAKAC。