Если вы уже участвовали в нашей олимпиаде, то, вероятно, помните, что в прошлом году Рудольф приобрёл N томов Сверхбольшой Энциклопедии Структур Данных, а его друзья Леонидас и Роберт помогли ему изготовить книжные шкафы.
Рудольфу пришлось потрудиться с заполнением шкафов, поскольку тома энциклопедии требовали расстановки в специальном _правильном_ порядке. Так или иначе, в этом году вышло новое издание Энциклопедии, и количество томов в нём многократно возросло! Рудольф с ужасом размышляет о том, сколько работы по расстановке томов придётся проделать на этот раз, поэтому вновь просит вас о помощи.
Тома энциклопедии нумеруются различными целыми числами от 1 до N. _Правильный_ порядок предполагает, что тома расставлены по возрастанию количества единичных бит в двоичном представлении их номеров, а если для нескольких томов это количество совпадает — по возрастанию номеров томов.
Тома ставятся в шкаф начиная с верхней полки, слева направо. Очередной том ставится в следующий шкаф только тогда, когда предыдущий шкаф полностью заполнен.
Помогите Рудольфу написать программу, которая подскажет, как расставить тома энциклопедии в конкретном шкафу.
Первая строка содержит целые числа N, L и K (1 ≤ N ≤ 1018, 1 ≤ L, K ≤ 100) — соответственно количество томов энциклопедии, количество полок в одном шкафу и количество томов, которые умещаются на одной полке.
Вторая строка содержит целое число M (1 ≤ M ≤ 1018) — номер шкафа, который интересует Рудольфа. Гарантируется, что шкаф M будет заполнен полностью или частично.
Выведите одну или более строк, каждая из которых содержит номера томов энциклопедии, размещённых в шкафу M, в _правильном_ порядке.
## Входные Данные
Первая строка содержит целые числа N, L и K (1 ≤ N ≤ 1018, 1 ≤ L, K ≤ 100) — соответственно количество томов энциклопедии, количество полок в одном шкафу и количество томов, которые умещаются на одной полке. Вторая строка содержит целое число M (1 ≤ M ≤ 1018) — номер шкафа, который интересует Рудольфа. Гарантируется, что шкаф M будет заполнен полностью или частично.
## Выходные Данные
Выведите одну или более строк, каждая из которых содержит номера томов энциклопедии, размещённых в шкафу M, в _правильном_ порядке.
## Примеры
Входные данные10 2 32Выходные данные69107Входные данные6 2 21Выходные данные1243
[samples]
**Definitions**
Let $ N, L, K \in \mathbb{Z}^+ $:
- $ N $: total number of volumes (numbered $ 1 $ to $ N $),
- $ L $: number of shelves per cabinet,
- $ K $: number of volumes per shelf.
Let $ M \in \mathbb{Z}^+ $: target cabinet index.
Define the *correct order* of volumes as a permutation $ \pi $ of $ \{1, 2, \dots, N\} $, such that:
- Volumes are sorted primarily by the number of 1-bits in their binary representation (popcount),
- Secondarily, by ascending numerical value if popcounts are equal.
Each 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 $.
**Constraints**
1. $ 1 \leq N \leq 10^{18} $
2. $ 1 \leq L, K \leq 100 $
3. $ 1 \leq M \leq 10^{18} $
4. Cabinet $ M $ is at least partially filled: $ (M-1) \cdot L \cdot K < N $
**Objective**
Output the volumes in cabinet $ M $, in correct order $ \pi $, arranged shelf-by-shelf (top to bottom), left to right on each shelf.
Let $ \text{start} = (M - 1) \cdot L \cdot K + 1 $,
$ \text{end} = \min(M \cdot L \cdot K, N) $.
Let $ S = \{ \pi[i] \mid i \in [\text{start}, \text{end}] \} $, sorted by:
- $ \text{popcount}(x) $ ascending,
- $ x $ ascending if popcounts equal.
Output each shelf (of up to $ K $ volumes) on a separate line.