You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

译自 COI 2019 T4「TENIS」

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（克罗地亚语中的「是」和「否」）。

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

DA
DA
NE

6 7
4 6 1 5 3 2
5 1 4 2 6 3
4 6 1 5 2 3
1 2
2 2 4 5
1 1
2 2 4 5
2 2 5 6
1 2
1 1

DA
NE
NE
DA

提示

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

详细子任务附加限制及分值如下表：