CF2168A2.Encode and Decode (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $a_i \leq 10^9$.

This is a run-twice (communication) problem. In these problems, your program will be run twice. All variables stored in the memory will be lost between runs, but information given to you in the first run may be important in trying to solve the problem correctly in the second run. Therefore, the main challenge is to find a strategy to communicate between the two runs using the limited output you can use.

Time limit and memory limit are not shared between the runs. For example, in this problem, since the time limit is $2$ seconds, you will only receive a verdict of Time Limit Exceeded if either run exceeds $2$ seconds, but it is perfectly okay if both runs of your program last $1.5$ seconds.

In this problem, your task is to find a strategy to encode and decode an array $a$ of size $n$.

The first run is the encoding phase. You are given $n$ and the elements of $a$ by the jury. Your task is to encode this array into a string $s$ that contains only letters of the lowercase English alphabet, and pass $s$ back to the jury. Then, your program will terminate, and all variables stored in memory will be lost.

The second run is the decoding phase. You are given the string $s$ (the same string you passed to the jury during the first run) by the jury. Your task is to decode $s$ and determine $n$ and the elements of array $a$ that were originally given by the jury. In other words, you must reverse your encoding algorithm from the first run.

First Run

Your code will be run exactly two times on each test. On the first run, you will perform encoding.

Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as the encoding algorithm.

The second line contains exactly an integer $n$ ($1 \le n \le 10^4$) — the length of $a$.

The third line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).

Output

When ready to send $s$, you can do so by printing the following:

• $s$, the encoded string ($1 \leq |s| \leq 10^5$, where $|s|$ denotes the length of $s$). This string must contain only lowercase letters of the English alphabet and should be printed without spaces.

After this, your program should terminate. Note that all variables stored in memory will be lost.

Second Run

On the second run, you will perform decoding.

Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as the decoding algorithm.

The second line of input contains string $s$, the variable that you passed to the jury during the first run.

Output

When ready to send the original values of $n$ and the array $a$, you can do so by printing the following:

• $n\, a_1\, a_2\, \ldots\, a_n$, the length of the original array, and the array itself.

这是该问题的困难版本。两个版本的区别在于，在本版本中，$a_i \leq 10^9$。

这是一个“运行两次”（通信）类问题。在此类问题中，你的程序将被运行两次。两次运行之间内存中存储的所有变量均会被清空，但在第一次运行中获得的信息可能对在第二次运行中正确求解问题至关重要。因此，主要挑战在于：利用你所能输出的有限信息，设计一种在两次运行之间进行通信的策略。

两次运行的时间限制和内存限制彼此独立。例如，在本题中，时间限制为 $2$ 秒；若任意一次运行耗时超过 $2$ 秒，则你会收到“超时”（Time Limit Exceeded）判据；但若你的程序两次运行分别耗时 $1.5$ 秒，则完全合法。

在本题中，你的任务是设计一种对长度为 $n$ 的数组 $a$ 进行编码与解码的策略。

第一次运行是编码阶段。评测系统会向你提供 $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$：原始数组的长度及其全部元素。

The two examples are meant to demonstrate two runs on the same test.

On the first run, you are given that $n = 5$ and $a = [100, 200, 300, 400, 500]$ by the jury. After reading in the input, you use your encoding algorithm to decide that $s$ should be skibidi. You output this back to the jury. Then, your program terminates, all variables stored in memory are lost, and the second run proceeds.

On the second run, you are given that $s = \mathtt{skibidi}$ by the jury. After reading this input, you use your decoding algorithm to restore the original values of $n$ and $a$. Fortunately, you determine that $n = 5$ and $a = [100, 200, 300, 400, 500]$. You output this back to the jury and the jury checks if it is equal to the original values. Since it is, you will pass this test.

These examples may not demonstrate optimal encoding/decoding algorithms.

这两个示例旨在展示在同一测试用例上的两次运行。

在第一次运行中，评测系统给出 $n = 5$ 和 $a = [100, 200, 300, 400, 500]$。读入输入后，你使用自己的编码算法确定字符串 $s$ 应为 skibidi，并将该字符串输出给评测系统。随后，你的程序终止，所有内存中存储的变量均被清除，接着开始第二次运行。

在第二次运行中，评测系统给出 $s = \mathtt{skibidi}$。读入该输入后，你使用自己的解码算法恢复原始的 $n$ 和 $a$ 的值。幸运的是，你确定出 $n = 5$ 且 $a = [100, 200, 300, 400, 500]$，并将该结果输出给评测系统；评测系统会检查该结果是否与原始值一致。由于二者完全相同，你将通过该测试。

这些示例未必展示了最优的编码/解码算法。