Перед ответственной олимпиадой Макс установил новый пароль для входа в тестирующую систему, состоящий из N символов. Этот пароль Макс записал на бумажке, а бумажку сложил гармошкой ширины M, как показано на рисунке, и положил в карман.
В день олимпиады Макс очень торопился, поэтому в какой-то момент сложенная бумажка выпала из кармана и упала в сугроб, так что K левых символов оказались в снегу. Когда Макс поднял и развернул бумажку, оказалось, что все попавшие в снег символы расплылись и стали нечитаемыми.
Но ещё не всё потеряно — определённую часть пароля Макс уже выучил наизусть. Тем не менее, некоторые символы он не запомнил, и хочет выяснить, попали они в снег или нет. Помогите ему найти ответ на этот вопрос.
Первая строка содержит целые числа N, M и K (1 ≤ K ≤ M ≤ N ≤ 1018) — соответственно длину пароля, длину сложенной гармошкой бумажки и количество левых символов сложенной бумажки, попавших в снег.
Вторая строка содержит целое число Q (1 ≤ Q ≤ 105) — количество запросов.
Третья строка содержит Q целых чисел Ai (1 ≤ Ai ≤ N) — номера символов, для которых Макс хочет узнать, оказались они в снегу или нет.
Для каждого из номеров Ai выведите, не разделяя пробелами, 0, если соответствующий символ не попал в снег, либо 1, если попал.
## Входные Данные
Первая строка содержит целые числа N, M и K (1 ≤ K ≤ M ≤ N ≤ 1018) — соответственно длину пароля, длину сложенной гармошкой бумажки и количество левых символов сложенной бумажки, попавших в снег.Вторая строка содержит целое число Q (1 ≤ Q ≤ 105) — количество запросов.Третья строка содержит Q целых чисел Ai (1 ≤ Ai ≤ N) — номера символов, для которых Макс хочет узнать, оказались они в снегу или нет.
## Выходные Данные
Для каждого из номеров Ai выведите, не разделяя пробелами, 0, если соответствующий символ не попал в снег, либо 1, если попал.
## Примеры
Входные данные13 5 281 3 7 8 9 10 11 13Выходные данные10001110Входные данные20 4 21015 5 6 1 18 12 4 2 9 13Выходные данные1001100110
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of studies.
Let $ [s, f] \subset \mathbb{Z} $ be the time interval of interest.
Let $ \mathcal{I} = \{ [b_i, e_i] \mid i \in \{1, \dots, n\} \} $ be the set of study intervals, where $ b_i, e_i \in \mathbb{Z} $, $ b_i < e_i $.
Let $ q \in \mathbb{Z}^+ $ be the number of queries.
Let $ K = (k_1, k_2, \dots, k_q) $ be the sequence of threshold values, where $ k_j \in \mathbb{Z}^+ $.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le s < f \le 10^9 $
3. $ 1 \le b_i < e_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
4. $ 1 \le q \le 10^5 $
5. $ 1 \le k_j \le n $ for all $ j \in \{1, \dots, q\} $
**Objective**
For each query $ k_j $, compute the total length of time within $ [s, f] $ during which the number of overlapping studies from $ \mathcal{I} $ is strictly less than $ k_j $. That is, define the coverage function:
$$
c(t) = \left| \{ i \in \{1, \dots, n\} \mid t \in [b_i, e_i] \} \right|, \quad t \in [s, f]
$$
Then, for each $ j \in \{1, \dots, q\} $, output:
$$
t_j = \int_{s}^{f} \mathbf{1}_{\{c(t) < k_j\}} \, dt
$$