题目描述

数轴上有 n 条线段， 第 i 条线段的左端点是 a[i]，右端点是 b[i]。
Bob 发现 1~2n 共 2n 个整数点，每个点都是某条线段的端点。
这些线段有如下两类特点：
1 a b，表示第 a 条线段和第 b 条线段相交
2 a b，表示第 a 条线段在第 b 条线段的左边，且它们不相交。
共有 m 个特点，每个特点都是如上两类之一。
Bob 想通过这些特点推理得到每条线段的端点。

输入

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

输出

输出 n 行， 第 i 行两个正整数， 用空格隔开， 分别是 a[i]和 b[i]
可能有多种答案，输出 字典序最小 的答案。即先要求 a[1]最小，若仍有多解
再要求 b[1] 最小，若仍有多解再要求 a[2]最小，若仍有多解再要求 b[2]最小，若
仍有多解再要求 a[3]最小……
如果无解输出“Wrong”（不输出引号）。

输入样例

3 2
1 2 3
2 1 3

输出样例

1 2
3 5
4 6

样例解释

第二条线段[3,5]与第三条线段[4,6]相交与[3,4]
第一条线段[1,2]在第三条线段[4.6]左边

数据范围

对于 30%的数据， 1<=n,m<=10
对于 60%的数据， 1<=n,m<=1000
对于 100%的数据， 1<=n,m<=100000

限制

时间限制1s,空间限制128m