Bajtoccy 的遗传学家们长期以来一直在研究两种模式生物的 bajtokwas 序列：线虫 Bajtorhabditis elegans 和果蝇 Bajtophila melanogaster。为了确定果蝇的序列在多大程度上来源于线虫的序列，他们希望在这些序列中找到尽可能多的相同片段。然而，研究受到进化过程中可能发生的突变的干扰，即某种类型的 bajtokwas 在序列中可能转变为另一种。

我们用自然数来表示 bajtokwas 的种类。我们假设，一次突变会影响片段序列中所有出现的某一类 bajtokwas。例如，片段 2 1 2 在一次突变后可以变为 6 1 6、2 5 2 或 2 2 2，但不能变为 2 1 6 或 1 1 2。

你的任务是帮助遗传学家回答以下问题：给定的果蝇序列片段是否可能由线虫序列片段在至多一次突变的作用下产生。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 500,000$），表示线虫 bajtokwas 序列的长度。 第二行包含 $n$ 个整数 $u_{i}$（$1 \le u_{i} \le 500,000$），表示线虫序列中依次出现的 bajtokwas 的种类。 第三行包含一个整数 $m$（$2 \le m \le 500,000$），表示果蝇 bajtokwas 序列的长度。 第四行包含 $m$ 个整数 $v_{i}$（$1 \le v_{i} \le 500,000$），表示果蝇序列中依次出现的 bajtokwas 的种类。

第五行包含一个整数 $q$（$1 \le q \le 500,000$），表示查询的数量。 接下来是 $q$ 行，每行包含三个整数 $a_{i}$、$b_{i}$ 和 $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$）。 它们表示一个查询，询问果蝇序列的片段 $[b\_{i},\ b\_{i}+l\_{i}-1]\$ 是否可能由线虫序列的片段 $[a_{i},\ a_{i}+l_{i}-1]$ 在至多一次突变作用下产生。

输出格式

你的程序应输出 $q$ 行；第 $i$ 行应包含一个单词 TAK 或 NIE，表示第 $i$ 个查询的答案。

示例

输入

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

输出

TAK  
NIE  
TAK  
NIE  
TAK