背景

小方小块小鸟对科技很感兴趣，毕竟「科学技术是第一生产力」嘛。2022年的诺贝尔物理学奖颁发给了三位在量子纠缠实验上有重大贡献的科学家。他们听说，量子力学是二十世纪物理学的重大发现，能有效的解释科学家们在微观粒子层面观察到的实验现象。 小方小块小鸟发现，这里面有好多词语每个字都认识，但连在一起就不知道是什么意思。但不要紧，他们约定，分头行动去收集一些信息，再一起汇总讨论，通过探究性的学习，尝试搞清楚一些词语的含义。

描述

小鸟在独自研究的过程中，发现了一个名叫「光学镊子」的技术，这个技术的是2018年诺贝尔物理学奖得主的主要工作成就。

由激光束强聚焦形成的光斑对于电介质微粒来说就像是一个「陷阱」，电介质微粒会被捕获在其中。这个时候，如果移动聚焦光斑，微粒就会跟着光斑移动。这种技术可以用于移动细胞病毒颗粒，把细胞捏成各种形状，或者冷却原子。由于光镊的力可以精准地直接作用于细胞甚至更小的目标，因此在生物学方面的应用变得越来越广泛。

科学家和工程师们在一起，已经利用光镊子技术制造出可以冷却原子的机器。在某项研究中，科学家和工程师们一个平面光子电路上实现了一个可配置的光镊阵列，证明了单个铯原子可以被光学镊子捕获，紧紧地聚焦在纳米结构的表面上。这些被捕获的原子可以利用电子倍增CCD摄像机上进行荧光成像。连眼睛都看不见的原子，科学家们都能操作，真的太厉害了！

这天晚上，小鸟做了个梦，自己得到了操控一台光学镊子的机会。在梦里，他一开始把$n$个铯原子排成一行，放在距离原点不同距离的位置($x_1, x_2, x_3, ... , x_n$)上（由于原子很小，所以小鸟可以把好几个铯原子放在同一个位置上）。接下来，他利用光学镊子对这些铯原子进行了$op$次操作。每次他都把某个位置$from$上的全部铯原子搬到了新的位置$to$上。

就这么在梦里完成了$n$次操作后，小鸟突然醒了！他的的辛苦操作的结果都没有了。小鸟趁自己还记得，赶紧找了张纸，把最初的$n$个铯原子的位置，以及$op$次操作的$from$、$to$都记了下来。现在需要你帮他计算一下，这么多次操作过后，在哪些位置上有铯原子，把这些有铯原子的位置按照从小到大输出。

输入输出格式

输入

第一行为正整数$n$ ( $1 < n <= 100000$)，表示最开始铯原子的个数。 第二行为若干个以空格分割的正整数$x$ ( $1 < x <=10000000000$ )，表示铯原子最初的位置。（注意，多个铯原子可以在同一个位置） 第三行为正整数$op$ ( $1 < op <= 100000$)，表示小鸟进行的操作次数。 随后$op$行，每行两个以空格分割的正整数$from$, $to$ ( $1 < from, to<=10000000000$ )，表示小鸟该次操作把哪个位置的铯原子搬到哪个位置上。

输出

一行，输出操作后，有铯原子的位置。位置按照从小到大排序。

样例

4
1 6 7 8
3
1 2
7 9
2 5

5 6 8 9

4
1 1 3 3
2
1 2
3 2

2