Prefix and Suffix Mex

Обмеження: 2 сек., 512 МіБ

For a sequence $X$ composed of a finite number of non-negative integers, we define $\text{mex}(X)$ as the smallest non-negative integer not in $X$. For example, $\text{mex}(0,0,1,3)=2, \text{mex}(1)=0, \text{mex}()=0$.

You are given two sequences $b$ and $c$ of $n$ non-negative integers.

Construct a sequence $a$ of $n$ non-negative integers that satisfies all of the following conditions.

• $\text{mex}(a_1, a_2, \dots, a_i) = b_i$ for all $1 \le i \le n$.

• $\text{mex}(a_i, a_{i + 1}, \dots, a_n) = c_i$ for all $1 \le i \le n$.

It is guaranteed that for a given input such a sequence exists.

Вхідні дані

The first line contains an integer $n$.

The second line contains $n$ integers $b_i$.

The third line contains $n$ integers $c_i$.

Вихідні дані

Print $n$ integers $a_i$ – the elements of sequence $a$. The values $a_i$ must not be greater than $10^9$. One can prove that there exists a sequence satisfying this constraint.

If there are multiple answers, any of them will be accepted.

Обмеження

$1 \le n \le 10^5$,

$0 \le b_i, c_i \le n$,

it is guaranteed that there exists a sequence $a$ satisfying the conditions.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 1 1 3 3 3 2 0	0 2 0 1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 0 0 3 4 4 4 4 4 4 4 4 3 2 0	1 2 0 3 2 0 1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 0 0 0 0 0 0 0 0	4 7 74 474747474

Примітки

In the first example, we have $b = (1, 1, 1, 3), c = (3, 3, 2, 0)$. Let us show that the sequence $a = (0, 2, 0, 1)$ is a possible answer.

• $\text{mex}(a_1) = \text{mex}(0) = 1 = b_1$.

• $\text{mex}(a_1, a_2) = \text{mex}(0, 2) = 1 = b_2$.

• $\text{mex}(a_1, a_2, a_3) = \text{mex}(0, 2, 0) = 1 = b_3$.

• $\text{mex}(a_1, a_2, a_3, a_4) = \text{mex}(0, 2, 0, 1) = 3 = b_4$.

• $\text{mex}(a_1, a_2, a_3, a_4) = \text{mex}(0, 2, 0, 1) = 3 = c_1$.

• $\text{mex}(a_2, a_3, a_4) = \text{mex}(2, 0, 1) = 3 = c_2$.

• $\text{mex}(a_3, a_4) = \text{mex}(0, 1) = 2 = c_3$.

• $\text{mex}(a_4) = \text{mex}(1) = 0 = c_4$.

Thus, since all the conditions are met, $a=(0, 2, 0, 1)$ is an answer to the problem.