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.