我们有 $n$ 张卡片，编号从 $1$ 到 $n$，分布在 $k$ 个栈 $S_1, S_2, \dots, S_k$ 中。每个栈都有容量限制：第 $i$ 个栈 $S_i$ 最多可以容纳 $C_i$ 张卡片。我们唯一的操作方式是取出一个栈顶的卡片，并将其移动到另一个栈的顶部（前提是这不会超过目标栈的容量）。

通过一系列这样的移动，我们希望重新排列这些卡片，使得索引最小的前若干个栈（0 个或更多）被填满，紧随其后的一个栈未被填满（甚至可以为空），而之后的所有栈都完全为空。此外，如果我们把从 $S_1$ 到 $S_k$ 的所有栈按顺序堆叠起来，卡片应该按从小到大的顺序排列，其中 $1$ 在最底部，$n$ 在最顶部。

保证 $n \le (\sum_{i=1}^k C_i) - \max_{1 \le i \le k} C_i$。

假设我们有 $n=6$ 张卡片，分布在 $k=3$ 个栈中，容量分别为 $C_1=4, C_2=C_3=3$，初始状态为：$S_1 = [2, 3, 0, 0]$（从底部到顶部；$0$ 表示空位），$S_2 = [4, 1, 6]$，$S_3 = [5, 0, 0]$。那么期望的最终状态为 $S_1 = [1, 2, 3, 4]$，$S_2 = [5, 6, 0]$，$S_3 = [0, 0, 0]$。

输入格式

第一行包含两个整数 $n$（卡片数量）和 $k$（栈的数量），用空格分隔。接下来的 $k$ 行描述了栈的初始状态；其中第 $i$ 行描述 $S_i$，包含 $C_i + 1$ 个整数，用空格分隔。第一个整数是 $C_i$（栈 $S_i$ 的容量），其余整数是 $S_i$ 上的卡片编号，从底部到顶部。如果栈 $S_i$ 包含的卡片少于 $C_i$ 张（甚至可以为空），则行中最后几个整数将为 $0$。

数据范围

• $1 \le n \le 100$
• $3 \le k \le 100$
• $1 \le C_i \le n$

输出格式

输出一系列移动步骤，将栈调整为期望的最终状态。对于每次移动，输出一行包含两个整数，用空格分隔：第一个整数是移动卡片所在的源栈编号，第二个整数是目标栈编号（栈的编号从 $1$ 到 $k$；目标栈不能与源栈相同）。移动次数不得超过 $10^5$。在移动序列结束后，输出一行包含 “0 0”（不含引号）。如果有多种可能的解，你可以输出其中任意一种。

样例

样例输入 1

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

样例输出 1

2 3
2 3
1 2
1 2
3 1
2 1
2 1
3 2
3 1
2 3
1 3
2 1
3 2
3 2
0 0

说明

这是题目描述中讨论的示例。样例输出展示了将栈调整为期望最终状态的 14 次移动序列。