题目描述

给定一个顶点编号为 $0$ 到 $n$ 的有向图 $G$。初始时，$G$ 包含恰好 $n$ 条形如 $v \to v + 1$ 的边。你的任务是向图中添加一些边，使得对于任意两个顶点 $v, u$ ($v < u$)，都存在一条从 $v$ 到 $u$ 且长度不超过三条边的有向路径。你还必须满足以下两个附加要求：

1. 你可以添加一条边 $a \to c$，当且仅当存在某个 $b$，使得边 $a \to b$ 和 $b \to c$ 已经在 $G$ 中。
2. 你总共最多可以添加 $6 \cdot n$ 条边。

交互

交互开始时，交互器会在单行上打印整数 $n$ ($0 \le n \le 2^{16}$)。之后，你的程序应输出 $k$ ($0 \le k \le 6 \cdot n$)：你想要添加到图中的边数。接下来的 $k$ 行应按添加顺序包含所添加边的描述。每条边应由三个整数 $a, b, c$ 描述，表示你添加了边 $a \to c$，且边 $a \to b$ 和 $b \to c$ 已经在 $G$ 中。

在此之后，请务必刷新输出缓冲区（在 C++ 中可以使用 cout << flush;），否则程序将获得“Idleness Limit Exceeded”。

然后，交互器会打印查询次数 $q$ ($0 \le q \le 2 \cdot 10^5$) 以及接下来的 $q$ 行查询。每个查询由两个整数 $\ell, r$ ($0 \le \ell < r \le n$) 描述，你需要输出一行，包含一条在 $G$ 中从顶点 $\ell$ 开始并以顶点 $r$ 结束的长度不超过三的路径。路径应打印为它访问的所有顶点（包括两个端点）的序列，并用空格分隔。

为了获取下一个查询，你的程序必须打印上一个查询的答案，以换行符结束，并刷新输出缓冲区。查询结果取决于你所添加的边。

在下方的样例中，输入和输出中没有实际的空行：它们仅用于视觉上对齐输入和对应的输出。

样例

输入格式 1

9

输出格式 1

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