A. Серийный убийца
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наш любимый детектив Шерлок занят поиском серийного убийцы, который убивает одного человека каждый день. Используя свой дедуктивный метод, он узнал, что у киллера есть стратегия для выбора следующей жертвы.

В первый день у убийцы есть две потенциальных жертвы. Он выбирает одну из них, убивает ее и заменяет ее новой потенциальной жертвой. Та же процедура повторяется каждый день. Таким образом, каждый день у убийцы есть две потенциальных жертвы, из которых он выбирает. Шерлок знает имена потенциальных жертв в первый день. Кроме этого, он знает, кого убили в каждый день и кто — новая потенциальная жертва, заменившая убитую.

Вам необходимо вычислить для каждого дня две потенциальные жертвы, из которых киллер выбирал в этот день, ведь Шерлок надеется найти в этой информации какую-то закономерность.

Входные данные

Первая строка содержит два имени (длина каждого не превосходит 10) потенциальных жертв в первый день.

Вторая строка содержит целое число n (1 ≤ n ≤ 1000) — число дней.

Каждая из следующих n строк содержит два имени (длина каждого не превосходит 10) — сначала имя человека, убитого в этот день, затем имя человека, ставшего новой потенциальной жертвой.

Входные данные согласованы, то есть гарантируется, что каждый убитый человек является одной из двух потенциальных жертв в этот день. Гарантируется, что имена всех людей различны и состоят из строчных букв латинского алфавита.

Выходные данные

Выведите n + 1 строку, i-я строка должна содержать имена двух людей, из которых убийца выбирает жертву в i-й день. (n + 1)-я строка должна содержать два имени, из которых будет выбрана следующая жертва. В каждой строке два имени могут быть выведены в любом порядке.

Примеры
Входные данные
ross rachel
4
ross joey
rachel phoebe
phoebe monica
monica chandler
Выходные данные
ross rachel
joey rachel
joey phoebe
joey monica
joey chandler
Входные данные
icm codeforces
1
codeforces technex
Выходные данные
icm codeforces
icm technex
Примечание

В первом примере изначально потенциальные жертвы это ross и rachel.

  • После дня 1: ross убит, и появляется joey.
  • После дня 2: rachel убит, и появляется phoebe.
  • После дня 3: phoebe убит, и появляется monica.
  • После дня 4: monica убит, и появляется chandler.