Dane są dwa słowa $ u $ i $ v $ złożone z liter a i b. Naszym celem jest przekształcić słowo $ u $ w słowo $ v $. Mamy w tym celu do dyspozycji następującą operację zamiany: wybieramy dwa $ rozłączne $ fragmenty ab i ba w pierwszym słowie i zamieniamy je miejscami. Czy, wykonując skończoną liczbę takich operacji, możemy przekształcić $ u $ w $ v $?

Input Format

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ n $ ($2 \le n \le 1\,000\,000$), oznaczającą długość słów. Każdy z dwóch następnych wierszy zawiera ciąg złożony z $ n $ znaków a i/lub b. Pierwszy wiersz opisuje słowo $ u $, a drugi - słowo $ v $. Możesz założyć, że słowa te będą różne.

Output Format

W pierwszym wierszu wyjścia powinno znaleźć się jedno słowo TAK lub NIE, oznaczające, czy słowo $ u $ można przekształcić w słowo $ v $, wykonując jedynie operacje zamiany.

Jeśli odpowiedź jest twierdząca oraz $ n \le 4\,000 $, Twój program powinien także wypisać przykładowy ciąg operacji prowadzących do celu. Pierwszy wiersz tego opisu powinien zawierać jedną liczbę całkowitą $ m $ ($1 \le m \le 1\,000\,000$), oznaczającą liczbę operacji. Każdy z kolejnych $ m $ wierszy powinien zawierać dwie liczby całkowite $ a_{i} $, $ b_{i} $ ($1 \le a_{i} , b_{i} \le n - 1$), oznaczające pozycje pierwszych liter zamienianych fragmentów ab (odpowiednio $ a_{i} $) i ba (odpowiednio $ b_{i} $).

Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien wypisać jakiekolwiek z nich. W szczególności Twoje rozwiązanie nie musi minimalizować liczby operacji, tj. liczby $ m $.

Example

Input

6
aabbaa
baaaab

Output

TAK
2
2 4
1 5

Input 2

6
aaabbb
ababab

Output 2

NIE