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.

Note

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.

Encode and Decode (Hard Version)

Examples