众所周知，寻找图的色数是一个 NPC 问题。然而，小 tarjen 声称他可以用一个简单的贪心算法解决这个问题：

按 $1$ 到 $n$ 的顺序为顶点着色。对于每个顶点 $u$，将 $\{col_v \mid v < u, (v, u) \in E\}$ 的最小排斥（MEX）正整数赋值给 $col_u$，其中 $E$ 是图的边集。例如，$\text{MEX}(\{1, 1, 2, 4\}) = 3$，$\text{MEX}(\emptyset) = 1$。

你需要证明这个贪心算法是完全错误的。请构造一个图，使得你可以用 $c$ 种颜色为该图着色，但贪心算法会使用至少 $c + k$ 种颜色为该图着色。

输入格式

仅一行，包含一个整数 $k$ ($1 \le k \le 500$)。

输出格式

第一行包含三个整数 $n, m, c$ ($1 \le n \le 1024, 0 \le m \le \frac{n(n-1)}{2}, 1 \le c \le n$)，分别表示顶点数、边数以及你可以用来为该图着色的颜色数量。

下一行包含 $n$ 个整数 $col_1, col_2 \dots col_n$ ($1 \le col_i \le c$)，表示你的着色方案。

接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v, col_u \neq col_v$)，表示图中的一条边。

如果存在多种解，输出任意一种即可。

样例

样例输入 1

1

样例输出 1

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