题目描述

You are given an integer $L$. Construct a directed graph that satisfies the conditions below. The graph may contain multiple edges between the same pair of vertices. It can be proved that such a graph always exists.

• The number of vertices, $N$, is at most $20$. The vertices are given ID numbers from $1$ to $N$.
• The number of edges, $M$, is at most $60$. Each edge has an integer length between $0$ and $10^6$ (inclusive).
• Every edge is directed from the vertex with the smaller ID to the vertex with the larger ID. That is, $1,2,...,N$ is one possible topological order of the vertices.
• There are exactly $L$ different paths from Vertex $1$ to Vertex $N$. The lengths of these paths are all different, and they are integers between $0$ and $L-1$.

Here, the length of a path is the sum of the lengths of the edges contained in that path, and two paths are considered different when the sets of the edges contained in those paths are different.

给你一个整数 $L$ 。请构建一个满足以下条件的有向图。该图可能包含同一对顶点之间的多条边。可以证明这样的图总是存在的。

• 顶点数 $N$ 最多为 $20$ 。顶点的 ID 号从 $1$ 到 $N$ 。
• 边的数量 $M$ 最多为 $60$ 。每条边的整数长度在 $0$ 和 $10^6$ 之间（含）。
• 每条边都从 ID 较小的顶点指向 ID 较大的顶点。也就是说， $1,2,...,N$ 是顶点的一种可能拓扑顺序。
• 从顶点 $1$ 到顶点 $N$ 恰好有 $L$ 条不同的路径。这些路径的长度各不相同，都是介于 $0$ 和 $L-1$ 之间的整数。

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

输入格式

输入内容按以下格式标准输入：

$L$

输出格式

在第一行，打印 $N$ 和 $M$ 图形中的顶点和边的数量。在接下来 $M$ 行的 $i$ /-th 中，打印三个整数 $u_i,v_i$ 和 $w_i$ ，分别代表起始顶点、终止顶点和 $i$ /-th 边的长度。如果有多个解决方案，我们将接受其中任何一个。

样例 #1

样例输入 #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

样例 #2

样例输入 #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

说明

数据规模与约定

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

样例 $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$

还有其他可能的解决方案。