P12768 [POI 2018 R3] 三人编程锦标赛 Triinformathlon

翻译来自于 [LibreOJ](https://loj.ac/p/5076)。

**题目译自 [XXV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi25-3/dashboard/) [Turniej trójinformatyczny](https://szkopul.edu.pl/problemset/problem/URPMk7vthz60i1J3MT3XbIIO/statement/)** **请注意本题的空间限制。** 拜托尼亚的程序员深受国民敬仰。因此，近年来的电视节目《三人编程锦标赛》收视率屡创新高。本届锦标赛有 $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$ 个查询的答案。

**样例 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$ |