Type: Default 1000ms 256MiB

线段

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

数轴上有 nn 条线段,第 ii 条线段的左端点是 a[i]a[i],右端点是 b[i]b[i]

Bob 发现 12n1-2n2n2n 个整数点,每个点都是某条线段的端点。

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

1 x y,表示第 xx 条线段和第 yy 条线段相交(相交在这里指至少有一个公共点)。

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

共有 mm 个特点,每个特点都是如上两类之一。

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

Format

Input

第一行两个正整数 n,mn , m

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

Output

输出 nn 行,第 ii 行两个正整数,用空格隔开,分别是 a[i]a[i]b[i]b[i]

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

如果无解输出“Wrong”(不输出引号) 。

Samples

3 1
1 2 3
1 2
3 5
4 6

Limitation

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

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

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

暑期模拟赛 一

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2024-7-11 8:30
End at
2024-7-11 12:00
Duration
3.5 hour(s)
Host
Partic.
9