J. 传送
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

你有一个数轴，数轴上有 $$$n$$$ 个点，它们的坐标依次为 $$$1, 2, \dots, n$$$。

数轴上被施加了 $$$m$$$ 个传送魔法，第 $$$i$$$ 个传送魔法可表为 $$$a_i, b_i, c_i, d_i$$$，表示该魔法可以在坐标 $$$[a_i, b_i]$$$ 范围内的任意点使用，从而任意指定 $$$[c_i, d_i]$$$ 范围内的点并传送到那里。所有传送魔法均满足 $$$[a_i, b_i] \subseteq [c_i, d_i] \subseteq [1, n]$$$；

你现在需要对于 $$$i = 1, 2, \dots, n$$$ 分别求解：从坐标为 $$$i$$$ 的点出发，任意顺序、任意次数地使用任意魔法，可以到达的点的最小坐标和最大坐标。

Input

第一行输入整数 $$$T\ (1 \le T \le 10^5)$$$，表示数据组数。

对于每组数据，第一行输入两个整数 $$$n, m(1 \le n \le 10^5, 0 \le m \le 10^5)$$$，表示坐标范围和传送魔法个数。

随后 $$$m$$$ 行，每行包含四个整数 $$$a_i, b_i, c_i, d_i$$$ ，保证 $$$[a_i, b_i] \subseteq [c_i, d_i] \subseteq [1, n]$$$，表示第 $$$i$$$ 个传送魔法可以在坐标 $$$[a_i, b_i]$$$ 范围内使用，传送到 $$$[c_i, d_i]$$$ 范围内的点。

保证 $$$T$$$ 组数据的 $$$\sum{n}, \sum{m}$$$ 均小于 $$$10^5$$$。

Output

对于每组数据，输出 $$$n$$$ 行，每行包含以空格间隔的两个数 $$$l_i, r_i$$$，分别表示坐标为 $$$i$$$ 的点可以到达的最小坐标和最大坐标。

Example
Input
2
4 0
4 2
1 1 1 3
3 3 1 4
Output
1 1
2 2
3 3
4 4
1 4
2 2
1 4
4 4