Перед ответственной олимпиадой Макс установил новый пароль для входа в тестирующую систему, состоящий из N символов. Этот пароль Макс записал на бумажке, а бумажку сложил гармошкой ширины M, как показано на рисунке, и положил в карман.
В день олимпиады Макс очень торопился, поэтому в какой-то момент сложенная бумажка выпала из кармана и упала в сугроб, так что K левых символов оказались в снегу. Когда Макс поднял и развернул бумажку, оказалось, что все попавшие в снег символы расплылись и стали нечитаемыми.
Но ещё не всё потеряно — определённую часть пароля Макс уже выучил наизусть. Тем не менее, некоторые символы он не запомнил и хочет выяснить, попали они в снег или нет. Помогите ему найти ответ на этот вопрос.
Первая строка содержит целые числа N, M и K (1 ≤ K ≤ M ≤ N ≤ 1018) — соответственно длину пароля, длину сложенной гармошкой бумажки и количество левых символов сложенной бумажки, попавших в снег.
Вторая строка содержит целое число Q (1 ≤ Q ≤ 105) — количество запросов.
Третья строка содержит Q целых чисел Ai (1 ≤ Ai ≤ N) — номера символов, для которых Макс хочет узнать, оказались они в снегу или нет.
Для каждого из номеров Ai выведите, не разделяя пробелами, 0, если соответствующий символ не попал в снег, либо 1, если попал.
13 5 2
8
1 3 7 8 9 10 11 13
10001110
20 4 2
10
15 5 6 1 18 12 4 2 9 13
1001100110
