В звёздной системе Бетельгейзе n планет. Каждая планета населена некоторой разумной расой, на разных планетах могут обитать одинаковые расы. Все планеты вращаются вокруг Бетельгейзе по круговым орбитам с одинаковой угловой скоростью и лежат на луче, начинающемся из звезды. В министерство космического туризма часто обращаются туристы-одиночки из других галактик, которые хотят, чтобы их вместе с их личным кораблём доставили на какую-нибудь планету, откуда они смогли бы отправиться в путешествие по планетам системы.

Корабли всех туристов снабжены небольшим топливным баком, который позволяет покрыть без дозаправки расстояние не более d астрономических единиц. На любой планете системы можно заправить топливный бак до максимума. Кроме того, для каждого корабля известен диапазон расстояний до звезды, в которых он может нормально функционировать, используя энергию излучения звезды. Туриста можно доставить на планету только в том случае, если расстояние от этой планеты до звезды попадает в данный диапазон.

Министерство поручило вам вычислить для каждого туриста максимальное количество рас, с которыми он сможет установить контакт.

В первой строке через пробел записаны целые числа n, s и d (1 ≤ n, s, d ≤ 10⁵) — количество планет в системе Бетельгейзе, количество известных науке рас и максимальное расстояние, которое могут пролететь корабли туристов без дозаправки. В каждой из следующих n строк через пробел записаны два целых положительных числа — расстояние от очередной планеты системы до звезды и номер расы, населяющей эту планету. Расы занумерованы целыми числами от 1 до s. Расстояния от Бетельгейзе до всех планет различны и не превосходят 10⁶ астрономических единиц. В следующей строке записано целое число m (1 ≤ m ≤ 10⁵) — количество туристов. В каждой из следующих m строк через пробел записаны два целых положительных числа — минимальное и максимальное расстояние до звезды, на котором может находиться корабль очередного туриста. Эти расстояния не превосходят 10⁶.

Для каждого туриста выведите в отдельной строке максимальное количество рас, с которыми он сможет познакомиться