考虑一个二维网格，上面有 $n$ 条垂直线段。有两个观察者，一个在西，一个在东，他们站在 X 轴上距离线段无限远的点上。

每位观察者都拥有某种非负整数等级的 X 射线视觉，这使他们能够看穿线段。如果观察者与线段上某一点之间的直线上没有超过 $p$ 条其他线段，那么该观察者就能以等级 $p$ 的视觉看到该点。如果线段的某一部分没有被任何观察者看到，我们就称其为不可见的。

给定 $q$ 次查询。每次查询包含两个整数：分别表示西侧观察者和东侧观察者的视觉等级。对于每次查询，你需要确定所有线段上不可见部分的长度总和。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示线段的数量。

接下来的 $n$ 行，第 $i$ 行包含三个整数 $x_i, a_i$ 和 $b_i$ ($1 \le x_i \le 10^9, 1 \le a_i < b_i \le 10^9$)，描述了第 $i$ 条线段的位置：其端点坐标为 $(x_i, a_i)$ 和 $(x_i, b_i)$。保证每条线段的长度均为正，且没有两条线段共享公共点。

下一行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示查询的数量。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$ ($0 \le l \le r \le 10^5$)，分别表示该次查询中西侧和东侧观察者的视觉等级。

输出格式

输出 $q$ 行，每行一个整数，表示对应查询的答案。

样例

样例输入 1

6
1 1 5
2 1 2
3 1 3
4 2 6
5 3 4
6 4 7
4
0 0
1 1
0 1
1 0

样例输出 1

4
0
0
0

说明

在第一次查询中，西侧观察者完全看到了第一条线段、第四条线段在 Y 坐标 $[5, 6]$ 处的部分，以及第六条线段在 Y 坐标 $[6, 7]$ 处的部分。

东侧观察者完全看到了第五条和第六条线段、第四条线段在 Y 坐标 $[2, 3]$ 处的部分，以及第三条线段在 Y 坐标 $[1, 2]$ 处的部分。

保持不可见的部分为：完整的第二条线段、第三条线段在 Y 坐标 $[2, 3]$ 处的部分，以及第四条线段在 Y 坐标 $[3, 5]$ 处的部分。它们的总长度为 $1 + 1 + 2 = 4$。

在所有其他查询中，没有不可见的部分。