题目描述

给定一个整数 $L$。请构造一个满足以下条件的有向图。构造出的图中可以包含重边。可以证明，必定存在满足条件的有向图。

• 顶点数 $N$ 不超过 $20$，所有顶点编号为 $1$ 到 $N$ 的不同整数。
• 边数 $M$ 不超过 $60$，所有边的长度为 $0$ 到 $10^6$ 之间的整数。
• 所有边都从编号较小的顶点指向编号较大的顶点。也就是说，$1,2,\ldots,N$ 是该图顶点的一个拓扑序。
• 从顶点 $1$ 到顶点 $N$ 的不同路径恰好有 $L$ 条，并且这些路径的长度分别为 $0$ 到 $L-1$ 的不同整数。

这里，路径的长度指的是路径上所有边的长度之和。两条路径不同，指的是它们经过的边集合不同。

输入格式

输入从标准输入读入，格式如下：

$L$

输出格式

第一行输出你构造的图的顶点数 $N$ 和边数 $M$。接下来的 $M$ 行中，第 $i$ 行输出三个整数 $u_i, v_i, w_i$，分别表示第 $i$ 条边的起点、终点和长度。若有多种合法解，输出任意一种均可。

样例 1

输入

4

输出

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

输入

5

输出

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$ 有 $4$ 条路径：

• 路径 $1 \to 2 \to 3 \to 4 \to 8$ 的长度为 $0$
• 路径 $1 \to 2 \to 3 \to 7 \to 8$ 的长度为 $1$
• 路径 $1 \to 2 \to 6 \to 7 \to 8$ 的长度为 $2$
• 路径 $1 \to 5 \to 6 \to 7 \to 8$ 的长度为 $3$

除此之外，也存在其他可被接受的输出。

由 ChatGPT 4.1 翻译