CFCF2168A2.Encode and Decode (Hard Version)

这是本题的高难度版本。不同之处在于本版本中 $a_i \leq 10^9$。

这是一道运行两次（通信）题。在这类题目中，你的程序会运行两次。两次运行间，存储在内存中的所有变量都会丢失，但在第一次运行中给你的信息，可能对你正确解决第二次运行至关重要。因此，主要的挑战在于采用一定策略，在两次运行间利用你能输出的有限内容进行信息传递。

时间限制和内存限制在两次运行之间不会共享。例如，在本题中，因为时间限制为 $2$ 秒，你只会在任一轮运行超时才会得到 TLE 判定，但如果两次你的程序各耗时 $1.5$ 秒，也是没有问题的。

在本题中，你需要找到一种策略，对一个大小为 $n$ 的数组 $a$ 进行编码和解码。

第一次运行为编码阶段。你将获得 $n$ 和 $a$ 的元素，由评测机给出。你的任务是将这个数组编码为仅包含小写英文字母的字符串 $s$，并将 $s$ 返回给评测机。然后你的程序终止，内存中所有变量都会丢失。

第二次运行为解码阶段。你将获得由评测机给出的字符串 $s$（与第一次输出的字符串相同），你的任务是对 $s$ 进行解码，还原原本的 $n$ 以及数组 $a$。也就是说，你需要逆转第一次的编码算法。

第一次运行

你的代码将在每个测试点上正好运行两次。第一次运行时，你需要进行编码操作。

第一行输入字符串 first。此行用于让你的程序识别这是第一次运行，应作为编码算法处理。

第二行输入一个整数 $n$，表示 $a$ 的长度，满足 $1 \le n \le 10^4$。

第三行输入 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$，其中 $1 \le a_i \le 10^9$。

准备好传递字符串 $s$ 后，请按如下输出：

• $s$，即编码后的字符串（$1 \le |s| \le 10^5$，其中 $|s|$ 表示 $s$ 的长度）。该字符串应仅包含英文小写字母，且中间不包含空格。

输出完毕后，程序应立即终止。请注意，所有内存变量都将在两次运行之间丢失。

第二次运行

在第二次运行时，你需要执行解码操作。

输入格式

第一行输入字符串 second。用于让你的程序识别这是第二次运行，应作为解码算法处理。

第二行输入字符串 $s$，即你在第一次运行中传递给评测机的字符串变量。

输出格式

还原原始的 $n$ 和数组 $a$ 后，请按如下格式输出：

• $n\ a_1\ a_2\ \ldots\ a_n$，即原始数组的长度以及所有数组元素。

两个示例用于演示同一测试点的两次运行。

第一次运行时，评测机给出 $n = 5$，$a = [100, 200, 300, 400, 500]$。读取输入后，你通过自己的编码算法决定编码字符串 $s$ 为 skibidi。输出 $s$ 给评测机，程序终止，所有存储在内存中的内容都将丢失，进入第二次运行。

第二次运行时，评测机给出 $s = \mathtt{skibidi}$。读取输入后，你使用自己的解码算法，成功还原出原来的 $n = 5$ 和 $a = [100, 200, 300, 400, 500]$。你将其输出，评测机会检查其是否与最初数据一致。若一致，则此测试通过。

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