P11340 [COI 2019] TENIS

**译自 [COI 2019](https://hsin.hr/coci/archive/2018_2019/) T4「[TENIS](https://hsin.hr/coci/archive/2018_2019/olympiad_tasks.pdf)」** Vito 十分喜欢打网球。不久，他就会组织一次大规模的锦标赛。这次锦标赛会有 $N$ 名选手参加，编号为从 $1$ 到 $N$。Vito 在过去几年跟踪了这些选手的数据。因此，他确定了这些选手在三种不同的球场：红土，草地和硬地上比赛的能力值。也就是说，对于每种场地，他都按最强到最弱的顺序确定了选手的排名。 Vito 的锦标赛赛制有点与众不同。一共会进行 $N-1$ 轮比赛。在每场比赛中，还没有被淘汰的两名选手会在某种特定的场地上进行比赛。在这种场地上较弱的选手会被淘汰出局。$N-1$ 轮比赛后唯一的胜者就是这次锦标赛的冠军。 Vito 是一个很有影响力的人，可以操纵比赛的结果。即对于每场比赛，Vito 可以选择参赛选手和比赛场地。当然，他只能选择未被淘汰的选手。 Vito 经常更新他收集的数据，他有时会交换在某种场地上两名选手的排名。并且他有很多朋友，有些朋友会问他：「选手 $X$ 是我的外甥，他有机会夺冠吗？」（*wink*），为了回答这些询问，你需要写一个程序帮助 Vito 更新排名，并根据当前时刻 Vito 的排名表回答他朋友的提问。

第一行两个整数 $N,Q$，分别表示选手数和事件数； 接下来三行，每行包含一个 $\{1,2,\ldots , N\}$ 的排列，表示选手在这种特定的球场上的排名，按从最强到最弱的顺序给出。 接下来 $Q$ 行，每行表示一个事件： - `1 X`：表示 Vito 的朋友想知道选手 $X$ 能否夺冠； - `2 P A B`：表示 Vito 意识到需要交换第 $P$ 个排名表中选手 $A$ 和选手 $B$ 的排名位置。

对于每个 `1` 类型的询问输出一行，包含 `DA` 或 `NE`（克罗地亚语中的「是」和「否」）。

### 样例 1 解释 如果所有比赛都在第一种场地上进行，选手 $1$ 会夺冠； 选手 $4$ 夺冠的方式： - 选手 $3$ 和 $4$ 在第三种场地上进行比赛，选手 $4$ 赢了； - 选手 $1$ 和 $2$ 在第一种场地上进行比赛，选手 $1$ 赢了； - 选手 $1$ 和 $4$ 在第三种场地上进行比赛，选手 $4$ 赢了。 在更新第三种场地上的选手排名后（排名变为：$\{2,1,3,4\}$），选手 $4$ 变成了在所有场地上都是最弱的了，因此他不可能夺冠。 ### 数据范围 对于全部数据，$1\le N,Q\le 10^5,1\le X,A,B\le N,1\le P\le 3,A\neq B$。 详细子任务附加限制及分值如下表： |子任务编号|附加限制|分值| |:-:|:-:|:-:| |$1$|$N\le 15,Q\le 10$|$7$| |$2$|$N\le 10^3,Q\le 10$|$11$| |$3$|$Q\le 10$|$12$| |$4$|所有的事件类型都是 `1` 类型|$21$| |$5$|无附加限制|$49$|