一个 $d$ 维集合（$d$-dimensional collection）是一个满足以下条件的向量集合：

• 集合中每个向量的每个坐标都是非负整数。
• 若向量 $v = (v_1, \dots, v_d)$ 属于该集合，则对于任意向量 $u = (u_1, \dots, u_d)$，只要 $u$ 的所有坐标均为非负整数且 $u$ 在坐标上不超过 $v$（即对于每个索引 $i \in \{1, \dots, d\}$，均满足 $0 \le u_i \le v_i$），则 $u$ 也必须属于该集合。

例如，$\{(0, 0), (0, 1), (1, 0)\}$ 和 $\{(0, 0), (1, 0), (2, 0), (3, 0)\}$ 是 2 维集合，而 $\{(0, 1), (1, 0), (1, 1)\}$、$\{(0, 0), (-1, 0)\}$ 以及 $\{(0, 0), (0, \frac{1}{2}), (0, 1)\}$ 则不是。

你需要存储两个完全相同的 $d$ 维集合，每个集合的大小均为 $n$。为此，你收集了 $n$ 个相同的 $d$ 维容器，每个容器的容量由容量向量 $c = (c_1, \dots, c_d)$ 给出。你决定为每个集合中的每个向量选择一个容器，使得每个容器恰好包含来自第一个集合的一个向量和来自第二个集合的一个向量。然而，如果两个向量 $v = (v_1, \dots, v_d)$ 和 $u = (u_1, \dots, u_d)$ 被放入同一个容器，必须满足对于每个 $i$，都有 $v_i + u_i \le c_i$；即向量 $v + u$ 在坐标上不能超过容量向量 $c$。

题目保证每个集合中的每个向量单独放入任何容器时都不会超过容量限制；即每个集合中的每个向量 $v$ 在坐标上均不超过容量向量 $c$。

找到一种将所有向量放入容器的方案比较困难，因此你决定编写一个程序来解决这个问题。

输入格式

第一行包含两个空格分隔的正整数 $n$ 和 $d$ ($1 \le n \cdot d \le 10^5$)，分别表示每个集合的大小和维度。

第二行包含 $d$ 个空格分隔的整数 $c_1, \dots, c_d$ ($0 \le c_i \le 10^9$)。

接下来的 $n$ 行包含集合的描述；其中第 $i$ 行包含 $d$ 个空格分隔的整数 $v_{i1}, \dots, v_{id}$ ($0 \le v_{ij} \le 10^9$)，表示集合中第 $i$ 个向量的坐标。保证所描述的向量集合确实符合上述定义的 $d$ 维集合，且满足 $v_{ij} \le c_j$。

输出格式

输出 $n$ 行，每行包含两个空格分隔的整数，分别表示放入第 $i$ 个容器中的第一个集合和第二个集合的向量编号。输入中的向量编号从 1 开始。每个集合中的每个向量都必须恰好被分配到一个容器中。

如果存在多种可能的方案，输出其中任意一种即可。题目保证至少存在一种满足所有要求的方案。

样例

样例输入 1

4 2
1 1
0 0
0 1
1 0
1 1

样例输出 1

1 4
2 3
3 2
4 1

样例输入 2

4 2
2 1
0 0
1 0
2 0
0 1

样例输出 2

1 4
2 2
3 1
4 3