{"raw_statement":[{"iden":"statement","content":"Теперь, когда количество шкафов посчитано, и Леонидас и Роберт смогли их изготовить, перед Рудольфом встала не менее важная и сложная проблема: такая важная энциклопедия, как Сверхбольшая Энциклопедия Структур Данных, не может стоять абы как, её тома должны стоять в _правильном_ порядке, чтобы их было удобно искать и читать.\n\nТома нумеруются различными целыми числами от 1 до n. _Правильный_ порядок предполагает, что тома расставлены по возрастанию количества единичных бит в двоичном представлении их номеров, а если для нескольких томов это количество совпадает — по возрастанию номеров томов. \n\nТома энциклопедии ставятся в шкаф начиная с верхней полки, слева направо. Том ставится в следующий шкаф только в том случае, если предыдущий шкаф полностью заполнен.\n\nВручную определять порядок томов оказалось утомительным даже для такого сильного математика, как Рудольф. Помогите ему написать программу, которая подскажет, как расставить тома энциклопедии в конкретном шкафу.\n\nПервая строка содержит целые числа n, l и k (1 ≤ n ≤ 1000, 1 ≤ l ≤ 100, 1 ≤ k ≤ 100) — соответственно количество томов энциклопедии, количество полок в одном шкафу и количество томов, которые умещаются на одной полке. \n\nВторая строка содержит целое число m (1 ≤ m ≤ 1000) — номер шкафа, который интересует Рудольфа. Гарантируется, что шкаф m будет заполнен полностью или частично.\n\nВыведите одну или более строк, каждая из которых содержит номера томов энциклопедии, которые будут стоять в шкафу m, в «_правильном_» порядке.\n\n"},{"iden":"входные данные","content":"Первая строка содержит целые числа n, l и k (1 ≤ n ≤ 1000, 1 ≤ l ≤ 100, 1 ≤ k ≤ 100) — соответственно количество томов энциклопедии, количество полок в одном шкафу и количество томов, которые умещаются на одной полке. Вторая строка содержит целое число m (1 ≤ m ≤ 1000) — номер шкафа, который интересует Рудольфа. Гарантируется, что шкаф m будет заполнен полностью или частично."},{"iden":"выходные данные","content":"Выведите одну или более строк, каждая из которых содержит номера томов энциклопедии, которые будут стоять в шкафу m, в «_правильном_» порядке."},{"iden":"примеры","content":"Входные данные10 2 32Выходные данные69107Входные данные6 2 21Выходные данные1243"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, l, k \\in \\mathbb{Z}^+ $: number of volumes, shelves per cabinet, volumes per shelf.  \nLet $ m \\in \\mathbb{Z}^+ $: target cabinet index.  \n\nLet $ V = \\{1, 2, \\dots, n\\} $ be the set of volume indices.  \nFor each volume $ i \\in V $, define $ b(i) = \\text{popcount}(i) $, the number of 1-bits in the binary representation of $ i $.  \n\nDefine the ordering $ \\prec $ on $ V $:  \n$ i \\prec j $ if and only if $ b(i) < b(j) $, or $ b(i) = b(j) $ and $ i < j $.  \n\nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of volumes sorted by $ \\prec $.  \n\nEach cabinet holds $ l \\cdot k $ volumes.  \nThe volumes in cabinet $ m $ are $ A_{(m-1) \\cdot l \\cdot k + 1}, A_{(m-1) \\cdot l \\cdot k + 2}, \\dots, A_{\\min(m \\cdot l \\cdot k, n)} $.  \n\n**Objective**  \nOutput the volumes in cabinet $ m $, arranged in $ l $ rows (shelves), each row containing $ k $ volumes (or fewer for the last row if incomplete), in left-to-right order.","simple_statement":"You are given n books numbered 1 to n.  \nSort them by:  \n1. Number of 1-bits in their binary representation (ascending)  \n2. If tie, by book number (ascending)  \n\nEach shelf holds k books, each cabinet has l shelves.  \nYou are given cabinet number m.  \nPrint all book numbers in cabinet m, in order, one shelf per line.","has_page_source":false}