G. Самосинхронизирующийся код
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это задача с двойным запуском.

На лабораторной работе по физике студенты разработали устройство, позволяющее передавать текстовые сообщения из строчных латинских букв с помощью лазера. Перед отправкой сообщение переводится в двоичный код и затем передаётся последовательно бит за битом.

Однако, при тестировании устройства выявилась проблема. Оказалось, что если при передаче встретятся четыре одинаковых бита подряд (то есть «0000» или «1111»), то на приёмной стороне сбивается синхронизация. Поэтому необходимо придумать способ кодирования, при котором такая ситуация будет невозможна. Также разработчики хотят, чтобы количество битов в закодированном сообщении превышало длину исходного сообщения не более чем в шесть раз.

Разработайте какой-нибудь способ кодирования и декодирования, удовлетворяющий данным требованиям.

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

Первая строка входных данных содержит число $$$t$$$, равное 1 или 2.

Если $$$t=1$$$, то вторая входная строка содержит сообщение, которое нужно закодировать. Оно состоит из строчных латинских букв и имеет длину от 1 до 10000 символов.

Если $$$t=2$$$, то вторая входная строка содержит закодированное ранее вашей программой сообщение, которое требуется декодировать.

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

Выведите одну строку — закодированное либо декодированное сообщение.

Пример
Входные данные
1
aba
Выходные данные
100101101101100101
Входные данные
2
100101101101100101
Выходные данные
aba