问题描述

公司D将迎来成立80周年纪念，为此决定在办公室前面装饰一个图形。
该图形需要满足以下条件：

• 它是一幅有向加权图。
• 它有N个顶点和M条边，顶点从1到N编号。
• N ≤ 70。
• 第i条边是从顶点$u_i$到顶点$v_i$的有向边，权重为$w_i$，满足$u_i < v_i, 0 ≤ w_i ≤ 2,000$（其中$w_i$为整数），并且当$i \neq j$时，$(u_i, v_i) \neq (u_j, v_j)$。
• 从顶点1到N的任何路径的长度都是$p_1, p_2, p_3, ..., p_Q$中的某一个值。其中路径长度指的是该路径上所有边的权重之和。
• 从顶点1到N的路径中，长度为$p_1$的路径至少有1条，长度为$p_2$的路径至少有1条，长度为$p_3$的路径至少有1条，..., 长度为$p_Q$的路径至少有1条。

请构建一幅满足以上条件的图形。
顶点数越少，装饰的费用就越低，因此总经理也会很高兴。

约束条件

• $1 ≤ Q ≤ 2,000$
• $1 ≤ p_1 < p_2 < p_3 < ... < p_Q ≤ 2,000$
• 所有输入值都是整数

得分

得分根据以下计算方法确定：

• 如果有任何一个测试用例不正确，则得分为0分。
• 如果所有测试用例都正确，使用最大的N值作为L，则得分根据以下规则确定：
  • 当$66 ≤ L ≤ 70$时，得分为600分。
  • 当$61 ≤ L ≤ 65$时，得分为800分。
  • 当$54 ≤ L ≤ 60$时，得分为$990 + 30 \times (60 - L)$分。
  • 当$L ≤ 53$时，得分为1200分。

注意，在该问题的约束条件下，可以证明对于任意输入，总会存在满足条件的图形使得$N ≤ 53$。

输入

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

$Q$

$p_1$ $p_2$ $p_3$ $...$ $p_Q$

输出

以以下格式输出满足条件的一幅图形。

$N$ $M$

$u_1$ $v_1$ $w_1$

$u_2$ $v_2$ $w_2$

$u_3$ $v_3$ $w_3$

...

$u_M$ $v_M$ $w_M$

如果存在多个满足条件的图形，输出其中任意一个即可。

示例1

3
1 2 5

输出示例1

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

这个输出对应以下图形：

从顶点1到N=5的路径有以下3条：

• $1$ → $2$ → $5$：长度为$1 + 0 = 1$
• $1$ → $3$ → $5$：长度为$2 + 0 = 2$
• $1$ → $4$ → $5$：长度为$5 + 0 = 5$

以上路径满足$Q = 3, p_1 = 1, p_2 = 2, p_3 = 5$的条件。除此之外，例如以下输出也是正确的解答：

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

示例2

4
1 2 3 4

输出示例2

5 10
1 2 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1
3 4 1
3 5 1
4 5 1

示例3

7
1 3 7 9 11 14 16

输出示例3

8 15
1 2 1
1 3 2
1 4 3
5 8 0
6 8 0
7 8 0
2 5 0
2 6 2
2 7 6
3 5 7
3 6 9
3 7 12
4 5 13
4 6 8
4 7 6