Problem Description

D Company, which will celebrate its 80th anniversary next year, has decided to decorate a graph in front of their office as a commemoration.
This graph must meet the following conditions:

• It is a weighted directed graph.
• The number of vertices is $ N $ and the number of edges is $ M $. The vertices are numbered $ 1, 2, 3, ..., N $.
• $N \leq 70$.
• The $ i $-th edge is a directed edge with weight $ w_i $ from vertex $ u_i $ to $ v_i $. $ u_i < v_i $, $0 \leq w_i \leq 2,000$ (where $ w_i $ is an integer). Also, $(u_i, v_i) \neq (u_j, v_j)$ if $i \neq j$.
• The length of any path from vertex $ 1 $ to $ N $ is one of $ p_1, p_2, p_3, ..., p_Q $. The length of a path is the sum of the weights of the edges included in that path.
• There is at least one path from vertex $ 1 $ to $ N $ with length exactly $ p_1 $, at least one with length exactly $ p_2 $, at least one with length exactly $ p_3 $, ..., and at least one with length exactly $ p_Q $.

Construct one such graph.
The fewer vertices, the less the decoration costs, which will please the president.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output one graph that satisfies the conditions in the following format:

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

If multiple graphs satisfy the conditions, any of them can be output as correct.

Sample Input and Output

Sample Input #1

3
1 2 5

Sample Output #1

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

Sample Input #2

4
1 2 3 4

Sample Output #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

Sample Input #3

7
1 3 7 9 11 14 16

Sample Output #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

Notes/Hints

Constraints

• $1 \leq Q \leq 2,000$
• $1 \leq p_1 < p_2 < p_3 < ... < p_Q \leq 2,000$
• All input values are integers.

Scoring

The score for a submission is calculated as follows:

• If any test case is incorrect, the score for that submission is $ 0 $.
• If all test cases are correct, let $ L $ be the maximum value of $ N $ used for those test cases. The score is determined as follows:
• If $66 \leq L \leq 70$, the score is $ 600 $.
• If $61 \leq L \leq 65$, the score is $ 800 $.
• If $54 \leq L \leq 60$, the score is $990 + 30 \times (60 - L)$.
• If $L \leq 53$, the score is $ 1,200 $.

It can be proven that under the constraints of this problem, there always exists a graph satisfying the conditions with $N \leq 53$ for any input.

Sample Explanation 1

This output corresponds to the following graph: The paths from vertex $ 1 $ to $ N = 5 $ are as follows: - $ 1 $ → $ 2 $ → $ 5 $: length $ 1 + 0 = 1 $ - $ 1 $ → $ 3 $ → $ 5 $: length $ 2 + 0 = 2 $ - $ 1 $ → $ 4 $ → $ 5 $: length $ 5 + 0 = 5 $ These satisfy the conditions in the problem statement for $ Q = 3, p_1 = 1, p_2 = 2, p_3 = 5 $. Other outputs, such as the following, are also correct: 4 6 1 2 1 1 3 4 1 4 1 2 3 3 2 4 1 3 4 1

见题面 Input 部分

见题面 Output 部分