E. Покраска забора
ограничение по времени на тест
3.0 с
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Около дома Монокарпа есть красивый забор, состоящий из $$$n$$$ последовательных досок. Доски нумеруются слева направо, начиная с единицы, причем $$$i$$$-я доска имеет цвет $$$a_i$$$.

Отец Монокарпа решил дать своему сыну $$$m$$$ указаний. Каждое указание характеризуется цветом $$$c_j$$$. После очередного указания Монокарп обязан покрасить все доски между самой левой и самой правой доской цвета $$$c_j$$$ в цвет $$$c_j$$$. Например, если доски забора были выкрашены в цвета (слева направо) $$$[1, 2, 3, 1, 4, 1, 5, 6]$$$, то после выполнения Монокарпом указания с цветом $$$1$$$ доски забора станут выкрашены в цвета (слева направо) $$$[1, 1, 1, 1, 1, 1, 5, 6]$$$.

Считайте, что Монокарп выполняет все указания по очереди, и пока не закончит перекраску забора в соответствии с текущим указанием, следующее указание он не получит.

Обратите внимание, что если цвет очередного указания равен $$$x$$$, и досок забора, покрашеных в цвет $$$x$$$, не больше одной, то Монокарпу не нужно перекрашивать ни одной доски после текущего указания, и он может сразу получить следующее указание.

Определите, как будет выглядеть забор после всех указаний отца Монокарпа.

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

В первой строке задано целое число $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$ — количество досок в заборе.

Во второй строке через пробел задана последовательность из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 3 \cdot 10^5)$$$, где $$$a_i$$$ равно изначальному цвету $$$i$$$-й доски забора.

В третьей строке задано целое число $$$m$$$ $$$(1 \le m \le 3 \cdot 10^5)$$$ — количество указаний.

В четвертой строке через пробел задана последовательность из $$$m$$$ целых чисел $$$c_1, c_2, \dots, c_m$$$ $$$(1 \le c_j \le 3 \cdot 10^5)$$$, где $$$c_j$$$ равно цвету из $$$j$$$-го указания по перекраске.

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

Выведите $$$n$$$ целых чисел через пробел — цвета досок забора после выполнения всех $$$m$$$ указаний.

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

В первом примере забор изначально выглядит как $$$[1, 2, 1, 2]$$$. После первого указания (цвет $$$2$$$) забор станет выглядеть как $$$[1, 2, 2, 2]$$$. После второго указания (цвет $$$1$$$) внешний вид забора не изменится.

Во втором примере забор изначально выглядит как $$$[7, 1, 7, 1, 23, 9, 23, 1]$$$. После первого указания (цвет $$$23$$$) забор станет выглядеть как $$$[7, 1, 7, 1, 23, 23, 23, 1]$$$. После второго указания (цвет $$$4$$$) внешний вид забора не изменится. После третьего указания (цвет $$$7$$$) забор станет выглядеть как $$$[7, 7, 7, 1, 23, 23, 23, 1]$$$. После четвертого указания (цвет $$$1$$$) забор станет выглядеть как $$$[7, 7, 7, 1, 1, 1, 1, 1]$$$.