题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXV Olimpiada Informatyczna — III etap Turniej trójinformatyczny

请注意本题的空间限制。

拜托尼亚的程序员深受国民敬仰。因此，近年来的电视节目《三人编程锦标赛》收视率屡创新高。本届锦标赛有 $n$ 名选手（编号 $1$ 至 $n$），他们角逐三项编程赛事（分别是限时实现后缀树、调试 SIO2 系统和解决图灵测试）。每项赛事均公布完整排名，明确每位选手的名次，且无并列情况。

每位拜托尼亚居民都支持某位选手，他们热衷于无休止的争论——尤其在社交媒体上——讨论某选手是否比另一位更优秀。三项赛事使得「更优秀」的定义颇为模糊，增添了讨论的火药味。

Bajtazar 希望满足居民的期待，开发一款应用，快速比较锦标赛选手的成绩。他引入了以下关系：

若满足以下至少一项，选手 $a$ 在道德上优于选手 $b$：

• 在三项赛事中至少两项，选手 $a$ 的名次优于 $b$；
• 存在选手 $c$，使得 $a$ 在道德上优于 $c$，且 $c$ 在道德上优于 $b$。

Bajtazar 的创业公司近期订单繁忙，比较选手的算法任务全权委托给你。编写程序，根据三项赛事的选手排名，回答 $m$ 个查询：「选手 $a$ 是否在道德上优于选手 $b$？」

输入格式

第一行包含一个整数 $n$ $(n \geq 2)$，表示锦标赛选手数量。

第二行包含 $n$ 个互不相同的整数，范围 $[1, n]$，表示第一项赛事中各选手的名次。

第三行和第四行类似，分别表示第二项和第三项赛事的排名，格式相同。

第五行包含一个整数 $m$ $(m \geq 1)$，表示查询数量。

接下来的 $m$ 行描述查询，第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示查询「选手 $a_i$ 是否在道德上优于选手 $b_i$？」。

输出格式

输出 $m$ 行，第 $i$ 行包含一个字符串 TAK 或 NIE，表示第 $i$ 个查询的答案。

5
1 2 4 3 5
2 3 5 1 4
3 1 5 2 4
4
2 4
4 2
1 5
5 1

TAK
TAK
TAK
NIE

提示

样例 1 解释

选手 $2$ 在道德上优于选手 $4$，因其在第一和第三项赛事中名次优于 $4$。

反之，选手 $4$ 也在道德上优于选手 $2$，因 $4$ 在第二和第三项赛事中优于选手 $1$，而 $1$ 在第一和第二项赛事中优于 $2$。

选手 $1$ 在道德上优于选手 $5$，因其在所有赛事中名次均优于 $5$。

选手 $5$ 未在道德上优于选手 $1$，因仅在至少两项赛事中优于选手 $3$，但 $3$ 未在任何两项赛事中优于其他选手。

附加样例

1. $n=10, m=90$，所有排名随机，查询覆盖所有可能。
2. $n=1000, m=1000$，三项赛事排名相同，查询随机。
3. $n=100000, m=10$，第一项赛事排名 $1,2,\ldots,n$，第二项排名 $n,n-1,\ldots,1$，第三项排名随机，查询 $10$ 个，随机生成。

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n, m \leq 100$	$9$
$2$	$n \leq 300, m \leq 100000$	$10$
$3$	$n \leq 1000, m \leq 1000000$	$18$
$4$	$n \leq 100000, m \leq 10$	$27$
$5$	$n \leq 500000, m \leq 1000000$	$36$