有 $ 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 $ 的排列。
| 子任务 | 分值 | $ n\le $ | $ m\le $ | 特殊性质 |
|---|---|---|---|---|
| 1 | 5 | $ 5000 $ | $ 5000 $ | |
| 2 | 15 | $ 16000 $ | $ 2\times 10^5 $ | AB |
| 3 | 15 | $ 10^5 $ | $ 10^6 $ | A |
| 4 | 15 | $ 16000 $ | $ 2\times 10^5 $ | B |
| 5 | 10 | $ 10^5 $ | $ 10^6 $ | B |
| 6 | 20 | $ 16000 $ | $ 2\times 10^5 $ | |
| 7 | 20 | $ 10^5 $ | $ 10^6 $ |
特殊性质 $ A $：所有 $ x $ 构成 $ 1\sim m $ 的随机排列。
特殊性质 $ B $：每次操作的 $ l=1,r=n $。