若干年前，棋盘的大小为 $n \times n$（$n$ 为偶数），被划分为 $1 \times 1$ 的方格。然而，多年过去，国际象棋王国发生了许多变化。

魔法进步从未停止，在测试最新大规模杀伤性武器的过程中，棋盘的两个角方格 $(1, 1)$ 和 $(n, n)$ 被摧毁了。此外，宫廷魔法师们了解到了一个平行世界的存在——所谓的“镜中世界”（Through the Looking Glass），它位于棋盘的另一侧。他们甚至学会了使用特殊的传送门，从任何棋盘方格移动到对应的“镜中世界”方格（即位于给定方格正下方的方格），反之亦然。

白王想和他的忠实朋友再次访问他王国的所有方格。他的朋友，即骑士（Knight），按照通常的国际象棋规则移动：首先向一个方向移动两格，然后将移动方向改变 90 度（向左或向右）并移动一格。在“镜中世界”中，骑士的移动方式完全相同。此外，国王有一个袖珍传送门，他和骑士可以用它往返于“镜中世界”。需要注意的是，使用传送门和骑士的移动都被视为一次移动。

请帮助白王找到一条移动路径。每一个 $2n^2 - 4$ 个棋盘方格都应该被恰好访问一次。此外，路径应该是闭合的，也就是说，应该能够从路径的第一个方格移动到最后一个方格，且仅需一步。宫廷智者已经证明这样的路径是存在的。

输入格式

给定一个偶数整数 $n$ ($4 \le n \le 100$)。

输出格式

输出 $2n^2 - 4$ 行。第 $i$ 行应描述骑士在第 $i$ 次移动开始时的位置，格式如下：$x\ y\ w$ ($1 \le x, y \le n, 0 \le w \le 1$)。其中 $x$ 和 $y$ 是方格的坐标，$w$ 是骑士和国王所处的世界：0 代表正常世界，1 代表“镜中世界”。所有方格必须各不相同。不应出现诸如 “1 1 0”、“1 1 1”、“n n 0”、“n n 1” 这样的方格。允许从任何单元格开始路径。详见样例。

如果有多种方案，输出其中任意一种即可。

样例

输入 1

4

输出 1

3 1 0
4 3 0
4 3 1
3 1 1
2 3 1
2 3 0
4 2 0
3 4 0
3 4 1
4 2 1
2 1 1
1 3 1
3 2 1
2 4 1
1 2 1
3 3 1
1 4 1
2 2 1
4 1 1
4 1 0
2 2 0
1 4 0
3 3 0
2 1 0
1 3 0
3 2 0
2 4 0
1 2 0