[AdditionalFile5158.zip](file://AdditionalFile5158.zip?type=additional_file)

#5158. 「ROIR 2017 Day 2」大型线性对撞机

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

译自 ROIR 2017 Day2 T2. Большой линейный коллайдер

一组科学家在国际科学实验室工作，研究大型线性对撞机（BLC）实验装置中基本粒子的行为。BLC 装置是一条直线，其上某些点放置了可以沿直线移动的粒子。

在一次实验中，BLC 中放置了 $n$ 个粒子，每个粒子要么是带负电的电子 $e^{-}$，要么是带正电的正电子 $e^{+}$。实验中，第 $i$ 个粒子初始放置在坐标为 $x_i$ 的点上。实验开始后，由于 BLC 的作用，粒子将开始沿直线向不同方向移动：$e^{-}$ 粒子向坐标减小的方向移动，$e^{+}$ 粒子向坐标增大的方向移动。所有粒子的速度绝对值相同，均为 $1$。

在移动过程中，如果 $e^{-}$ 和 $e^{+}$ 粒子到达同一点，它们会相互作用并同时消失，且不会对其他粒子的后续行为产生影响。

科学家选择了 $m$ 个不同的时间点 $t_1, t_2, \ldots, t_m$，对于每个时间点，他们希望知道在该时间点之后 BLC 中剩余的粒子数量。时间从 $0$ 时刻开始计算，即粒子开始移动的时刻。在时间点 $t_j$ 因相互作用而消失的粒子不应计入该时间点的粒子数量。

你的任务是编写一个程序，根据粒子初始位置和类型描述，以及给定的时间点，确定每个时间点之后 BLC 中剩余的粒子数量。

输入格式

输入文件的第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$，表示粒子数量。接下来的 $n$ 行描述粒子，每行包含两个整数 $x_i$ 和 $v_i$（$-10^{9} \leq x_1 < x_2 < \ldots < x_n \leq 10^{9}$，$v_i$ 为 $-1$ 或 $1$），分别表示第 $i$ 个粒子的坐标和类型。$e^{-}$ 粒子由 $v_i = -1$ 表示，$e^{+}$ 粒子由 $v_i = 1$ 表示。

下一行包含一个整数 $m$ $(1 \leq m \leq 200000)$，表示科学家选择的时间点数量。最后一行包含 $m$ 个整数 $t_1, t_2, \ldots, t_m$ $(0 \leq t_1 < t_2 < \ldots < t_m \leq 10^{9})$。

输出格式

对于输入文件中的每个时间点，输出一个数字，表示该时间点之后 BLC 中剩余的粒子数量。

样例

输入

4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3

输出

4
2
0
0

在给出的样例中，初始时刻 BLC 中有 $4$ 个粒子：坐标为 $-1$ 的 $e^{+}$ 粒子，坐标为 $0$ 的 $e^{-}$ 粒子，坐标为 $1$ 的 $e^{+}$ 粒子，以及坐标为 $5$ 的 $e^{-}$ 粒子。

在时间 $0.5$ 时刻，第一个 $e^{+}$ 粒子和第一个 $e^{-}$ 粒子在坐标为 $-0.5$ 的点碰撞并消失。在时间 $1$ 时刻，剩余的两个粒子分别位于坐标 $2$ 和 $4$。在时间 $2$ 时刻，它们在坐标 $3$ 处碰撞并消失。此后 BLC 中不再有粒子。

数据范围与提示

详细子任务附加限制及分值如下表所示：