ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Summer 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Space Tourism

Time limit: 2.0 second
Memory limit: 64 MB
There are n planets in Betelgeuse star system. Each planet is inhabited by a single race, different planets can be inhabited by the same race. All planets move in circular orbits, lie on a single ray starting at the star and have same constant angular velocity. Tourists from other galaxies often ask the Ministry of Space Tourism to help them plan their journey. They would like to be escorted to a planet, from which they can start their individual journey on their own small spaceship.
Spaceships of all the tourists are equipped with a small fuel tank, which allows to cover at most d astronomical units without reloading. Such a reloading can be made on any planet of the system. Moreover, each ship can operate only in a fixed range of distances to the star, where he can use the radiation energy. A tourist can be escorted to a planet only if the distance from this planet to the star fall into this range.
The Ministry ordered you to calculate the maximal number of races each tourist can come in contact with.


The first line contains space-separated integers n, s and d (1 ≤ n, s, d ≤ 105), which are the number of planets in Betelgeuse star system, the number of known races and the maximal distance each ship can fly without reloading, respectively. Each of the next n lines describes a planet and contains two space-separated positive integers which are a distance from this planet to the star and a number of race which lives on this planet, respectively. Races are numbered with integers from 1 to s. The distances from planets to Betelgeuse are all different and don't exceed 106 astronomical units. The next line contains a number of tourists m (1 ≤ m ≤ 105). Each of the next m lines contains two space-separated positive integers, which are the minimal and the maximal possible distance to the star at which the ship of the tourist can operate in. These distances doesn't exceed 106.


For each tourist, you should output the maximal number of races he can come in contact with.


5 5 11
10 1
50 2
30 1
20 1
60 3
5 65
15 45
Problem Author: Dmitry Ivankov
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2010
To submit the solution for this problem go to the Problem set: 1850. Space Tourism