给定一个长度为 $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)$ 定义为从顶点 $i$ 到顶点 $j$ 所需经过的最少边数。

请构造一个具有 $N$ 个顶点和 $M$ 条边的简单连通无向图 $G$，使得代价最小。

输入格式

输入通过标准输入按以下格式给出：

$N \ M$ $X_1 \ X_2 \ \dots \ X_{N-1}$

输出格式

若图中的第 $i$ 条边连接顶点 $A_i$ 和 $B_i$，请输出 $M$ 行，格式如下：

$A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_M \ B_M$

数据范围

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

样例输入 2

4 6
12 34 56

样例输出 2

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

说明

对于第一个样例： 在该输出中，代价为 $X_{d(1,2)} + X_{d(1,3)} + X_{d(2,3)} = X_1 + X_1 + X_2 = 13$。 由于不存在代价小于或等于 $12$ 的 $3$ 个顶点且有 $2$ 条边的无向图，因此该输出是正确的。