問題文

長さ N-1 の広義単調増加である正整数列 X=(X_1,X_2,\dots,X_{N-1}) が与えられます。

N 頂点 M 辺単純連結無向グラフ G のコストを \sum_{i=1}^{N} \sum_{j=i+1}^{N} X_{d(i,j)} と定義します。ただし、d(i,j) は G 上で頂点 i から頂点 j へ移動するまでに通る辺の本数としてあり得る最小値として定義します。

コストが最小になる N 頂点 M 辺単純連結無向グラフ G を 1 個構築してください。

制約

• 2 \le N \le 100
• N-1 \le M \le \frac{N(N-1)}{2}
• 1 \le X_1 \le X_2 \le \dots \le X_{N-1} \le 10^9

入力例 1

3 2
4 5

出力例 1

1 2
1 3

この出力の場合、コストは X_{d(1,2)} + X_{d(1,3)} + X_{d(2,3)} = X_1 + X_1 + X_2 = 13 となります。

コストが 12 以下になる 3 頂点 2 辺無向グラフは存在しないため、この出力は正答です。

入力例 2

4 6
12 34 56

出力例 2

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