Vito loves tennis. Soon, he will organize a huge tournament with $N$ participating players, denoted $1,2,\dots ,N$. Vito has followed the players' statistics in the last couple of years. Thus, he has determined their strengths 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.

Input Specification

The first line contains integers $N$ and $Q$ $(1\le N,Q\le 100000)$, the number of players and the number of events.

Each of the next three lines contains a permutation of integers $\{1,2,\dots ,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\le X\le N$ — Vito's friend wants to know if player $X$ can win the tournament.

• 2 P A B, where $1\le P\le 3$ and $1\le A\ne B\le N$ — Vito has realized that he should swap the positions of players $A$ and $B$ in the $P^{\text{th}}$ ranking list.

Output Specification

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

Constraints

Subtask	Points	Constraints
1	7	$N\le 15,Q\le 10$
2	11	$N\le 1000,Q\le 10$
3	12	$Q\le 10$
4	21	All events are of type 1.
5	49	No additional constraints.

Sample Input 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

Sample Output 1

DA
DA
NE

Explanation of Sample Output 1

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.

Sample Input 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

Sample Output 2

DA
NE
NE
DA