题目描述

译自 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$。

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