Memory training#184
Vasyl and Petro are training their memories. To do this, they take an array with elements and perform the following actions:
First, Vasyl takes any number from the array, and names all other elements of the array at random.
Then Petro takes any number from the array named by Vasyl, and names all other elements of that array at random.
Then Vasyl performs his turn again.
Then Petro performs his turn.
And so on.
Obviously, after moves, all elements of the array will be distributed between Vasyl and Petro.
Let's take a look at an example of how memory training works. Let the initial array be A = [1\; 2\; 3\; 4\; 5\; 6].
Vasyl makes the first move: [3\; 6\; 1\; 2\; 4]. He took number and named all other elements of the array at random.
Then Petro names this array: [2\; 6\; 3\; 4]. He took number for himself.
Vasyl names this array: . He took number for himself.
Petro names this array: . He took number for himself.
Vasyl names this array: . He took number for himself.
Petro takes the last number, for himself.
Thus, Vasyl received the numbers , and Petro received the numbers .
Write a program that, given an input array and the sequence of actions, determines who got which elements.
The first line contains a single integer (2 \leq n \leq 1\,000) — the number of elements in the array.
The second line contains integers a_1, a_2, \dots, a_n (-10^9 \leq a_i \leq 10^9).
Each of the following (n-1) lines contains an array, which was named by either Vasyl or Petro. It is guaranteed that the arrays are correct, that is, each of them can be obtained from the previous one.
In the first line, output the elements that Vasyl took in non-descending order.
In the second line, output the elements that Petro took in non-descending order.
Example 1
Example 2
In this problem, each test is evaluated separately. However, further:
In 22% of the tests, each integer from to occurs exactly once in the initial array .
In 35% of the tests, n \leq 10.