题目描述

在一个 $n\times 3$ 的棋盘上跳马，即从 $(x,y)$ 可以跳到八个格子：

• $(x-2,y+1)$
• $(x-2,y-1)$
• $(x-1,y+2)$
• $(x-1,y-2)$
• $(x+1,y+2)$
• $(x+1,y-2)$
• $(x+2,y+1)$
• $(x+2,y-1)$

求一条汉密尔顿回路，即从任意一个位置出发，经过所有的位置恰好一次，并且最后回到起始位置的路径。如果不存在解，则输出 No solution!。

输入格式

一行，一个整数$n$。

输出格式

假如无解，输出一行，No solution!。

否则输出 $3n+1$ 行，每行输出两个空格隔开的整数 $x,y$（$1\leq x\leq n,1\leq y\leq 3$），依次表示汉密尔顿回路经过的格子，输出的相邻两个要求能够互相到达，且第一个格子和最后一个格子必须相同。

样例

input

12

output

1 1
2 3
3 1
1 2
3 3
4 1
2 2
4 3
5 1
6 3
8 2
10 1
12 2
10 3
11 1
12 3
10 2
12 1
11 3
9 2
7 1
5 2
7 3
8 1
6 2
8 3
9 1
11 2
9 3
7 2
5 3
6 1
4 2
2 1
1 3
3 2
1 1

数据范围与提示

$n\le 1000$