一个欧洲足球锦标赛共有 $n$ 支参赛队伍。在第一轮中，进行 $n/2$ 场比赛，每支队伍与其他一支队伍进行比赛。每一轮结束后，只有获胜的队伍晋级下一轮。在第二轮中，进行 $n/4$ 场比赛，每场比赛由第一轮的胜者对阵另一名第一轮的胜者。最终，只剩下两支队伍进行决赛。决赛的胜者即为锦标赛的冠军。

荷兰足球队可能不是世界上最强的队伍，但他们依然是一支相当不错的队伍。他们可以轻松击败至少一半的其他队伍。此外，对于荷兰队在直接对抗中无法击败的每一支队伍 $t$，都存在另一支队伍 $t'$，该队伍能击败 $t$，但会被荷兰队击败。

荷兰队教练希望操纵锦标赛，使荷兰队成为冠军。他碰巧知道每一对队伍之间如果进行比赛，哪支队伍一定会获胜。

题目描述

对于任意两支队伍，你预先知道如果它们进行比赛，哪一方会获胜。（由于这是淘汰赛，不会出现平局。）此外，你确定你的目标队伍（即荷兰队）可以击败至少一半的其他队伍，并且对于你的目标队伍无法击败的每一支队伍 $t$，都存在一支队伍 $t'$，该队伍能击败 $t$ 但会被你的目标队伍击败。

请确定一个锦标赛赛程，使得你的目标队伍赢得锦标赛。

输入格式

对于每个测试用例，输入如下： 第一行包含队伍数量 $n$，其中 $n$ 是 2 的幂，且 $2 \le n \le 1024$。队伍编号从 $1$ 到 $n$，其中队伍 $1$ 是你的目标队伍。 $n$ 行，每行包含一个长度为 $n$ 的二进制字符串。 第 $j$ 行的第 $k$ 个数字如果为 ‘1’，表示队伍 $j$ 一定能击败队伍 $k$，否则为 ‘0’。 队伍不能与自己比赛，因此第 $j$ 行的第 $j$ 个数字为 ‘0’。 若 $j \neq k$，则第 $j$ 行的第 $k$ 个数字与第 $k$ 行的第 $j$ 个数字不同。

输出格式

对于每个测试用例，输出 $n-1$ 行，指定一个确保队伍 $1$ 获胜的锦标赛赛程。 前 $n/2$ 行描述锦标赛的第一轮。接下来的 $n/4$ 行描述第二轮（如果有的话），以此类推。最后一行描述决赛。 每行包含两个整数 $x$ 和 $y$，表示队伍 $x$ 与队伍 $y$ 进行比赛。 如果存在多种使得队伍 $1$ 获胜的赛程，输出其中任意一种即可。

样例

输入 1

4
0110
0011
0000
1010

输出 1

1 3
2 4
1 2

输入 2

8
00111010
10101111
00010010
01000101
00110010
10101011
00010000
10101010

输出 2

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