E. Painting the Fence
time limit per test
3.0 s
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a beautiful fence near Monocarp's house. The fence consists of $$$n$$$ planks numbered from left to right. The $$$i$$$-th plank has color $$$a_i$$$.

Monocarp's father have decided to give his son $$$m$$$ orders. Each order is a color $$$c_j$$$. After each order Monocarp finds leftmost and rightmost planks currently having color $$$c_j$$$ and repaints all planks between them into color $$$c_j$$$.

For example, if, at first, fence looked like (from left to right) $$$[1, 2, 3, 1, 4, 1, 5, 6]$$$, then after fulfilling an order with color $$$1$$$ fence will look like $$$[1, 1, 1, 1, 1, 1, 5, 6]$$$.

Assume that Monocarp fulfills all orders in the order they come, one by one.

Note that if current order is about color $$$x$$$ and there is no more than one plank in the fence having color $$$x$$$, then Monocarp doesn't repaint anything, so he can skip this order and skip to the next one.

Find out the color of each plank after Monocarp has done all the given orders.

Input

The first line contains one integer $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$ — the number of planks in the fence.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 3 \cdot 10^5)$$$, where $$$a_i$$$ is the initial color of the $$$i$$$-th plank.

The third line contains one integer $$$m$$$ $$$(1 \le m \le 3 \cdot 10^5)$$$ — the number of orders.

The fourth line contains $$$m$$$ space-separated integers $$$c_1, c_2, \dots, c_m$$$ $$$(1 \le c_j \le 3 \cdot 10^5)$$$, where $$$c_j$$$ is the color of the $$$j$$$-th order.

Output

Print $$$n$$$ space-separated integers — the colors of planks in the fence after processing all $$$m$$$ orders.

Examples
Input
4
1 2 1 2
2
2 1
Output
1 2 2 2
Input
8
7 1 7 1 23 9 23 1
4
23 4 7 1
Output
7 7 7 1 1 1 1 1
Note

In the first example initial appearance of the fence is $$$[1, 2, 1, 2]$$$. After the first order (color $$$2$$$) fence will look like $$$[1, 2, 2, 2]$$$. After the second order (color $$$1$$$) appearance of the fence will not change.

In the second example initial appearance of the fence is $$$[7, 1, 7, 1, 23, 9, 23, 1]$$$. After the first order (color $$$23$$$) the fence will look like $$$[7, 1, 7, 1, 23, 23, 23, 1]$$$. After the second order (color $$$4$$$) appearance of the fence will not change. After the third order (color $$$7$$$) the fence will look like $$$[7, 7, 7, 1, 23, 23, 23, 1]$$$. After the fourth order (color $$$1$$$) the fence will look like $$$[7, 7, 7, 1, 1, 1, 1, 1]$$$.