Vito 非常喜欢网球。不久后，他将组织一场有 $N$ 名选手参加的大型比赛，选手编号为 $1, 2, \dots, N$。Vito 收集了过去几年中这些选手的统计数据。因此，他确定了他们在三种不同场地表面（红土、草地和硬地）上的实力。具体来说，对于每种场地，他都确定了选手的排名表，从最强到最弱。

Vito 的比赛规则非常独特。总共将进行 $N - 1$ 场比赛。在每场比赛中，两名尚未被淘汰的选手将在特定的场地表面上进行对决。在该场地上实力较弱的选手将输掉比赛并被淘汰。在所有 $N - 1$ 场比赛结束后，唯一留在比赛中的选手将成为冠军。

Vito 是一个有影响力的人，可以操纵比赛的结果。也就是说，对于比赛的每一场对决，Vito 都可以自由选择参赛的两名选手以及比赛的场地表面。当然，他只能选择尚未被淘汰的选手。

Vito 经常更新他书中的统计数据，有时他会交换某个场地排名表中两名选手的位置。此外，Vito 有很多朋友，其中一些人会带着这样的问题来找他：“选手 $X$ 是我的侄子，他有没有可能赢得比赛？”为了回答他们的提问，Vito 向你提出了一个难以拒绝的提议。你应该编写一个程序，根据当时的排名表更新数据并回答 Vito 朋友们的问题。

输入格式

第一行包含两个整数 $N$ 和 $Q$（$1 \le N, Q \le 100\,000$），分别表示选手人数和事件数量。

接下来的三行，每行包含一个 $\{1, 2, \dots, N\}$ 的排列——表示选手在某种特定场地表面上的排名，从最强到最弱。

接下来的 $Q$ 行，每行是以下类型之一：

• 1 X，其中 $1 \le X \le N$ —— Vito 的朋友想知道选手 $X$ 是否有可能赢得比赛。
• 2 P A B，其中 $1 \le P \le 3$ 且 $1 \le A \neq B \le N$ —— Vito 决定在第 $P$ 个排名表中交换选手 $A$ 和 $B$ 的位置。

输出格式

对于每个类型为 1 的询问，在单独的一行中输出 DA（克罗地亚语中的“是”）或 NE（克罗地亚语中的“否”）。

子任务

样例

输入样例 1

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

输出样例 1

DA
DA
NE

输入样例 2

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

输出样例 2

DA
NE
NE
DA

说明

第一个样例解释：

如果所有比赛都在第一种场地表面上进行，选手 1 将赢得比赛。

以下是选手 4 赢得比赛的一个对阵示例：

• 选手 3 和选手 4 在第三种场地表面上比赛——选手 4 获胜。
• 选手 1 和选手 2 在第一种场地表面上比赛——选手 1 获胜。
• 选手 1 和选手 4 在第三种场地表面上比赛——选手 4 获胜。

在更新第三种场地表面的排名表（新排名为：2 1 3 4）后，选手 4 在所有场地表面上都是最弱的，因此无法赢得比赛。