2856: 小明挫骨扬灰
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
小明收到了一份骨灰盒，还有一个长度为 n 的二元组序列 (x,y)。
小明不知道里面装的是自己的骨灰，所以他想把这个骨灰盒毁灭掉，但必须解决如下问题：
在一个二元组集合 S 中，一个二元组 (a,b) 被称为优秀的，当且仅当集合中不存在另一个二元组 (x,y) 满足 x ≥ a 且 y ≥ b。 若二元组集合只有一个元素，则那个唯一的元素被视作优秀的。
小明不知道里面装的是自己的骨灰，所以他想把这个骨灰盒毁灭掉，但必须解决如下问题：
在一个二元组集合 S 中，一个二元组 (a,b) 被称为优秀的，当且仅当集合中不存在另一个二元组 (x,y) 满足 x ≥ a 且 y ≥ b。 若二元组集合只有一个元素，则那个唯一的元素被视作优秀的。
输入
输入第一行一个整数 n，表示二元组序列的长度。
接下来 n 行，每行两个数 (x,y) 表示二元组序列中的一个元素。
接下来一行一个整数 q，表示询问个数。
接下来 q 行，每行两个数表示询问 [l,r]，满足 l ≤ r。
接下来 n 行，每行两个数 (x,y) 表示二元组序列中的一个元素。
接下来一行一个整数 q，表示询问个数。
接下来 q 行，每行两个数表示询问 [l,r]，满足 l ≤ r。
输出
为了证明你真的知道是哪些二元组，对于每个询问，请你输出所有优秀二元组 (x,y) 的 x 异或 y 的乘积 模 1000000007 的值。
样例输入 复制
3
1 2
1 5
2 4
2
1 2
1 3样例输出 复制
4
24提示
样例解释：
当询问区间 [1,2] 的时候，只有 (1,5) 是优秀的，所以答案为 1 ^ 5 = 4。
当询问区间 [1,3] 的时候，(1,5) 和 (2,4) 是优秀的，所以答案为 (1 ^ 5) × (2 ^ 4) = 4 × 6 = 24。
其中，^ 表示异或运算
数据范围：
1 ≤ n ≤ 200000，1 ≤ q ≤ 400000，1 ≤ x,y ≤ 10^9。
保证所有的二元组都是随机的，但是询问的区间并不保证随机,不保证所有的二元组都是两两不同的。
当询问区间 [1,2] 的时候，只有 (1,5) 是优秀的，所以答案为 1 ^ 5 = 4。
当询问区间 [1,3] 的时候，(1,5) 和 (2,4) 是优秀的，所以答案为 (1 ^ 5) × (2 ^ 4) = 4 × 6 = 24。
其中，^ 表示异或运算
数据范围：
1 ≤ n ≤ 200000，1 ≤ q ≤ 400000，1 ≤ x,y ≤ 10^9。
保证所有的二元组都是随机的，但是询问的区间并不保证随机,不保证所有的二元组都是两两不同的。