Big Linear Collider

A group of scientists works at an international research laboratory that studies the behavior of elementary particles in the experimental facility "Big Linear Collider" (BLC). The BLC is a straight line, and particles that can move along the line are placed at some of its points.

In the next experiment, n particles are placed in the BLC. Each particle is either a negatively charged particle, an electron e–, or a positively charged particle, a positron e+. In the experiment, the i-th particle is initially placed at the point with coordinate xi. Once the experiment starts, the BLC makes the particles move in opposite directions along the line: e– particles move in the direction of decreasing coordinate, and e+ particles move in the direction of increasing coordinate. The speeds of all particles have the same magnitude, equal to 1.

If an e– particle and an e+ particle end up at the same point while moving, they interact and both disappear, and they do not affect the further behavior of the remaining particles.

The scientists chose m distinct moments of time t1, t2, …, tm, and for each of them they want to know how many particles are in the BLC immediately after that moment. Time is measured from moment 0, when the particles start moving. Particles that disappeared due to an interaction at time tj must not be counted when counting the number of particles for that moment.

You must write a program that, given the initial arrangement and types of the particles and the given moments of time, determines for each moment the number of particles that are in the BLC immediately after that moment.

The first line of the input file contains the number n, the number of particles (1 ≤ n ≤ 200 000). The next n lines describe the particles as follows: each line contains two integers xi and vi, the coordinate of the i-th particle and its type (–109 ≤ x1 < x2 < … < xn ≤ 109, vi is –1 or 1). The particle e– is described by the value vi = –1, and the particle e+ is described by the value vi = 1.

The next line contains the integer m, the number of moments of time chosen by the scientists (1 ≤ m ≤ 200 000). The last line contains m integers: t1, t2, …, tm (0 ≤ t1 < t2 < … < tm ≤ 109).

For each moment of time, output one number: the number of particles in the BLC immediately after that moment.

In the given example, at the initial moment there are 4 particles in the BLC: an e+ particle at point –1, an e– particle at point 0, an e+ particle at point 1, and an e– particle at point 5.

At time 0.5, the first e+ particle and the first e– particle collide at the point with coordinate –0.5 and disappear. At time 1, the two remaining particles are at the points with coordinates 2 and 4, respectively. At time 2, they collide at the point with coordinate 3 and disappear. There are no more particles in the BLC.