题目描述

给定一个由 $0$ 和 $1$ 组成的 $n \times n$ 二进制矩阵。初始时，你有一个空字符串 $S$。

你从位置 $(0,0)$，即左上角开始，每一步只能向右或向下移动。你会按照经过格子的顺序，将每个经过格子的元素依次追加到字符串 $S$ 中。

请判断是否存在一种走法，使得最终得到的 $S$ 是一个回文串。如果存在，请输出达到这一目标的路径。

注意：本题中的每个矩阵都是随机生成的。

输入格式

第一行包含唯一的整数 $n$，表示矩阵大小。

接下来 $n$ 行，每行包含 $n$ 个字符 $a_{i,j}$，表示矩阵内容。

输入矩阵是在所有合法的 $n \times n$ 二进制矩阵中随机选取的。

输出格式

如果不存在这样的回文路径，输出 NO。

否则，第一行输出 YES。接下来 $2n-1$ 行，每行输出两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个经过的格子的坐标。

坐标满足 $0 \le x_i,y_i < n$。

输入

2
01
00

输出

YES
0 0
0 1
1 1

数据范围

$1 \le n \le 5000$

$0 \le a_{i,j} \le 1$

评分方式

1. $5$ 分：$n \le 10$；
2. $9$ 分：$n \le 100$；
3. $19$ 分：$n \le 500$；
4. $27$ 分：$n \le 1500$；
5. $40$ 分：无额外限制。