E. Замена чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив целых чисел (изначально пустой).

Вам предстоит выполнить $$$q$$$ запросов. Каждый запрос имеет один из двух типов:

  • «$$$1$$$ $$$x$$$» — добавить элемент $$$x$$$ в конец массива;
  • «$$$2$$$ $$$x$$$ $$$y$$$» — заменить все вхождения $$$x$$$ в массиве на $$$y$$$.

Найдите массив, получившийся после выполнения всех запросов.

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

Первая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — количество запросов.

Следующие $$$q$$$ строк содержат запросы (по одному на строку). Каждый запрос имеет один из двух типов:

  • «$$$1$$$ $$$x$$$» ($$$1 \le x \le 5 \cdot 10^5$$$);
  • «$$$2$$$ $$$x$$$ $$$y$$$» ($$$1 \le x, y \le 5 \cdot 10^5$$$).

Гарантируется, что есть хотя бы один запрос первого типа.

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

В единственную строку выведите $$$k$$$ целых чисел — массив, получившийся после выполнения всех запросов, где $$$k$$$ — количество запросов первого типа.

Примеры
Входные данные
7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3
Выходные данные
3 2 2 3 2
Входные данные
4
1 1
1 2
1 1
2 2 2
Выходные данные
1 2 1
Входные данные
8
2 1 4
1 1
1 4
1 2
2 2 4
2 4 3
1 2
2 2 7
Выходные данные
1 3 3 7
Примечание

В первом примере из условия массив меняется следующим образом:

$$$[]$$$ $$$\rightarrow$$$ $$$[3]$$$ $$$\rightarrow$$$ $$$[3, 1]$$$ $$$\rightarrow$$$ $$$[3, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 1]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 1, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 3, 2]$$$.

Во втором примере из условия массив меняется следующим образом:

$$$[]$$$ $$$\rightarrow$$$ $$$[1]$$$ $$$\rightarrow$$$ $$$[1, 2]$$$ $$$\rightarrow$$$ $$$[1, 2, 1]$$$ $$$\rightarrow$$$ $$$[1, 2, 1]$$$.

В третьем примере из условия массив меняется следующим образом:

$$$[]$$$ $$$\rightarrow$$$ $$$[]$$$ $$$\rightarrow$$$ $$$[1]$$$ $$$\rightarrow$$$ $$$[1, 4]$$$ $$$\rightarrow$$$ $$$[1, 4, 2]$$$ $$$\rightarrow$$$ $$$[1, 4, 4]$$$ $$$\rightarrow$$$ $$$[1, 3, 3]$$$ $$$\rightarrow$$$ $$$[1, 3, 3, 2]$$$ $$$\rightarrow$$$ $$$[1, 3, 3, 7]$$$.