400473: GYM100187 M Heaviside Function

Heaviside function is defined as the piecewise constant function whose value is zero for negative argument and one for non-negative argument:

You are given the function f(x) = θ(s_1x - a₁) + θ(s_2x - a₂) + ... + θ(s_nx - a_n), where s_i =  ± 1. Calculate its values for argument values x₁, x₂, ..., x_m.

The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of the summands in the function.

Each of the next n lines contains two integers separated by space — s_i and a_i (s_i =  ± 1,  - 10⁹ ≤ a_i ≤ 10⁹) — parameters of the i-th summand.

The next line contains a single integer m (1 ≤ m ≤ 200000) — the number of the argument values you should calculate the value of the function for.

The last line contains m integers x₁, ..., x_m ( - 10⁹ ≤ x_i ≤ 10⁹) separated by spaces — the argument values themselves.

Output m lines. i-th line should contain the value of f(x_i).

6
1 3
-1 2
1 9
-1 2
1 7
-1 2
8
0 12 2 8 4 -3 7 9

0
3
0
2
1
3
2
3