题目描述

Vito loves tennis. Soon, he will organize a huge tournament with N participating players, denoted 1, 2, ..., N. Vito has followed the players' statistics in the last couple of years. Thus, he has determined their strenghts on three different court surfaces: clay, grass, and hardcourt. Namely, for each surface he has determined the players' ranking list, from the strongest to the weakest player on that surface.

The rules of Vito's tournament are quite unusual. A total of N – 1 matches will be played. In each match, two players that have not yet been eliminated will play against each other on a particular court surface. The player who is weaker on that surface will lose the match and thus be eliminated from the tournament. The only player who remains in the tournament after all N – 1 matches will be the winner of the tournament.

Vito is an influential man and can manipulate the outcome of the tournament. Namely, for each match of the tournament, Vito can choose both players and the court surface of the match. Of course, he can only choose players which have not been eliminated yet.

Vito often updates the statistics in his books in such a way that he sometimes swaps the positions of two players in a particular surface's ranking list. Besides, Vito has a lot of friends, some of which come to him with questions like this: Player X is my nephew, is there any chance he will win the tournament (wink, wink)? To answer their queries, Vito has made you an offer which is hard to refuse. You should write a program which will update the ranking lists and answer the questions of Vito's friends based on the ranking lists at that moment.

维托喜欢网球。很快，他将组织一场有 N 个参赛选手参加的大型锦标赛，记为 1、2、 ...，N. Vito 在过去几年一直关注球员的统计数据。因此，他确定了他们的 三种不同球场表面的优势：红土、草地和硬地。也就是说，对于他有的每个表面 确定了玩家的排名名单，从那个表面上的最强到最弱的玩家。

维托的比赛规则很不寻常。总共将进行 N – 1 场比赛。每一个 比赛中，两名尚未被淘汰的球员将在特定球场上进行比赛 表面。在该表面上较弱的玩家将输掉比赛并因此被淘汰出局 比赛。在所有 N - 1 场比赛之后唯一留在比赛中的球员将成为获胜者 的比赛。

维托是一个有影响力的人，可以操纵比赛的结果。即，对于每场比赛 比赛中，维托既可以选择球员，也可以选择比赛场地。当然，他可以 只选择尚未被淘汰的玩家。

维托经常更新他书中的统计数据，以至于他有时会交换 特定表面排名列表中的两名玩家。此外，维托有很多朋友，其中一些来了 问他这样的问题：球员X是我的侄子，他有没有机会赢得比赛 （眨眼眨眼）？为了回答他们的疑问，Vito 向您提供了一个难以拒绝的报价。你应该 编写一个程序，它会更新排名列表并根据以下内容回答 Vito 朋友的问题 那一刻的排行榜。

输入格式

The first line contains integers N and Q (1 ≤ N, Q ≤ 100 000), the number of players and the number of events.

Each of the next three lines contains a permutation of integers {1, 2, …, N} — the ranking of players on a particular court surface, from the strongest to the weakest one. Each of the following Q lines is of one of the following types:

• “1 X”, where 1 ≤ X ≤ N — Vito's friend wants to know if player X can win the tournament.

• “2 P A B”, where 1 ≤ P ≤ 3 and 1 ≤ A ≠ B ≤ N — Vito has realised that he should swap the positions of players A and B in the P th ranking list.

第一行包含整数 N 和 Q (1 ≤ N, Q ≤ 100 000)，玩家人数和人数 的事件。

接下来的三行中的每一行都包含整数 {1, 2, ..., N} 的排列——玩家的排名 在特定的球场表面上，从最强到最弱。 以下每个 Q 行都是以下类型之一：

• “1 X”，其中 1 ≤ X ≤ N — Vito 的朋友想知道玩家 X 是否能赢得比赛。

• “2 P A B”，其中 1 ≤ P ≤ 3 和 1 ≤ A ≠ B ≤ N — Vito 意识到他应该交换 玩家 A 和 B 在 P 中的位置 排名榜。

输出格式

For each query of type 1, output “DA” or “NE” (Croatian words for “YES” and “NO”) in a separate line.

样例 #1

样例输入 #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

样例输入 #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

提示

First sample description:

If all matches are played on the first court surface, player 1 will win the tournament.

Example of a tournament where player 4 wins:

• Players 3 and 4 play on the third court surface – player 4 wins.

• Players 1 and 2 play on the first court surface – player 1 wins.

• Players 1 and 4 play on the third court surface – player 4 wins.

After updating the third court surface's ranking list (new ranking: 2 1 3 4), player 4 is the weakest on all surfaces and thus cannot win the tournament.

如果所有比赛都在第一个场地进行，球员 1 将赢得比赛。

球员 4 获胜的锦标赛示例：

• 球员 3 和 4 在第三个场地上比赛 – 球员 4 获胜。

• 球员 1 和 2 在第一个场地上比赛——球员 1 获胜。

• 球员 1 和 4 在第三个场地上比赛——球员 4 获胜。

更新了第三球场的排名表（新排名：2 1 3 4）后，球员4是最弱的 表面，因此无法赢得比赛。