{"raw_statement":[{"iden":"statement","content":"Перед ответственной олимпиадой Макс установил новый пароль для входа в тестирующую систему, состоящий из N символов. Этот пароль Макс записал на бумажке, а бумажку сложил гармошкой ширины M, как показано на рисунке, и положил в карман.\n\nВ день олимпиады Макс очень торопился, поэтому в какой-то момент сложенная бумажка выпала из кармана и упала в сугроб, так что K левых символов оказались в снегу. Когда Макс поднял и развернул бумажку, оказалось, что все попавшие в снег символы расплылись и стали нечитаемыми.\n\nНо ещё не всё потеряно — определённую часть пароля Макс уже выучил наизусть. Тем не менее, некоторые символы он не запомнил, и хочет выяснить, попали они в снег или нет. Помогите ему найти ответ на этот вопрос.\n\nПервая строка содержит целые числа N, M и K (1 ≤ K ≤ M ≤ N ≤ 1018) — соответственно длину пароля, длину сложенной гармошкой бумажки и количество левых символов сложенной бумажки, попавших в снег.\n\nВторая строка содержит целое число Q (1 ≤ Q ≤ 105) — количество запросов.\n\nТретья строка содержит Q целых чисел Ai (1 ≤ Ai ≤ N) — номера символов, для которых Макс хочет узнать, оказались они в снегу или нет.\n\nДля каждого из номеров Ai выведите, не разделяя пробелами, 0, если соответствующий символ не попал в снег, либо 1, если попал. \n\n"},{"iden":"входные данные","content":"Первая строка содержит целые числа N, M и K (1 ≤ K ≤ M ≤ N ≤ 1018) — соответственно длину пароля, длину сложенной гармошкой бумажки и количество левых символов сложенной бумажки, попавших в снег.Вторая строка содержит целое число Q (1 ≤ Q ≤ 105) — количество запросов.Третья строка содержит Q целых чисел Ai (1 ≤ Ai ≤ N) — номера символов, для которых Макс хочет узнать, оказались они в снегу или нет."},{"iden":"выходные данные","content":"Для каждого из номеров Ai выведите, не разделяя пробелами, 0, если соответствующий символ не попал в снег, либо 1, если попал. "},{"iden":"примеры","content":"Входные данные13 5 281 3 7 8 9 10 11 13Выходные данные10001110Входные данные20 4 21015 5 6 1 18 12 4 2 9 13Выходные данные1001100110"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of studies.  \nLet $ [s, f] \\subset \\mathbb{Z} $ be the time interval of interest.  \nLet $ \\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 $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ K = (k_1, k_2, \\dots, k_q) $ be the sequence of threshold values, where $ k_j \\in \\mathbb{Z}^+ $.\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 1 \\le s < f \\le 10^9 $  \n3. $ 1 \\le b_i < e_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\le q \\le 10^5 $  \n5. $ 1 \\le k_j \\le n $ for all $ j \\in \\{1, \\dots, q\\} $\n\n**Objective**  \nFor 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:  \n$$  \nc(t) = \\left| \\{ i \\in \\{1, \\dots, n\\} \\mid t \\in [b_i, e_i] \\} \\right|, \\quad t \\in [s, f]  \n$$  \nThen, for each $ j \\in \\{1, \\dots, q\\} $, output:  \n$$  \nt_j = \\int_{s}^{f} \\mathbf{1}_{\\{c(t) < k_j\\}} \\, dt  \n$$","simple_statement":"You are given n time intervals representing research studies.  \nYou are also given a time range [s, f] that investors care about.  \nFor each moment in [s, f], count how many studies cover it.  \nIf a moment is covered by fewer than k studies, it needs more research.  \nFor q queries, each with a different k, output the total time in [s, f] covered by fewer than k studies.","has_page_source":false}