16330번 - Fishermen 다국어

문제

The ocean can be represented as the first quarter of the Cartesian plane.

There are n fish in the ocean. Each fish has its own coordinates. There may be several fish at one point. There are also m fishermen.

Each fisherman has its own x-coordinate. The y-coordinate of each fisherman is equal to 0.Each fisherman has a fishing rod of length l. Therefore, he can catch a fish at a distance less than or equal to l. The distance between a fisherman in position x and a fish in position (a, b) is |a − x| + b.

Find for each fisherman how many fish he can catch.

입력

The first line contains three integers n, m, and l (1 ≤ n, m ≤ 2 · 10⁵, 1 ≤ l ≤ 10⁹) — the number of fish, the number of fishermen, and the length of the fishing rod, respectively.

Each of the next n lines contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ 10⁹) — the fish coordinates.

Next line contains m integers a_i (1 ≤ a_i ≤ 10⁹) — the fishermen coordinates.

출력

For each fisherman, output the number of fish that he can catch, on a separate line.

제한

힌트

The picture illustrates for the above example the area on which the third fisherman can catch fish.