Тренування пам'яті
Тренування пам'яті
Василь та Петро тренують пам'ять. Для цього вони беруть масив A[1..n] із n елементів та виконують такі дії:
спочатку Василь забирає собі будь-яке число з цього масиву та називає в довільному порядку всі інші елементи масиву;
потім Петро робить аналогічні дії з масивом, елементи якого назвав Василь, тобто забирає собі будь-яке число з цього масиву та називає в довільному порядку всі інші елементи масиву;
потім свій хід знову робить Василь;
потім знову Петро;
і так далі.
Очевидно, що після n ходів усі елементи масиву A будуть розподілені між Василем та Петром.
Розглянемо на прикладі, як відбувається тренування пам'яті. Нехай початковий масив A = [1\; 2\; 3\; 4\; 5\; 6].
Першу дію виконує Василь: [3\; 6\; 1\; 2\; 4]. Він забрав собі число 5 та назвав у довільному порядку всі інші елементи масиву A.
Далі Петро називає такий масив: [2\; 6\; 3\; 4]. Він забрав собі число 1.
Далі Василь називає такий масив: [3\; 4\; 6]. Він забрав собі число 2.
Далі Петро називає такий масив: [4\; 3]. Він забрав собі число 6.
Далі Василь називає такий масив: [3]. Він забрав собі число 4.
Петро забирає собі останнє число 3.
Отже, у Василя опинилися числа [2\;4\; 5], а в Петра [1\; 3\; 6].
Напишіть програму, яка за заданим масивом та перебігом подій з'ясує, хто які елементи забрав собі.
Input data
Перший рядок містить одне ціле число n (2 \le n \le 1\,000) — кількість елементів у масиві A.
Другий рядок містить n цілих чисел a_1, a_2, \dots, a_n (-10^9 \le a_i \le 10^9).
Кожен з наступних (n-1) рядків містить масив, який називав Василь або Петро. Гарантується, що масиви правильні, тобто кожен такий масив можна отримати з попереднього.
Output data
У першому рядку виведіть у порядку неспадання елементи, які забрав собі Василь.
У другому рядку виведіть у порядку неспадання елементи, які забрав собі Петро.
Examples
6 1 2 3 4 5 6 3 6 1 2 4 2 6 3 4 3 4 6 4 3 3
2 4 5 1 3 6
5 1 8 4 2 100 2 4 100 8 100 2 8 2 8 2
1 2 100 4 8
Scoring
У цій задачі кожен тест оцінюється окремо. Проте також:
У 22% тестів у початковому масиві A кожне ціле число від 1 до n трапляється рівно один раз.
У 35% тестів n \leq 10.