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