A. Интересная книга
Задачу добавил: alef
Успешно сдано решений: 22
Вы, наверное, знаете (а если не знали, то теперь узнаете), что прошедшим летом на Большом Адронном Коллайдере был найден бозон Хиггса.
— Ну новая частица и новая частица, их же сотни, что такой шум подняли? — спросил Программист у Физика. — Вечно эти журналисты делают из мухи слона.
— Это действительно очень важная частица, — ответил Физик. — Возможно, она позволит объяснить спонтанное нарушение симметрии...
Послушав рассказ Физика про бозон Хиггса, Программист захотел изучить квантовую теорию и попросил Физика посоветовать ему какую-нибудь хорошую книгу. Физик знает, что, с точки зрения Программиста, хорошей является книга, в которой достаточно много математических формул.
Уточним, что если на странице не менее A формул, то такая страница представляется Программисту интересной, если же менее — то скучной.
Программист прочитывает ровно p страниц в день (за исключением, быть может, дня, когда он дочитает последние страницы в книге). Если последняя из прочитанных им страниц была, по его мнению, интересной, он сообщает Физику, что «сегодня было интересно», в противном случае Физик получит от него сообщение «сегодня было скучно».
По заданным значениям p определите, какое количество сообщений «сегодня было интересно» и какое количество сообщений «сегодня было скучно» получит Физик, пока Программист будет читать книгу.
В первой строке содержатся целые числа N и A (1 ≤ N, A ≤ 105) — количество страниц в книге и количество формул на странице, достаточное для того, чтобы Программист счёл эту страницу интересной.
Во второй строке содержится N чисел a1, a2, ..., aN (0 ≤ aj ≤ 105, j = 1, 2, ..., N), определяющих количество формул на соответствующей странице книги.
В третьей строке содержится число Q (1 ≤ Q ≤ 105) — количество запросов, для которых необходимо найти ответ.
В последующих Q строках содержится по одному значению p (1 ≤ p ≤ N), для каждого из которых нужно определить количество сообщений «сегодня было интересно» и количество сообщений «сегодня было скучно».
В каждой из Q строк содержится по два целых числа через пробел: количество сообщений «сегодня было интересно» и количество сообщений «сегодня было скучно» для соответствующего значения p.
10 5
0 3 8 5 1 0 0 4 9 0
6
3
2
1
2
7
10
2 2
1 4
3 7
1 4
0 2
0 1