Vito loves tennis. Soon, he will organize a huge tournament with participating players, denoted . 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 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 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 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 and , the number of players and the number of events.
Each of the next three lines contains a permutation of integers — the ranking of players on a particular court surface, from the strongest to the weakest one.
Each of the following lines is of one of the following types:
1 X
, where — Vito's friend wants to know if player can win the tournament.2 P A B
, where and — Vito has realized that he should swap the positions of players and in the ranking list.
Output Specification
For each query of type , output DA
or NE
(Croatian words for "YES" and "NO") in a separate
line.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 7 | |
2 | 11 | |
3 | 12 | |
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 will win the tournament. Example of a tournament where player wins:
- Players and play on the third court surface – player wins.
- Players and play on the first court surface – player wins.
- Players and play on the third court surface – player wins.
After updating the third court surface's ranking list (new ranking: ), player 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
Comments