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