Відносний порядок

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

У Зеника є два масиви цілих чисел $a_i$ та $b_i$. Усі $2n$ значень масивів різні.

Зеник хоче утворити один масив-перестановку з $n$ елементів. Для цього він спочатку обирає рядок з $n$ символів, де кожен символ або 1 або 2. Тоді він створює проміжний масив з $n$ елементів, в якому на $i$-ій позиції розташоване $a_i$, якщо $i$-ий символ рядка рівний 1 та $b_i$, якщо 2. Далі він записує масив, в якому на першому місці знаходиться індекс мінімуму в проміжному масиві, на другому — індекс 2-го найменшого значення, на $i$-ому місці індекс $i$-го найменшого значення.

Наприклад, нехай масив $a$ рівний [3, 1, 7, 4], масив $b$ рівний [47, 2, 10, 8], рядок рівний 2122. Тоді проміжний масив рівний [47, 1, 10, 8]. Мінімальне значення в цьому масиві знаходиться на позиції 2, 2-ге найменше значення на позиції 4, 3-тє на позиції 3, 4-те на позиції 1. Тому результат рівний [2, 4, 3, 1].

Марічці цікаво, чи існують 2 різні рядки з символів 1 та 2, що перестановки отримані таким чином однакові.

Вхідні дані

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

В другому рядку задано $n$ цілих чисел $a_i$.

В третьому рядку задано $n$ цілих чисел $b_i$.

Вихідні дані

В першому рядку виведіть TAK, якщо існують 2 різні рядки, що утворюють однакову перестановку, і NI, якщо таких рядків не існує.

Якщо рядки існують, в наступних двох рядках виведіть їх. Кожен рядок повинен бути довжини $n$ з символів 1 та 2, а також рядки повинні бути різними.

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

Обмеження

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

$0 \le a_i, b_i \le 10^9$,

Усі значення $a_i$ та $b_i$ різні.

Приклади