Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

A. Интересная книга

Задачу добавил: alef

Успешно сдано решений: 21

ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

Вы, наверное, знаете (а если не знали, то теперь узнаете), что прошедшим летом на Большом Адронном Коллайдере был найден бозон Хиггса.

— Ну новая частица и новая частица, их же сотни, что такой шум подняли? — спросил Программист у Физика. — Вечно эти журналисты делают из мухи слона.

— Это действительно очень важная частица, — ответил Физик. — Возможно, она позволит объяснить спонтанное нарушение симметрии...

Послушав рассказ Физика про бозон Хиггса, Программист захотел изучить квантовую теорию и попросил Физика посоветовать ему какую-нибудь хорошую книгу. Физик знает, что, с точки зрения Программиста, хорошей является книга, в которой достаточно много математических формул.

Уточним, что если на странице не менее 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

Сдать задачу

Задать вопрос жюри по этой задаче