题目描述

Deni 的日程非常繁忙，她把每天的安排精确到了毫秒。

每天共有 $N$ 个活动。对于编号为 $i$ 的活动（$0 \le i \le N-1$），它占用的时间段是从第 $L_i$ 毫秒到第 $R_i$ 毫秒（含端点）。

在任意一个毫秒时刻，Deni 最多只能做一项活动；如果这个时刻不属于任何允许的活动区间，她就休息。

接下来会有 $D$ 天的限制安排。
在第 $j$ 天（$0 \le j \le D-1$），她只被允许做编号在 $X_j$ 到 $Y_j$ 之间（含端点）的活动。

Deni 是个工作狂，所以只要某一毫秒落在任意一个被允许活动的时间区间内，她就会在这毫秒工作。她可以随时切换活动，甚至可以重新开始做某项更早时刻安排的活动；因此对于某一天而言，真正重要的只是这些被允许区间的并集长度。

请你对于每一天，求出 Deni 会忙碌多少毫秒。

你需要实现程序 freetime。

实现要求

你需要实现函数：

std::vector<int> solve(
    std::vector<int> L, std::vector<int> R,
    std::vector<int> X, std::vector<int> Y
)

其中：

• L 和 R：长度为 $N$ 的数组，第 $i$ 个活动的时间区间为 $[L_i, R_i]$；
• X 和 Y：长度为 $D$ 的数组，第 $j$ 天只允许活动编号落在区间 $[X_j, Y_j]$ 内。

函数需要返回一个长度为 $D$ 的数组。
返回值中第 $j$ 个数应为：在第 $j$ 天里，所有允许活动区间的并集中包含的毫秒数。

限制

• $1 \le N \le 5 \times 10^5$
• 对所有 $0 \le i \le N-1$，有 $1 \le L_i \le R_i \le 10^6$
• $1 \le D \le 5 \times 10^5$
• 对所有 $0 \le j \le D-1$，有 $0 \le X_j \le Y_j \le N-1$

子任务

注：原 PDF 表格在文本提取时有轻微错位，上表按可辨识内容整理。

样例

输入

5
1 5
2 7
9 11
5 10
2 4
15
0 0
0 1
0 2
0 3
0 4
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

输出

5
7
10
11
11
6
9
10
10
3
7
10
6
9
3

说明

共有 5 个活动区间：

• $[1,5]$
• $[2,7]$
• $[9,11]$
• $[5,10]$
• $[2,4]$

例如：

• 查询 $(0,2)$ 表示只允许编号 $0,1,2$ 的活动，对应区间并集为 $[1,7]\cup[9,11]$，总长度为 $7+3=10$；
• 查询 $(0,3)$ 对应区间并集为 $[1,11]$，总长度为 $11$；
• 查询 $(4,4)$ 只保留区间 $[2,4]$，总长度为 $3$。