Bajtoccy genetycy od dawna badają sekwencje bajtokwasów dwóch modelowych organizmów: nicienia Bajtorhabditis elegans i muszki Bajtophila melanogaster. Aby stwierdzić, w jakim stopniu sekwencja muszki pochodzi od sekwencji nicienia, chcieliby oni znaleźć jak najwięcej takich samych fragmentów w tych sekwencjach. Badania utrudnia fakt, że w wyniku ewolucji gatunków w sekwencjach mogły wystąpić mutacje, polegające na tym, że pewien rodzaj bajtokwasu z sekwencji mógł przekształcić się w inny.

Rodzaje bajtokwasów oznaczamy liczbami naturalnymi. Zakładamy, że mutacja dotyczy wszystkich wystąpień danego rodzaju bajtokwasu we fragmencie sekwencji. Przykładowo, fragment 2 1 2 mógł w wyniku jednej mutacji przekształcić się we fragment 6 1 6, 2 5 2 lub 2 2 2, ale nie we fragment 2 1 6 lub 1 1 2.

Twoim zadaniem jest pomóc genetykom odpowiadać na pytania o to, czy dany fragment sekwencji muszki mógł powstać z danego fragmentu sekwencji nicienia w wyniku co najwyżej jednej mutacji.

Input Format

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($2 \le n \le 500,000$) oznaczającą długość sekwencji bajtokwasów nicienia. Drugi wiersz zawiera ciąg $n$ liczb całkowitych $u_{i}$ ($1 \le u_{i} \le 500,000$) oznaczających rodzaje kolejnych bajtokwasów wchodzących w skład sekwencji nicienia. Trzeci wiersz zawiera jedną liczbę całkowitą $m$ ($2 \le m \le 500,000$) oznaczającą długość sekwencji bajtokwasów muszki. Czwarty wiersz zawiera ciąg $m$ liczb całkowitych $v_{i}$ ($1 \le v_{i} \le 500,000$) oznaczających rodzaje kolejnych bajtokwasów wchodzących w skład sekwencji muszki.

Piąty wiersz zawiera jedną liczbę całkowitą $q$ ($1 \le q \le 500,000$) oznaczającą liczbę zapytań. Dalej następuje $q$ wierszy, z których każdy zawiera trzy liczby całkowite $a_{i}$, $b_{i}$ oraz $l_{i}$ ($1 \le a_{i} \le a_{i} + l_{i} - 1 \le n$, $1 \le b_{i} \le b_{i} + l_{i} - 1 \le m$). Oznaczają one zapytanie o to, czy fragment $[b_{i},\ b_{i}+l_{i}-1]$ sekwencji bajtokwasów muszki mógł powstać z fragmentu $[a_{i},\ a_{i}+l_{i}-1]$ sekwencji bajtokwasów nicienia w wyniku co najwyżej jednej mutacji.

Output Format

Twój program powinien wypisać na wyjście $q$ wierszy; $i$-ty z nich powinien zawierać jedno słowo TAK lub NIE oznaczające odpowiedź na $i$-te zapytanie.

Example

Input

6  
4 3 2 1 2 2  
7  
3 2 2 6 1 6 2  
5  
1 1 1  
1 1 2  
3 4 3  
3 4 4  
5 2 2

Output

TAK  
NIE  
TAK  
NIE  
TAK