Трансформація рядків
Маємо два рядки u і v, що складаються з літер a і b. Наша мета — перетворити рядок u на v за допомогою наступної операції обміну: можна вибрати два неперетинні фрагменти ab і ba в першому рядку і поміняти їх місцями. Чи можливо перетворити u на v за допомогою певної послідовності таких операцій?
Вхідні дані
Перша строка містить одне число n (2 ≤ n ≤ 10^6) — довжину рядків. Далі йдуть два рядки, кожен з яких складається з n літер a та/або b. Перший рядок описує u, другий рядок описує v. Вважайте, що рядки різні.
Вихідні дані
У першому рядку виведіть слово TAK (польське так) або NIE (польське ні) якщо u можна перетворити на v за допомогою операцій обміну.
Якщо відповідь позитивна і n ≤ 4000, програма повинна вивести приклад послідовності операцій обміну. У першому рядку виведіть кількість операцій m (1 ≤ m ≤ 10^6). Кожен з наступних m рядків містить два цілих числа a[i], b[i] (1 ≤ a[i], b[i] ≤ n - 1) — позиції початкових літер фрагментів, які обмінюються: a[i] вказує на позицію ab, b[i] вказує на позицію ba.
Якщо існує декілька рішень, виведіть будь-яке з них. Зокрема, вам не потрібно мінімізувати кількість операцій, тобто число m.