有 $ 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 $。