Злиття послідовності і перестановки

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

У Зеника є послідовність \(a\) із \(n\) цілих чисел, кожне з яких від 1 до \(n\) включно. Послідовність може містити однакові елементи.

Марічка поки не має своєї послідовності, але хоче її придумати. Як свою послідовність \(b\) вона може вибрати довільну перестановку різних цілих чисел від 1 до \(n\) включно.

Після цього вони утворять послідовність \(c\) виконавши \(2 \cdot n\) наступних кроків: вибрати найлівіший елемент із \(a\) (якщо \(a\) не пуста) або із \(b\) (якщо \(b\) не пуста) і перемістити його у кінець послідовності \(c\). Зауважте, що на початку послідовність \(c\) пуста, а після завершення процесу вона буде містити рівно \(2 \cdot n\) елементів. На кожному кроці вони можуть незалежно вирішити, із якої послідовності вибрати елемент.

Ваше завдання — знайти таку послідовність \(c\), яку вони можуть отримати, у якої немає однакових сусідніх елементів, або повідомити, що такої не існує.

Вхідні дані

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

У другому рядку задано \(n\) цілих чисел через пробіли — послідовність \(a\).

Вихідні дані

У першому рядку виведіть Tak, якщо шукана послідовність існує, або Ni в протилежному випадку.

Якщо послідовність існує, у другому рядку виведіть \(2 \cdot n\) цілих чисел через пробіли — шукана послідовність \(c\). Якщо існує декілька правильних відповідей — виведіть довільну із них.

Обмеження

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

\(1 \le a_i \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 3 2 2	Tak 3 1 3 2 4 2 3 2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 2 2 2	Ni

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 4 3	Tak 1 2 4 3 1 2 3 4

Примітки

У першому прикладі послідовність Зеника це [3, 3, 2, 2]. Марічка може вибрати перестановку [1, 4, 3, 2]. Після злиття послідовностей вони можуть отримати послідовність [3 1 3 2 4 2 3 2], у якої жодні два сусідні елементи не є однаковими.