Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Удаление

(Время: 1 сек. Память: 64 Мб Сложность: 45%)

Вася уже долго занимается k-расширениями. Недавно ему это надоело, и он стал изучать следующую операцию на строках: сначала удаляется каждый k-ый символ строки с начала и до конца (т. е. сначала k-й, потом 2k-й, и т. д., пока число ik не превосходит длины строки). Потом эта операция повторяется, и так далее, пока в строке есть хотя бы k символов.

Например, если дана строка длины 10, и K = 2, то сначала будут удалены 2, 4, 6, 8 и 10 символы. Затем будут удалены 2 и 4 символы новой строки, которые соответствуют 3 и 7 символам старой. Затем будет удален 2 символ получившейся строки - 5 символ старой. Последним будет удален 9 символ старой строки.

Собственно, задумал он это все для того, чтобы узнать, какой и когда символ исчезнет. Но когда ему надоело вручную удалять символы, он решил поручить это Вам. А именно, Вам придется отвечать на его вопросы: "А на какой секунде был удален i-ый символ строки?" На удаление каждого символа тратится одна секунда.

Входные данные

В первой строке входного файла INPUT.TXT находятся три числа: 1 ≤ n ≤ 5•106 - количество символов, которые написал Вася, число 1 ≤ k ≤ n, и 1 ≤ l ≤ 10 000 - количество вопросов, которые задает Вася. В последующих l строках указаны номера символов, для которых Вася хочет узнать, когда они были удалены. Все номера лежат в пределах от 1 до n и могут повторяться.

Выходные данные

В выходной файл OUTPUT.TXT выведите l строк с ответами на вопросы в том порядке, в каком они были во входном файле. Если окажется, что символ из строки не будет удален никогда, выведите 0.

Пример

INPUT.TXTOUTPUT.TXT
110 2 6
1
2
3
5
10
5
0
1
6
8
5
8

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483