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

Обмеження: 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\) різні.

Приклади