Милпул и Догпуля
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это задача с двойным запуском. На каждом тесте ваше решение будет запущено дважды.

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

  1. Милпул загадывает целое неотрицательное число $$$n$$$, после чего каким-то образом преобразует его в битовую строку (последовательность нулей и единиц) $$$s$$$;
  2. Догпуля убедительно лает на получившуюся битовую строку, из-за чего к ней в конец дописывается какое-то (возможно, нулевое) число произвольных бит;
  3. от умиления Милпул забывает, какое число он изначально загадывал, и должен восстановить его по получившейся последовательности $$$q$$$.

Ваша цель — играть за Милпула и выиграть (успешно восстановить исходное число).

Во время первого запуска вашему решению на вход подается целое неотрицательное число $$$n$$$ от $$$1$$$ до $$$10^{18}$$$. Вы должны вывести битовую строку $$$s$$$ длины не более $$$\sqrt{2} \cdot \lceil\log_2 n\rceil + 5$$$.

При втором запуске ваше решение получает на вход строку $$$q$$$ длины не более $$$1000$$$, полученную из строки $$$s$$$ не выходе первого запуска дописыванием произвольного числа бит в конец. Ваше решение должно восстановить число $$$n$$$, поданное на вход во время первого запуска.

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

При первом запуске единственная строка ввода содержит число $$$1$$$ и целое число $$$n$$$ ($$$1 \le n \le 10^{18}$$$).

При втором запуске единственная строка ввода содержит число $$$2$$$ и строку $$$q$$$, полученную из вывода первого запуска описанным в условии образом ($$$1 \le |q| \le 1000$$$).

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

При первом запуске выведите непустую строку $$$s$$$ длины не более $$$\sqrt{2} \cdot \lceil\log_2 n\rceil + 5$$$, состоящую только из символов '0' и '1' — ваш код числа $$$n$$$.

При втором запуске по полученной строке $$$q$$$ восстановите и выведите целое число $$$n$$$, изначально поданное на ввод.

Протокол взаимодействия

Во избежание получения некорректных вердиктов вроде Idleness Limit Exceeded или Security Violation заканчивайте вывод каждой строки символом перевода строки ('{\}n').

Примеры

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

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

010

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

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

11111111

15664

Примечание

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