Танцующие слоны
Танцующие слоны — это зрелищное шоу в Паттайе, в котором участвуют n слонов, танцующих на одной линии, называемой сценой.
В результате многолетних тренировок слоны, участвующие в шоу, разучили большое количество танцевальных движений. Все шоу состоит из последовательности актов. В каждом акте только один слон совершает одно танцевальное движение, в результате которого он может переместиться на другую позицию на сцене.
Постановщики шоу хотят сделать фотоальбом, который бы содержал фотографии всего шоу. После каждого акта они хотят сделать фотографии всех слонов.
В любой момент времени на протяжении шоу некоторое количество слонов может находиться в одной и той же позиции — это значит, что слоны просто стоят рядом.
Одна фотокамера может фотографировать группу слонов тогда и только тогда, когда все позиции, в которых находятся слоны, лежат на отрезке длины l (обе границы отрезка включаются в него). Так как слоны могут располагаться вдоль всей сцены, то может потребоваться несколько фотокамер, чтобы сфотографировать всех слонов одновременно.
К примеру, предположим, что l = 10 и слоны располагаются на сцене в позициях 10, 15, 17 и 20 соответственно. В этот момент достаточно одной фотокамеры, чтобы сфотографировать всех слонов, как это показано ниже (слоны изображены как треугольники, фотокамеры изображены как трапеции).
В последующем акте слон, находящийся в позиции 15, в результате танцевального движения перемещается в позицию 32. После этого необходимо уже не менее двух фотокамер для того, чтобы сфотографировать всех слонов одновременно.
В следующем акте слон, находящийся в позиции 10, перемещается в позицию 7. В данном случае понадобится 3 фотокамеры для того, чтобы сфотографировать всех слонов.
Вы же должны определить для каждого акта минимальное количество фотокамер, которые нужны, чтобы сфотографировать всех слонов после него.
Входные данные
Первая строка входного файла содержит три целых неотрицательных числа n, l и m (0 ≤ n ≤ 15·10^4, 0 ≤ l ≤ 10^9, 0 ≤ m ≤ 15·10^4). Далее следуют n строк по одному числу x_i в каждой — позиция каждого слона (0 ≤ x_i ≤ 10^9). Гарантируется, что все входные позиции упорядочены. Следует заметить, что в течение танца может поменяться порядок слонов. Далее следует m строк. В каждой из них содержится два числа i и y, означающих, что в соответствующем акте слон с номером i перемещается в позицию c координатами y. Гарантируется, что y удовлетворяет ограничению: 0 ≤ y ≤ 10^9.
Выходные данные
Выведите m строк по одному числу в каждой: минимальное количество фотокамер, необходимых, чтобы сфотографировать всех слонов после него.