考虑平面上一组 $n$ 条垂直线段 $S$（线段包含其端点）。$S$ 中的任意两个元素都没有公共点。如果存在一条水平线段连接两条垂直线段，且该水平线段与 $S$ 中的其他线段没有公共点，则称这两条线段“互相可见”。

在下图中，展示了一组线段的示例。互相可见的线段对有：1-2、1-3、2-3、1-5 和 4-5。线段 1 和 4 互相不可见。

对于给定的数字 $n$，我们需要寻找一组包含 $n$ 条垂直线段的集合 $S$，使得互相可见的线段对数量尽可能多。

编写一个程序：

• 从标准输入读取数字 $n$；
• 计算 $n$ 条垂直线段的位置，使得：
  • 它们之间没有公共点；
  • 互相可见的线段对数量尽可能多；
• 将答案写入标准输出。

输入格式

标准输入的第一行也是唯一一行包含一个整数 $n$ ($1 \le n \le 20\,000$)。

输出格式

输出的第一行应包含一个整数，即互相可见的线段对的最大数量。接下来的 $n$ 行，每行应标识一条线段的坐标。第 $i+1$ 行（对于 $i = 1, 2, \ldots, n$）包含三个整数：$x_{i}$、$d_{i}$ 和 $g_{i}$ ($0 \le x_{i} \le 1\,000\,000\,000$，$0 \le d_{i} < g_{i} \le 1\,000\,000\,000$)，以空格分隔。它们表示连接点 $(x_{i}, d_{i})$ 和 $(x_{i}, g_{i})$ 的线段。

如果存在多种满足条件的 $n$ 条线段的排列方式，程序可以输出其中任意一种。

样例

输入 1

4

输出 1

6
1 1 5
2 2 4
3 3 5
4 1 4