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

Limits: 2 sec., 256 MiB

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

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

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

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

Input

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

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

Output

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

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

Constraints

$1 \le n \le 10^5$,

$1 \le a_i \le n$.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 3 2 2	Tak 3 1 3 2 4 2 3 2

Input (stdin) сopy	Output (stdout) сopy
3 2 2 2	Ni

Input (stdin) сopy	Output (stdout) сopy
4 1 2 4 3	Tak 1 2 4 3 1 2 3 4

Notes

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