题目描述

给定一个由编号 $1$ 到 $N$ 的 $N$ 个顶点和 $M$ 条边组成的带权无向简单图 $G$，定义它的森林分数如下。

1. 令 $F_1,F_2,\ldots,F_M$ 均为包含顶点 $1,2,\ldots,N$、但初始没有任何边的图。
2. 将 $G$ 的边按权值从小到大排列为 $e_1,e_2,\ldots,e_M$。依次处理 $i=1,2,\ldots,M$：
   • 找到最小的正整数 $j$，使得把 $e_i$ 加入 $F_j$ 后不会产生环；
   • 将 $e_i$ 加入 $F_j$。
3. 至少包含一条边的 $F_i$ 中，最大的下标 $i$ 称为图 $G$ 的森林分数。

现在给定一个正整数 $k$，请构造一个森林分数恰好为 $k$、且顶点数不超过 $2024$ 的图 $G$。

除此之外，构造还必须满足：

• 若图的顶点数为 $N$，则边数必须恰好为 $2N-2$；
• 可以把其中 $N-1$ 条边染成红色、另外 $N-1$ 条边染成蓝色，使得只保留红边时得到一棵树，只保留蓝边时也得到一棵树。

输入格式

第一行包含一个整数 $k$。

$$2\le k\le 12$$

输出格式

第一行输出图 $G$ 的顶点数 $N$。

$$2\le N\le 2024$$

接下来输出 $2N-2$ 行。第 $i$ 行输出三个整数 $a_i,b_i,c_i$，表示存在一条连接顶点 $a_i$ 与 $b_i$、权值为 $c_i$ 的边。

$$1\le a_i,b_i\le N, \qquad a_i\ne b_i, \qquad 1\le c_i\le 10^9$$

输出必须满足以下条件：

• 所有边的权值两两不同；
• 输出的前 $N-1$ 条边构成一棵树；
• 输出的后 $N-1$ 条边也构成一棵树；
• 任意一对顶点之间至多有一条边；
• 图 $G$ 的森林分数恰好为 $k$。

样例

输入

3

输出

5
1 2 8
2 3 1
3 4 2
4 5 5
1 3 6
3 5 4
5 2 7
2 4 3

样例说明

下面给出了 $k=3$ 时的一组合法答案。

该图可以分成两棵没有公共边的生成树。

按定义计算森林分数时，红、蓝、绿边分别表示被分配到 $F_1,F_2,F_3$ 的边，因此森林分数为 $3$。

本题答案不唯一。部署到在线评测系统时需要使用 SPJ 验证输出图。