题目描述

给定一个整数 $L$。构造一个满足以下条件的有向图。图中可能存在相同顶点对之间的多条边。可以证明这样的图总是存在的。

• 顶点的数量 $N$ 最多为 $20$，顶点从 $1$ 到 $N$ 给出 ID 编号。
• 边的数量 $M$ 最多为 $60$。每条边的长度为 $0$ 到 $10^6$ 的整数（包括边界值）。
• 每条边的方向都是从较小的顶点到较大的顶点。也就是说，$1,2,...,N$ 是顶点的一种可能的拓扑排序。
• 从顶点 $1$ 到顶点 $N$ 恰好存在 $L$ 条不同的路径。这些路径的长度都不相同，并且它们的长度是从 $0$ 到 $L-1$ 的整数。

这里，路径的长度是路径中包含的边的长度之和，当路径中包含的边的集合不同时，两条路径被认为是不同的。

约束条件

• $2 \leq L \leq 10^6$
• $L$ 是一个整数。

输入格式

从标准输入中按以下格式给出输入：

$L$

输出格式

在第一行中打印 $N$ 和 $M$，表示你的图中的顶点和边的数量。在接下来的 $M$ 行中，按顺序打印三个整数 $u_i,v_i$ 和 $w_i$，表示第 $i$ 条边的起始顶点、结束顶点和长度。如果有多个解，任意一个都将被接受。

示例输入 1

4

示例输出 1

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

在示例输出所代表的图中，从顶点 $1$ 到 $N=8$ 有四条路径：

• $1$ → $2$ → $3$ → $4$ → $8$，长度为 $0$
• $1$ → $2$ → $3$ → $7$ → $8$，长度为 $1$
• $1$ → $2$ → $6$ → $7$ → $8$，长度为 $2$
• $1$ → $5$ → $6$ → $7$ → $8$，长度为 $3$

还有其他可能的解。

示例输入 2

5

示例输出 2

5 7
1 2 0
2 3 1
3 4 0
4 5 0
2 4 0
1 3 3
3 5 1