410565: GYM104052 D Lost in Translation

This is a "run-twice" problem; your program will be run twice for each test.

Your task is to implement a program that transmits data through an unreliable channel. On the first end (during the first run), you get a binary string of length $$$n$$$, and your program has to be able to recover it on the other end of the channel (during the second run).

Thankfully, the channel allows you to send strings with $$$k$$$ different types of characters ($$$k > 2$$$) and use strings of length $$$m$$$ ($$$m > n$$$). But, there is a catch: when you transmit a string, all occurrences of some type of character will be removed. The remaining characters will still follow in the same order. Your job is to develop an algorithm to encode the input string, so it's possible to recover it after the transmission.

To speed up the testing, in each test, you will need to encode and transmit $$$t$$$ binary strings at once. These strings will be transmitted independently, and different strings might have different types of characters removed from them.

During the first run, the first line contains an integer $$$1$$$. The second line contains four integers $$$t$$$, $$$n$$$, $$$m$$$, and $$$k$$$ — the numbers of strings to encode, the length of each string, the maximum possible length of the encoded string, and the number of types of characters you can use ($$$1 \le t \le 100$$$, $$$k = 3$$$ or $$$k = 4$$$).

The following $$$t$$$ lines contain a binary string of length $$$n$$$.

If $$$k = 4$$$, then you can use A, B, C, D in the encoded string. If $$$k = 3$$$, then you can only use A, B, and C.

During the second run, the first line contains an integer $$$2$$$. The second line contains four integers $$$t$$$, $$$n$$$, $$$m$$$, and $$$k$$$, similar to the previous description.

Then, the following $$$t$$$ lines contain strings outputted by your program during the first run, but every string is missing some type of character. These strings are given to you in the same order as during the first run.

During the first run, print $$$t$$$ nonempty strings with at most $$$m$$$ characters from { A, B, C, D } or { A, B, C }, depending on the value of $$$k$$$.

The character to be deleted will be chosen in such a way that the resulting string is not empty. For example, if you output CCCC, all characters of type C will not be removed from the string.

During the second run, you need to decode these strings into initial binary strings of length $$$n$$$.

1
2 10 20 4
0111011001
1111111110

BAACBBACDCDDAACCAABD
DABBADCBCBBCCACA

2
2 10 20 4
AACACDCDDAACCAAD
DBBDCBCBBCCC

0111011001
1111111110

In the example, you need to transmit two binary strings 0111011001 and 1111111110, using strings of length $$$m = 20$$$ and $$$k = 4$$$ different characters. For example, suppose that after the first run, your program outputted BAACBBACDCDDAACCAABD for the first string and DABBADCBCBBCCACA for the second string.

Before the second run, the judges' program removes some type of character from each string. For example, here, we removed all B's from the first string and all A's from the second string. You have to restore and print the initial binary strings 0111011001 and 1111111110.