题目描述

数轴上有 $n$ 条线段，第 $i$ 条线段的左端点是 $a[i]$，右端点是 $b[i]$。

Bob 发现 $1-2n$ 共 $2n$ 个整数点，每个点都是某条线段的端点。

这些线段有如下两类特点：

1 x y，表示第 $x$ 条线段和第 $y$ 条线段相交（相交在这里指至少有一个公共点）。

2 x y，表示第 $x$ 条线段在第 $y$ 条线段的左边，且它们不相交。

共有 $m$ 个特点，每个特点都是如上两类之一。

Bob 想通过这些特点推理得到每条线段的端点。

输入格式

第一行两个正整数 $n , m$ 。

接下来 $m$ 行，每行三个正整数，描述线段的特点，格式见题目描述。

输出格式

输出 $n$ 行，第 $i$ 行两个正整数，用空格隔开，分别是 $a[i]$和 $b[i]$ 。

可能有多种答案，输出字典序最小的答案。即先要求 $a[1]$最小，若仍有多解再要求 $b[1]$最小，若仍有多解再要求 $a[2]$最小，若仍有多解再要求 $b[2]$最小，若仍有多解再要求 $a[3]$最小……

如果无解输出“Wrong”（不输出引号） 。

样例

input

3 1
1 2 3

output

1 2
3 5
4 6

数据范围与提示

对于 $30\%$ 的数据， $1 \leq n,m \leq 10$

对于 $60\%$ 的数据， $1 \leq n,m \leq 1000$

对于 $100\%$的数据，$1 \leq n,m \leq 100000$