Для послідовності , що складається зі скінченної кількості невід’ємних цілих чисел, визначимо як найменше невід’ємне ціле число, якого немає в . Наприклад, \text{mex}(0,0,1,3)=2, \text{mex}(1)=0, \text{mex}()=0.
Вам задано дві послідовності та , що складаються з невід’ємних цілих чисел.
Побудуйте послідовність з невід’ємних цілих чисел, яка задовольняє наведені нижче умови.
\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.
Гарантовано, що для заданих вхідних даних така послідовність існує.
У першому рядку задано ціле число .
У другому рядку задано цілих чисел b_i.
У третьому рядку задано цілих чисел c_i.
1 \le n \le 10^5,
0 \le b_i, c_i \le n,
гарантовано, що існує послідовність , яка задовольняє умови.
Виведіть цілих чисел a_i – елементи послідовності . Значення a_i не повинні бути більшими за 10^9. Можна довести, що існує послідовність, яка задовольняє це обмеження.
Якщо існує декілька відповідей, виведіть будь-яку з них.
Example
Example 1
Example 2
В першому прикладі, маємо 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) є відповіддю на задачу.