披萨工厂决定举办一次盛大的宾客聚会以进行宣传，并邀请了 $n$ 位最尊贵的宾客。厨师准备了 $n$ 个盘子，每个盘子上正好有一整张披萨。所有披萨的种类都各不相同。厨师不知道宾客们的喜好，因此他希望每个人都能品尝到每种类型的披萨。

为了实现这一目标，他将每张披萨切成了 $n$ 等份，现在他想把它们重新组合成 $n$ 张“节日”披萨，使得每张“节日”披萨都包含每种类型的一块披萨。他还有一个额外的小盘子，只能容纳任意披萨的一块。

厨师的一次移动可以是以下操作之一：

• 从某个盘子上取出一块披萨，并将其放入另一个盘子的空余空间中。注意，每个盘子同时最多只能容纳 $n$ 块披萨。
• 如果额外的小盘子是空的，从某个盘子上取出一块披萨并放入该小盘子中。
• 从额外的小盘子上取出一块披萨，并将其放入另一个盘子的空余空间中。

你的任务是帮助厨师制定出为了制作出 $n$ 张“节日”披萨所需的最短移动步骤序列。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 100$)。

输出格式

输出制作 $n$ 张“节日”披萨所需的最短移动步骤序列。

每行输出一次移动，由三个整数 $a$、$b$ 和 $c$ 组成 ($0 \le a, c \le n$, $1 \le b \le n$)。一行 “$a\ b\ c$” 表示厨师将属于第 $b$ 种披萨的一块从盘子 $a$ 移动到盘子 $c$，其中盘子 $0$ 表示额外的小盘子。

样例

输入样例 1

3

输出样例 1

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