|
Удаление
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 10 2 6
1
2
3
5
10
5 | 0
1
6
8
5
8 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
