您有一个整数数组(最初为空)。
您必须执行 $$$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$$$ 是第一种类型的查询数量。
示例
输入 #1
7 1 3 1 1 2 1 2 1 2 1 1 1 2 2 1 3
输出 #1
3 2 2 3 2
输入 #2
4 1 1 1 2 1 1 2 2 2
输出 #2
1 2 1
输入 #3
8 2 1 4 1 1 1 4 1 2 2 2 4 2 4 3 1 2 2 2 7
输出 #3
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]$$$。