考虑一个 $n \times n$ 的棋盘，方格坐标从 $(1, 1)$ 到 $(n, n)$。棋盘上有一枚“长马”。长马可以从方格 $(x, y)$ 移动到 $(x', y')$，当且仅当满足以下两个条件之一：

• $|x - x'| = 3$ 且 $|y - y'| = 1$
• $|x - x'| = 1$ 且 $|y - y'| = 3$

本质上，这与普通的国际象棋马的走法相同，只是步长更长。

棋盘的“巡游”是指一个方格序列 $S_1, S_2, S_3, \dots, S_n$，使得对于所有 $1 \le i \le n - 1$，从 $S_i$ 到 $S_{i+1}$ 的移动都是长马的合法走法。当且仅当该巡游恰好访问棋盘的每一行和每一列各一次时，称该巡游为“完全”巡游。

对于每个正整数 $n$，判断 $n \times n$ 的棋盘是否存在完全巡游，如果存在，请构造出其中一种。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示棋盘的大小。

输出格式

如果无法创建“完全”巡游，则在唯一的一行中输出字符串 “IMPOSSIBLE”。

否则，在第一行输出 “POSSIBLE”。 接下来的 $n$ 行应包含 $x_i, y_i$ —— 完全巡游中第 $i$ 个方格的位置。

样例

样例输入 1

1

样例输出 1

POSSIBLE
1 1

样例输入 2

2

样例输出 2

IMPOSSIBLE