暂无测试数据。

小 A 收到了一份礼物，一个长度为 $n$ 的二元组序列 $(x,y)$。

小 A 特别喜欢这个序列，所以他想知道关于这个序列的一切信息。

小 A 定义在一个二元组集合 $S$ 中，一个二元组 $(a,b)$ 被称为优秀的，当且仅当集合中不存在另一个二元组 $(x,y)$，满足 $x \ge a$ 且 $y \ge b$。 只有一个元素的二元组集合 $\{(x,y)\}$，$(x,y)$ 被视作优秀的。

现在小 A 提出了 $q$ 个问题，每个问题形如 “在 $[l,r]$ 区间构成的二元组集合中，有哪些二元组是优秀的”。你需要回答小 A 的问题。

注意常数因子在程序效率方面的影响。

输入格式

输入第一行一个整数 $n$，表示二元组序列的长度。

接下来 $n$ 行，每行两个数 $(x,y)$ 表示二元组序列中的一个元素。

接下来一行一个整数 $q$，表示询问个数。

接下来 $q$ 行，每行两个数表示询问 $[l,r]$，满足 $l \le r$。

输出格式

为了证明你真的知道是哪些二元组，对于每个询问，请你输出所有优秀二元组 $(x,y)$ 的 $x$ 异或 $y$ 的 乘积 模 $10^9+7$ 的值。

数据范围

对于 $30\%$ 的数据: $1 \le n,q \le 100$。

对于 $60\%$ 的数据: $1 \le n,q \le 100000$。

对于 $100\%$ 的数据: $1 \le n \le 200000$, $1 \le q \le 400000$，$1 \le x,y \le 10^9$。我们保证所有的二元组都是随机的，但是询问的区间并不保证随机。我们不保证所有的二元组都是两两不同的。

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

4
24