问题陈述
N 顾客参观了一家咖啡馆:顾客 1,客户 2, \ldots和客户 N.
对于 i = 1, 2, \ldots, N,客户 i 在咖啡馆呆了好久 A_i 到时间 B_i (包括时间 A_i 和时间 B_i).
除这些客户外没有其他客户 N 参观了咖啡馆。
对于每个 Q 次 t_1, t_2, \ldots, t_Q, 找出当时留在咖啡馆的顾客数量。
约束
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq A_i \lt B_i \leq 10^9
- 1 \leq t_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 \vdots A_N B_N Q t_1 t_2 \vdots t_Q
输出
打印 Q 行。 对于 i = 1, 2, \ldots, Q, i- 第行应包含当时留在咖啡馆的顾客数量 t_i.
示例输入 1
4 2 4 4 5 3 6 4 5 7 1 2 3 4 5 6 7
示例输出 1
0 1 2 4 3 1 0
- 时间 1,咖啡馆里没有人。
- 时间 2,咖啡馆里有一位顾客:顾客 1.
- 时间 3,咖啡馆里有两个顾客:顾客 1 和 3.
- 时间 4,咖啡馆里有四位顾客:顾客 1, 2, 3,和 4.
- 时间 5,咖啡馆里有三名顾客:顾客 2, 3,和 4.
- 时间 6,咖啡馆里有一位顾客:顾客 3.
- 时间 7,咖啡馆里没有人。
示例输入 2
1 1 1000000000 2 1000000000 1
示例输出 2
1 1