有 n 个区间 [Li,Ri],然后有 m 次切割操作,每次操作由三元组 (x,l,r) 描述,对 i∈[l,r] 进行如下操作:
- 如果 x∉[Li,Ri],什么都不做。
- 否则区间 i 将被切割为 [Li,x] 和 [x,Ri] 两段,用较长的一段作为新的区间 i,如果长度相等选择 [Li,x]。
求出每个区间在所有操作后的左右端点。为了简化问题,保证所有 x 构成 1∼m 的排列。
输入格式
第一行包含三个整数 n,m,id (1≤n≤105,1≤m≤106,0≤id≤7),其中 id 表示子任务编号,样例中 id=0。
接下来 n 行,每行包含两个整数 Li,Ri (1≤Li<Ri≤m),表示区间 i 的左右端点。
接下来 m 行,每行包含三个整数 x,l,r (1≤x≤m,1≤l≤r≤n),表示一次切割操作。保证所有 x 构成 1∼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≤n≤105,1≤m≤106
1≤Li<Ri≤m,1≤x≤m,1≤l≤r≤n,保证所有 x 构成 1∼m 的排列。
子任务 | 分值 | n≤ | m≤ | 特殊性质 |
---|---|---|---|---|
1 | 5 | 5000 | 5000 | |
2 | 15 | 16000 | 2×105 | AB |
3 | 15 | 105 | 106 | A |
4 | 15 | 16000 | 2×105 | B |
5 | 10 | 105 | 106 | B |
6 | 20 | 16000 | 2×105 | |
7 | 20 | 105 | 106 |
特殊性质 A:所有 x 构成 1∼m 的随机排列。
特殊性质 B:每次操作的 l=1,r=n。