{"problem":{"name":"G. Пароль в снегу","description":{"content":"Перед ответственной олимпиадой Макс установил новый пароль для входа в тестирующую систему, состоящий из N символов. Этот пароль Макс записал на бумажке, а бумажку сложил гармошкой ширины M, как показ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10126G"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nПервая строка содержит целые числа N, M и K (1 ≤ K ≤ M ≤ N ≤ 1018) — соответственно длину пароля, длину сложенной гармошкой бумажки и количество левых символов сложенной бумажки, попавших в снег.Вторая строка содержит целое число Q (1 ≤ Q ≤ 105) — количество запросов.Третья строка содержит Q целых чисел Ai (1 ≤ Ai ≤ N) — номера символов, для которых Макс хочет узнать, оказались они в снегу или нет.\n\n## Выходные Данные\n\nДля каждого из номеров Ai выведите, не разделяя пробелами, 0, если соответствующий символ не попал в снег, либо 1, если попал. \n\n## Примеры\n\nВходные данные13 5 281 3 7 8 9 10 11 13Выходные данные10001110Входные данные20 4 21015 5 6 1 18 12 4 2 9 13Выходные данные1001100110\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10126G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}