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

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

2 seconds
512 megabytes
Very hard

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

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

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

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

Input

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

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

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

1 \le n \le 10^5,

0 \le b_i, c_i \le n,

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

Output

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

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

В першому прикладі, маємо 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) є відповіддю на задачу.