Танцующие слоны --- это зрелищное шоу в Паттайе, в котором участвуют \textbf{n} слонов, танцующих на одной линии, называемой сценой. В результате многолетних тренировок слоны, участвующие в шоу, разучили большое количество танцевальных движений. Все шоу состоит из последовательности актов. В каждом акте только один слон совершает одно танцевальное движение, в результате которого он может переместиться на другую позицию на сцене. Постановщики шоу хотят сделать фотоальбом, который бы содержал фотографии всего шоу. После каждого акта они хотят сделать фотографии всех слонов. В любой момент времени на протяжении шоу некоторое количество слонов может находиться в одной и той же позиции --- это значит, что слоны просто стоят рядом. Одна фотокамера может фотографировать группу слонов тогда и только тогда, когда все позиции, в которых находятся слоны, лежат на отрезке длины \textbf{l} (обе границы отрезка включаются в него). Так как слоны могут располагаться вдоль всей сцены, то может потребоваться несколько фотокамер, чтобы сфотографировать всех слонов одновременно. К примеру, предположим, что l\textbf{ = 10} и слоны располагаются на сцене в позициях \textbf{10}, \textbf{15}, \textbf{17} и \textbf{20} соответственно. В этот момент достаточно одной фотокамеры, чтобы сфотографировать всех слонов, как это показано ниже (слоны изображены как треугольники, фотокамеры изображены как трапеции). \includegraphics{https://static.e-olymp.com/content/3a/3a8d06ba4dbe6eb3cdeec7339b292d79dd419c3c.jpg} В последующем акте слон, находящийся в позиции \textbf{15}, в результате танцевального движения перемещается в позицию \textbf{32}. После этого необходимо уже не менее двух фотокамер для того, чтобы сфотографировать всех слонов одновременно. \includegraphics{https://static.e-olymp.com/content/80/809e05b2b6a993edd5f88fd7c5767220394f1075.jpg} В следующем акте слон, находящийся в позиции \textbf{10}, перемещается в позицию \textbf{7}. В данном случае понадобится \textbf{3 }фотокамеры для того, чтобы сфотографировать всех слонов. \includegraphics{https://static.e-olymp.com/content/d8/d86cb8fc8b736670ce5c198c74a39c10698835ea.jpg} Вы же должны определить для каждого акта минимальное количество фотокамер, которые нужны, чтобы сфотографировать всех слонов после него. \InputFile Первая строка входного файла содержит три целых неотрицательных числа \textbf{n}, \textbf{l} и \textbf{m} (\textbf{0} ≤ \textbf{n }≤ \textbf{15·10^4}, \textbf{0 }≤ \textbf{l }≤ \textbf{10^9}, \textbf{0 }≤ \textbf{m} ≤ \textbf{15·10^4}). Далее следуют \textbf{n} строк по одному числу \textbf{x_i} в каждой --- позиция каждого слона (\textbf{0} ≤ \textbf{x_i} ≤ \textbf{10^9}). Гарантируется, что все входные позиции упорядочены. Следует заметить, что в течение танца может поменяться порядок слонов. Далее следует \textbf{m} строк. В каждой из них содержится два числа \textbf{i} и \textbf{y}, означающих, что в соответствующем акте слон с номером \textbf{i} перемещается в позицию c координатами \textbf{y}. Гарантируется, что \textbf{y }удовлетворяет ограничению: \textbf{0} ≤ \textbf{y} ≤ \textbf{10^9}. \OutputFile Выведите \textbf{m} строк по одному числу в каждой: минимальное количество фотокамер, необходимых, чтобы сфотографировать всех слонов после него.