Byteotian geneticists have long been studying the sequences of byte-acids in two model organisms: the nematode Bajtorhabditis elegans and the fruit fly Bajtophila melanogaster. To determine the extent to which the fly's sequence is derived from the nematode's, they would like to find as many identical fragments as possible in these sequences. Research is complicated by the fact that, as a result of species evolution, mutations may have occurred in the sequences, where one type of byte-acid in a sequence could have transformed into another.

Types of byte-acids are denoted by natural numbers. We assume that a mutation affects all occurrences of a given type of byte-acid within a sequence fragment. For example, the fragment 2 1 2 could have transformed into 6 1 6, 2 5 2, or 2 2 2 as a result of a single mutation, but not into 2 1 6 or 1 1 2.

Your task is to help the geneticists answer questions about whether a given fragment of the fly's sequence could have been formed from a given fragment of the nematode's sequence as a result of at most one mutation.

Input

The first line of input contains a single integer $n$ ($2 \le n \le 500,000$) representing the length of the nematode's byte-acid sequence. The second line contains a sequence of $n$ integers $u_{i}$ ($1 \le u_{i} \le 500,000$) representing the types of consecutive byte-acids in the nematode's sequence. The third line contains a single integer $m$ ($2 \le m \le 500,000$) representing the length of the fly's byte-acid sequence. The fourth line contains a sequence of $m$ integers $v_{i}$ ($1 \le v_{i} \le 500,000$) representing the types of consecutive byte-acids in the fly's sequence.

The fifth line contains a single integer $q$ ($1 \le q \le 500,000$) representing the number of queries. This is followed by $q$ lines, each containing three integers $a_{i}$, $b_{i}$, and $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$). These represent a query as to whether the fragment $[b_{i},\ b_{i}+l_{i}-1]$ of the fly's byte-acid sequence could have been formed from the fragment $[a_{i},\ a_{i}+l_{i}-1]$ of the nematode's byte-acid sequence as a result of at most one mutation.

Output

Your program should output $q$ lines; the $i$-th line should contain a single word TAK or NIE representing the answer to the $i$-th query.

Examples

Input 1

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 1

TAK  
NIE  
TAK  
NIE  
TAK