問題文

来年で設立 80 周年を迎える D 社は、記念としてオフィスの前にグラフを飾ることにしました。
このグラフは、以下の条件を満たす必要があります。

• 重み付き有向グラフである。
• 頂点の数を N、辺の数を M として、頂点は 1, 2, 3, ..., N と番号付けられている。
• N \leq 70 である。
• i 本目の辺が頂点 u_i から v_i への重み w_i の有向辺であるとすると、u_i < v_i, 0 \leq w_i \leq 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 個構築してください。
頂点数が少ないほど、飾りつけにかかる費用が減るので社長も喜ぶでしょう。

制約

• 1 \leq Q \leq 2 \ 000
• 1 \leq p_1 < p_2 < p_3 < ... < p_Q \leq 2 \ 000
• 入力値はすべて整数

得点

提出の得点は、以下のように計算される。

• 一つのテストケースでも不正解であった場合、その提出の得点は 0 点となる。
• すべてのテストケースに正解した場合、それらに対して用いられた N の最大値を L として、提出の得点は以下のように決定される。
  • 66 \leq L \leq 70 のとき、600 点
  • 61 \leq L \leq 65 のとき、800 点
  • 54 \leq L \leq 60 のとき、990 + 30 \times (60 - L) 点
  • L \leq 53 のとき、1200 点

なお、この問題の制約下で、任意の入力に対して N \leq 53 であるような条件を満たすグラフが必ず存在することが証明できる。

入力例 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