Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$a_i \leq 10^9$$$.

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

Ограничения по времени и памяти не делятся между запусками. Например, в этой задаче ограничение по времени составляет $$$2$$$ секунды, поэтому вы получите вердикт Time Limit Exceeded только в том случае, если хотя бы один из запусков превысит $$$2$$$ секунды. Если же оба запуска вашей программы займут $$$1.5$$$ секунды, это не будет ошибкой.

В этой задаче ваша задача состоит в том, чтобы найти стратегию для кодирования и декодирования массива $$$a$$$ размером $$$n$$$.

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

Второй запуск — это фаза декодирования. Вам передается строка $$$s$$$ (та же строка, которую вы передали жюри во время первого запуска). Ваша задача — декодировать $$$s$$$ и определить $$$n$$$ и элементы массива $$$a$$$, которые изначально были даны жюри. Другими словами, вы должны обратить свой алгоритм кодирования из первого запуска.

Первый запуск

Ваша программа будет запущена ровно дважды для каждого теста. В первом запуске вы будете выполнять кодирование.

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

Первая строка входных данных содержит строку first. Это нужно для того, чтобы ваша программа распознала, что это ее первый запуск, и она должна действовать как алгоритм кодирования.

Вторая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^4$$$) — длина $$$a$$$.

Третья строка содержит $$$n$$$ целых чисел, разделенных пробелами $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

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

Когда будете готовы отправить $$$s$$$, вы можете сделать это, напечатав следующее:

• $$$s$$$: закодированную строку ($$$1 \leq |s| \leq 10^5$$$, где $$$|s|$$$ обозначает длину $$$s$$$). Эта строка должна содержать только строчные буквы латинского алфавита и должна быть напечатана без пробелов.

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

Второй запуск

Во втором запуске вы будете выполнять декодирование.

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

Первая строка входных данных содержит строку second. Это нужно для того, чтобы ваша программа распознала, что это ее второй запуск, и она должна действовать как алгоритм декодирования.

Вторая строка входных данных содержит строку $$$s$$$, переменную, которую вы передали жюри во время первого запуска.

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

Когда будете готовы отправить оригинальные значения $$$n$$$ и массива $$$a$$$, вы можете сделать это, напечатав следующее:

• $$$n\, a_1\, a_2\, \ldots\, a_n$$$: длину оригинального массива и сам массив.