题目描述

Vito 十分喜欢打网球。不久，他就会组织一次大规模的锦标赛。这次锦标赛会有 $n$ 名选手参加，编号为从 $1$ 到 $n$。Vito 在过去几年跟踪了这些选手的数据。因此，他确定了这些选手在三种不同的球场：红土，草地和硬地上比赛的能力值。也就是说，对于每种场地，他都按最强到最弱的顺序确定了选手的排名。

Vito 的锦标赛赛制有点与众不同。一共会进行 $n-1$ 轮比赛。在每场比赛中，还没有被淘汰的两名选手会在某种特定的场地上进行比赛。在这种场地上较弱的选手会被淘汰出局。$n-1$ 轮比赛后唯一的胜者就是这次锦标赛的冠军。

Vito 是一个很有影响力的人，可以操纵比赛的结果。即对于每场比赛，Vito 可以选择参赛选手和比赛场地。当然，他只能选择未被淘汰的选手。

Vito 经常更新他收集的数据，他有时会交换在某种场地上两名选手的排名。并且他有很多朋友，有些朋友会问他：“选手 $x$ 是我的外甥，他有机会夺冠吗？”，为了回答这些询问，你需要写一个程序帮助 Vito 更新排名，并根据当前时刻 Vito 的排名表回答他朋友的提问。

输入格式

第一行包含两个整数 $n$ 和 $Q$ 表示选手数量和事件的数量。

接下来三行，每行一个 $\{1,2,\dots,n\}$ 的排列，表示某一种场地的排名，从左往右，战斗力逐渐变弱。

接下来 $Q$ 行，每行的输入为以下两种中的一种：

1. 1 x 表示询问 $x$ 能否赢得比赛；
2. 2 P A B 表示 Vito 交换了第 $P$ 种场地中选手 $A$ 和 $B$ 的排名。

输出格式

对于每一个询问，输出 DA 或者 NE。（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

样例说明

样例一解释：

对于第一个事件，只需都在场地一进行比赛。

对于第二个事件，比赛安排如下：

• 选手 $3$ 和选手 $4$ 在第三个场地比赛——选手 $4$ 胜。

• 选手 $1$ 和选手 $2$ 在第一个场地比赛——选手 $1$ 胜。

• 选手 $1$ 和选手 $4$ 在第三个场地比赛——选手 $4$ 胜。

因此选手 $4$ 可以获得最终胜利。

对于第三个事件，交换后选手 $4$ 成了最弱的。

对于第四个时间，选手 $4$ 无论在哪个场地都是最弱的，因此他不能获得最终胜利。

数据规模与约定

本题按照原题设置 Subtask。

Subtask	Points	additional constraints
1	7	$n \le 15$，$Q\le 10$
2	11	$n\le 10^3$，$Q\le10$
3	12	$Q\le10$
4	21	所有的事件均为第一种
5	49	无特殊性质

对于 $100\%$ 的数据，$1\le n,Q\le10^5$。

对于操作 $1$，保证 $1\le x \le n$。

对于操作 $2$，保证 $1\le P\le3$ 且 $A!=B$。

题目来源

题目译自 COCI2018-2019 Final T4 TENIS。