Танцюючі слони --- це видовищне шоу у Паттайї, у якому беруть участь \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} переміщується у позицію з координатою \textbf{y}. Гарантується, що \textbf{y за}довольняє обмеженню: \textbf{0} ≤ \textbf{y} ≤ \textbf{10^9}. \OutputFile Виведіть \textbf{m} рядків по одному числу у кожному: мінімальну кількість фотокамер, необхіних, щоб сфотографувати усіх слонов після кожного акту.