题目描述

Y 同学得到了一个大小为 $n \times n$ 的字符方阵，其中每个位置都填有一个小写英文字母。

已知该方阵满足以下条件：

• 方阵中恰好出现了 $n$ 种不同的字母；
• 对于每一种出现过的字母 $c$，恰好有 $1$ 头与之对应的猪；
• 因而一共恰好有 $n$ 头猪。

对于字母 $c$ 对应的那头猪，它只能被放置在字符为 $c$ 的格子上。

现在，Y 同学需要在方阵中为这 $n$ 头猪各选出一个位置，并满足以下要求：

1. 对于任意一头猪，它所选位置上的字符必须等于该猪对应的字母；
2. 任意两头猪不能位于同一行；
3. 任意两头猪不能位于同一列；
4. 任意两头猪不能在八个方向上相邻。更形式化地说，若两头猪分别位于 $(x_1,y_1)$ 与 $(x_2,y_2)$，则不能同时满足 $ \lvert x_1-x_2\rvert \le 1,\ \lvert y_1-y_2\rvert \le 1 $ 且 $(x_1,y_1)\ne(x_2,y_2)$。

题目保证：

• 满足条件的合法方案存在且唯一；
• 按照如下消元过程，整个过程一定可以顺利进行：

设当前尚未确定位置的猪构成一个集合。每一步中，在这些猪里一定至少存在一种字母，其当前仍然合法的候选位置恰好只剩下 $1$ 个。此时确定这头猪的位置，并将该位置所在的整行、整列，以及与该位置八个方向相邻的所有位置，从其余未确定猪的候选集合中删除。不断重复这一过程，直到所有猪的位置都被确定。

坐标从 $1$ 开始计数，左上角位置记为 $(1,1)$。

你需要输出所有猪所在的位置。输出时按照行优先顺序输出，即先按行号从小到大排序；若行号相同，则按列号从小到大排序。

输入格式

第一行输入一个整数 $n$，表示方阵的大小，同时也表示猪的数量。

接下来输入 $n$ 行，每行一个长度为 $n$ 的字符串，表示该字符方阵。

输出格式

输出 $n$ 行。

每行输出两个整数 $x,y$，表示一头猪所在的位置。

输出顺序需满足：先按 $x$ 升序排列；若 $x$ 相同，则按 $y$ 升序排列。

样例

样例输入 #1

4
dadb
ddbb
cddd
bddd

样例输出 #1

1 2
2 4
3 1
4 3

数据范围与约定

对于 $100$ 的数据，保证：

• $1 \le n \le 26$；
• 方阵中的字符均为小写英文字母；
• 方阵中恰好出现了 $n$ 种不同的字符；
• 合法方案存在且唯一；
• 按照题面给出的消元过程，任意时刻都至少存在一种尚未确定位置的猪，其当前合法候选位置数恰好为 $1$。

特殊性质 A：每种字母在方阵中恰好出现 $1$ 次。

特殊性质 B：对于任意一种字母，其在方阵中的出现次数不超过 $2$。

特殊性质 C：最终答案中所有猪所在位置两两均满足行号严格递增且列号严格递增。

特殊性质 D：每一步消元时，当前合法候选位置恰好为 $1$ 的字母唯一。