{"problem":{"name":"E. Рудольф и правильный порядок","description":{"content":"Если вы уже участвовали в нашей олимпиаде, то, вероятно, помните, что в прошлом году Рудольф приобрёл N томов Сверхбольшой Энциклопедии Структур Данных, а его друзья Леонидас и Роберт помогли ему изго","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10176E"},"statements":[{"statement_type":"Markdown","content":"Если вы уже участвовали в нашей олимпиаде, то, вероятно, помните, что в прошлом году Рудольф приобрёл N томов Сверхбольшой Энциклопедии Структур Данных, а его друзья Леонидас и Роберт помогли ему изготовить книжные шкафы.\n\nРудольфу пришлось потрудиться с заполнением шкафов, поскольку тома энциклопедии требовали расстановки в специальном _правильном_ порядке. Так или иначе, в этом году вышло новое издание Энциклопедии, и количество томов в нём многократно возросло! Рудольф с ужасом размышляет о том, сколько работы по расстановке томов придётся проделать на этот раз, поэтому вновь просит вас о помощи.\n\nТома энциклопедии нумеруются различными целыми числами от 1 до N. _Правильный_ порядок предполагает, что тома расставлены по возрастанию количества единичных бит в двоичном представлении их номеров, а если для нескольких томов это количество совпадает — по возрастанию номеров томов. \n\nТома ставятся в шкаф начиная с верхней полки, слева направо. Очередной том ставится в следующий шкаф только тогда, когда предыдущий шкаф полностью заполнен.\n\nПомогите Рудольфу написать программу, которая подскажет, как расставить тома энциклопедии в конкретном шкафу.\n\nПервая строка содержит целые числа N, L и K (1 ≤ N ≤ 1018, 1 ≤ L, K ≤ 100) — соответственно количество томов энциклопедии, количество полок в одном шкафу и количество томов, которые умещаются на одной полке. \n\nВторая строка содержит целое число M (1 ≤ M ≤ 1018) — номер шкафа, который интересует Рудольфа. Гарантируется, что шкаф M будет заполнен полностью или частично.\n\nВыведите одну или более строк, каждая из которых содержит номера томов энциклопедии, размещённых в шкафу M, в _правильном_ порядке.\n\n## Входные Данные\n\nПервая строка содержит целые числа N, L и K (1 ≤ N ≤ 1018, 1 ≤ L, K ≤ 100) — соответственно количество томов энциклопедии, количество полок в одном шкафу и количество томов, которые умещаются на одной полке. Вторая строка содержит целое число M (1 ≤ M ≤ 1018) — номер шкафа, который интересует Рудольфа. Гарантируется, что шкаф M будет заполнен полностью или частично.\n\n## Выходные Данные\n\nВыведите одну или более строк, каждая из которых содержит номера томов энциклопедии, размещённых в шкафу M, в _правильном_ порядке.\n\n## Примеры\n\nВходные данные10 2 32Выходные данные69107Входные данные6 2 21Выходные данные1243\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, L, K \\in \\mathbb{Z}^+ $:  \n- $ N $: total number of volumes (numbered $ 1 $ to $ N $),  \n- $ L $: number of shelves per cabinet,  \n- $ K $: number of volumes per shelf.  \n\nLet $ M \\in \\mathbb{Z}^+ $: target cabinet index.  \n\nDefine the *correct order* of volumes as a permutation $ \\pi $ of $ \\{1, 2, \\dots, N\\} $, such that:  \n- Volumes are sorted primarily by the number of 1-bits in their binary representation (popcount),  \n- Secondarily, by ascending numerical value if popcounts are equal.  \n\nEach cabinet has $ L \\times K $ slots. The $ m $-th cabinet ($ m \\geq 1 $) contains volumes at positions $ \\{(m-1) \\cdot L \\cdot K + 1, \\dots, \\min(m \\cdot L \\cdot K, N)\\} $ in the correct order $ \\pi $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^{18} $  \n2. $ 1 \\leq L, K \\leq 100 $  \n3. $ 1 \\leq M \\leq 10^{18} $  \n4. Cabinet $ M $ is at least partially filled: $ (M-1) \\cdot L \\cdot K < N $  \n\n**Objective**  \nOutput the volumes in cabinet $ M $, in correct order $ \\pi $, arranged shelf-by-shelf (top to bottom), left to right on each shelf.  \n\nLet $ \\text{start} = (M - 1) \\cdot L \\cdot K + 1 $,  \n$ \\text{end} = \\min(M \\cdot L \\cdot K, N) $.  \n\nLet $ S = \\{ \\pi[i] \\mid i \\in [\\text{start}, \\text{end}] \\} $, sorted by:  \n- $ \\text{popcount}(x) $ ascending,  \n- $ x $ ascending if popcounts equal.  \n\nOutput each shelf (of up to $ K $ volumes) on a separate line.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10176E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}