Вибір команди#11755

Вибір команди

4 секунди

128 мегабайтів

Середня

Два капітани команд формують свої команди, обираючи гравців з множини, яка нумерується від $1$ до $n$ . Капітани вибирають по черзі, причому кожен з них обирає $k$ -го гравця серед тих, що залишились, виходячи зі своїх ідей про те, який з решти гравців буде найкращим доповненням до їхніх команд.

Враховуючи вибори двох лідерів (перший капітан команди починає першим), обчисліть список гравців у кожній команді.

Вхідні дані

Складається з трьох рядків.

Перший рядок містить єдине ціле число $n (2 \leq n \leq 4 \cdot 1 0^{6}$ n~(2 \le n \le 4 \cdot 10^6, $n$ кратне $2$ ).

Другий рядок містить $n /2$ цілих чисел $a_{1}, a_{2}, ..., a_{n /2}$ a_1, a_2, ..., a_{n/2}, що представляють вибори першого капітана команди: під час $(2 k - 1)$ (2k - 1)-го ходу перший капітан вибрав $a_{k}$ a_k-го гравця, що залишився.

Третій рядок містить $n /2$ цілих чисел $b_{1}, b_{2}, ..., b_{n /2}$ b_1, b_2, ..., b_{n/2}, що представляють вибори другого капітана команди: під час $2 k$ -го ходу другий капітан вибрав $b_{k}$ b_k-го гравця, що залишився.

Вибори капітанів команди є дійсними: на кожному етапі вони знаходяться між $1$ та кількістю залишених гравців (включно).

Вихідні дані

Виведіть два рядки, кожен з яких містить $n /2$ цілих чисел.

Перший рядок має містити список $x_{1}, x_{2}, ..., x_{n /2}$ x_1, x_2, ..., x_{n/2} гравців, обраних для участі в першій команді, у порядку їх вибору: гравець $x_{k}$ x_k був обраний під час $(2 k - 1)$ (2k - 1)-го ходу.

Другий рядок має містити список $y_{1}, y_{2}, ..., y_{n /2}$ y_1, y_2, ..., y_{n/2} гравців, обраних для участі в другій команді, у порядку їх вибору: гравець $y_{k}$ y_k був обраний під час $2 k$ -го ходу.

Приклади

Приклад 1