Bajtazar dał w prezencie swojemu synowi, Bajtkowi, talię kart. Talia składa się z $ n $ kart, ponumerowanych liczbami od 1 do $ n $.

Bajtek bardzo ucieszył się z prezentu. Przez cały wieczór siedział w swoim pokoju i bawił się, tasując karty w talii. Doszedł przy tym do takiej wprawy, że za każdym razem wychodziło mu to tak samo, tzn. podczas tasowania karta z pozycji $ k $ (dla $1 \le k \le n $) przechodziła zawsze na pozycję $ a_{k} $ (oczywiście $1 \le a_{k} \le n $).

W pewnym momencie do pokoju Bajtka przyszedł tata i powiedział, że czas już spać. Bajtek uprosił tatę, aby pokazał mu jeszcze przed snem, jak powinno się tasować karty. Wówczas Bajtazar potasował karty tak, że karta z pozycji $ k $ znalazła się na pozycji $ b_{k} $ (znów $1 \le k,b_{k} \le n $).

Bajtek patrzył z podziwem na to, z jaką wprawą jego tata tasuje karty. Sam też chciałby tak umieć! Niestety Bajtek jest jeszcze mały i nie umie tasować tak jak jego tata. Wpadł jednak na pomysł, że spróbuje kilka razy powtórzyć swój sposób tasowania, tak aby na końcu otrzymać taki układ, jak po tasowaniu taty.

Teraz chłopiec nie może zasnąć, bo zastanawia się, czy jest to w ogóle możliwe. Pomóż mu!

Input Format

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $ n $ ($2 \le n \le 1\,000\,000$). Drugi i trzeci wiersz zawierają opisy permutacji $ a_{1}, \ldots, a_{n} $ oraz $ b_{1}, \ldots, b_{n} $, czyli ciągi $ n $ parami różnych liczb całkowitych z zakresu od 1 do $ n $. Możesz założyć, że te dwie permutacje są różne.

Output Format

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedno słowo TAK lub NIE, w zależności od tego, czy istnieje takie $ k $ > 1, że powtarzając $ k $-krotnie tasowanie Bajtka, można uzyskać potasowanie Bajtazara.

Example

Input

4
2 4 3 1
1 2 3 4

Output

TAK

Input 2

4
1 2 3 4
2 4 3 1

Output 2

NIE