Префіксний і суфіксний mex

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

Для послідовності \(X\), що складається зі скінченної кількості невід’ємних цілих чисел, визначимо \(\text{mex}(X)\) як найменше невід’ємне ціле число, якого немає в \(X\). Наприклад, \(\text{mex}(0,0,1,3)=2\), \(\text{mex}(1)=0\), \(\text{mex}()=0\).

Вам задано дві послідовності \(b\) та \(c\), що складаються з \(n\) невід’ємних цілих чисел.

Побудуйте послідовність \(a\) з \(n\) невід’ємних цілих чисел, яка задовольняє наведені нижче умови.

• \(\text{mex}(a_1, a_2, \dots, a_i) = b_i\) для всіх \(1 \le i \le n\).

• \(\text{mex}(a_i, a_{i + 1}, \dots, a_n) = c_i\) для всіх \(1 \le i \le n\).

Гарантовано, що для заданих вхідних даних така послідовність існує.

Вхідні дані

У першому рядку задано ціле число \(n\).

У другому рядку задано \(n\) цілих чисел \(b_i\).

У третьому рядку задано \(n\) цілих чисел \(c_i\).

Вихідні дані

Виведіть \(n\) цілих чисел \(a_i\) – елементи послідовності \(a\). Значення \(a_i\) не повинні бути більшими за \(10^9\). Можна довести, що існує послідовність, яка задовольняє це обмеження.

Якщо існує декілька відповідей, виведіть будь-яку з них.

Обмеження

\(1 \le n \le 10^5\),

\(0 \le b_i, c_i \le n\),

гарантовано, що існує послідовність \(a\), яка задовольняє умови.

Приклади

Вхідні дані (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

Примітки

В першому прикладі, маємо \(b = (1, 1, 1, 3), c = (3, 3, 2, 0)\). Покажемо, що послідовність \(a = (0, 2, 0, 1)\) є можливою відповіддю.

• \(\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\).

Таким чином, оскільки всі умови виконано, \(a=(0, 2, 0, 1)\) є відповіддю на задачу.