25674번 - Message Made of Noise 다국어투 스텝

문제

Alisa wants to send a message to Eva using a number wire. The message is one English word.

Unfortunately, right now the number wire transmits just some noise: random integers from 0ドル$ to 10ドル^{9} - 1$ inclusive. Alisa knows the sequence of the next 10ドル,000円$ integers that will be transmitted.

Fortunately, Alisa has a superpower: she can erase any number of elements from any positions in the sequence. The relative order of the remaining elements does not change.

Unfortunately, after that, around half of the integers will be lost in transmission: each transmitted integer will disappear with a probability of 1ドル / 2$. The relative order of the remaining elements once again does not change.

How should Alisa and Eva act to transmit a given word?

입력

출력

제한

인터랙션

In this problem, your solution will be run twice on each test. In input and output, numbers on a single line are separated by spaces. Each line of input is terminated by an end-of-line character.

첫 번째 실행

During the first run, the solution acts for Alisa. The first line contains the name "Alisa". The second line contains one word from English dictionary, its length is from 2ドル$ to 15ドル$ letters, and it consists of lowercase English letters. The third line contains an integer $n,ドル the length of the sequence (in this problem, $n$ is always equal to 10ドル,000円$). The fourth line contains $n$ integers from 0ドル$ to 10ドル^{9} - 1$ inclusive: the initial sequence. The numbers are selected in advance by a pseudorandom number generator, all numbers from the range are equiprobable.

The solution should print the numbers that Alisa decided to leave in the sequence. On the first line, print an integer $m$: the number of integers left. On the second line, print the remaining numbers in the order they follow in the initial sequence.

두 번째 실행

During the second run, the solution acts for Eva. The first line contains the name "Eva". The second line contains an integer $k,ドル the number of remaining integers in the sequence. The third line contains $k$ integers from 0ドル$ to 10ドル^{9} - 1$ inclusive: the remaining sequence itself. Each number that Alisa decided to leave in the sequence is present with probability 1ドル / 2$ and missing with probability 1ドル / 2$. The way the numbers go missing is fixed in advance in each test, so, if solutions make the same choices in the first run, they will get the same sequences for the second run.

Print one English word: the word Alisa should have sent to Eva.

예제

For each test, the input during the second run depends on the solution's output during the first run.

Below we show two runs of a certain solution on the first test. The sequences are shown only partially for brevity. The full version of the example can be seen in 001.phase1.full.input 001.phase1.full.output 001.phase2.full.input 001.phase2.full.output.

힌트