eolymp
bolt
Try our new interface for solving problems
Problems

Тренування пам'яті

Тренування пам'яті

Time limit 1 second
Memory limit 256 MiB

Василь та Петро тренують пам'ять. Для цього вони беруть масив 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

Input example #1
6
1 2 3 4 5 6
3 6 1 2 4
2 6 3 4
3 4 6
4 3
3
Output example #1
2 4 5 
1 3 6 
Input example #2
5
1 8 4 2 100
2 4 100 8
100 2 8
2 8
2
Output example #2
1 2 100 
4 8 

Scoring

У цій задачі кожен тест оцінюється окремо. Проте також:

  1. У 22% тестів у початковому масиві A кожне ціле число від 1 до n трапляється рівно один раз.

  2. У 35% тестів n \leq 10.

Author Nikolay Arzubov
Source UOI 2023. III stage