A. Распределение тортов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чокола и Ванила любят торты. Сегодня менеджер кондитерской дал им в общей сложности $$$2^{k+1}$$$ тортов. Торты были распределены поровну, так что каждый из них изначально получил $$$2^k$$$ тортов.

Однако теперь Чокола и Ванила хотят перераспределить торты так, чтобы у Чокола оказалось ровно $$$x$$$ тортов, а у Ванилы — оставшиеся $$$2^{k+1}-x$$$ тортов.

На каждом шаге они могут выполнить ровно одну из следующих двух операций:

  1. Чокола отдает половину своих тортов Ваниле. Эта операция разрешена только в том случае, если у Чокола в данный момент четное количество тортов.
  2. Ванила отдает половину своих тортов Чоколе. Эта операция разрешена только в том случае, если у Ванилы в данный момент четное количество тортов.

Ваша задача — определить минимальное количество шагов, необходимых для достижения целевого распределения, и вывести любую допустимую последовательность операций, достигающую этого минимума.

Можно доказать, что при заданных ограничениях допустимое решение всегда существует, и минимальное количество необходимых шагов не превосходит $$$120$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$k$$$ и $$$x$$$ ($$$1 \le k \le 60$$$, $$$1 \le x \le 2^{k+1}-1$$$) — каждый человек изначально получил $$$2^k$$$ тортов, а $$$x$$$ — это количество тортов, которое должен иметь Чокола после перераспределения.

Выходные данные

Для каждого набора входных данных выведите одно целое число $$$n$$$ ($$$0\le n\le 120$$$), представляющее минимальное количество шагов, необходимых для перераспределения тортов.

На следующей строке выведите $$$n$$$ целых числа $$$o_1, o_2, \ldots, o_n$$$ ($$$o_i = \mathtt{1}$$$ или $$$o_i = \mathtt{2}$$$), где $$$o_i = \mathtt{1}$$$ означает, что на $$$i$$$-м шаге Чокола отдал половину своих тортов Ваниле (операция 1), а $$$o_i = \mathtt{2}$$$ означает, что Ванила отдал половину своих тортов Чоколу (операция 2).

Пример
Входные данные
4
2 3
2 4
3 7
2 5
Выходные данные
2
2 1 
0

3
2 2 1 
2
1 2
Примечание

В первом наборе входных данных они могут использовать следующие шаги, чтобы у Чокола оказалось ровно $$$x = 3$$$ торта, а у Ванилы — ровно $$$2 ^ {k + 1} - x = 5$$$ тортов. Мы используем $$$\{a, b\}$$$ для обозначения того, что у Чокола в данный момент $$$a$$$ тортов, а у Ванилы — $$$b$$$ тортов.

$$$$$$\{4, 4\} \xrightarrow{o_1 = \mathtt{2}} \{6, 2\} \xrightarrow{o_2 = \mathtt{1}} \{3, 5\}$$$$$$

Во втором наборе входных данных у Чокола уже ровно $$$x = 4$$$ торта, а у Ванилы уже ровно $$$2 ^ {k + 1} - x = 4$$$ торта, поэтому операции не требуются.

В третьем наборе входных данных они могут использовать следующие шаги, чтобы у Чокола оказалось ровно $$$x = 7$$$ тортов, а у Ванилы — ровно $$$2 ^ {k + 1} - x = 9$$$ тортов.

$$$$$$\{8, 8\} \xrightarrow{o_1 = \mathtt{2}} \{12, 4\} \xrightarrow{o_2 = \mathtt{2}} \{14, 2\} \xrightarrow{o_3 = \mathtt{1}} \{7, 9\}$$$$$$