有 $n$ 个区间 $[L_i,R_i]$，然后有 $m$ 次切割操作，每次操作由三元组 $(x,l,r)$ 描述，对 $i\in [l,r]$ 进行如下操作：

• 如果 $x\not\in [L_i,R_i]$，什么都不做。
• 否则区间 $i$ 将被切割为 $[L_i,x]$ 和 $[x,R_i]$ 两段，用较长的一段作为新的区间 $i$，如果长度相等选择 $[L_i,x]$。

求出每个区间在所有操作后的左右端点。为了简化问题，保证所有 $x$ 构成 $1\sim m$ 的排列。

输入格式

第一行包含三个整数 $n,m,id$ ($1\le n\le 10^5,1\le m\le 10^6,0\le id\le 7$)，其中 $id$ 表示子任务编号，样例中 $id=0$。

接下来 $n$ 行，每行包含两个整数 $L_i,R_i$ ($1\le L_i<R_i\le m$)，表示区间 $i$ 的左右端点。

接下来 $m$ 行，每行包含三个整数 $x,l,r$ ($1\le x\le m,1\le l\le r\le n$)，表示一次切割操作。保证所有 $x$ 构成 $1\sim m$ 的排列。

输出格式

共 $n$ 行，第 $i$ 行包含两个整数表示线段 $i$ 最终的左右端点。

样例输入 #1

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

样例输出 #1

1 2

样例输入 #2

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

样例输出 #2

2 3
4 5
1 4
2 5
2 4

样例输入/输出 #3

ex_cut3.in/out，满足子任务 $2$ 的限制。

样例输入/输出 #4

ex_cut4.in/out，满足子任务 $3$ 的限制。

数据范围

对于全部数据

$1\le n\le 10^5,1\le m\le 10^6$

$1\le L_i<R_i\le m,1\le x\le m,1\le l\le r\le n$，保证所有 $x$ 构成 $1\sim m$ 的排列。

特殊性质 $A$：所有 $x$ 构成 $1\sim m$ 的随机排列。

特殊性质 $B$：每次操作的 $l=1,r=n$。