Vito rất yêu thích quần vợt. Sắp tới, anh sẽ tổ chức một giải đấu lớn với ~N~ người chơi tham gia, đánh số ~1, 2, ..., N~. Vito đã theo dõi thống kê của các người chơi trong vài năm qua và đã xác định được sức mạnh của họ trên ba mặt sân khác nhau: sân đất nện, sân cỏ và sân cứng. Cụ thể, đối với mỗi mặt sân, anh đã xác định danh sách xếp hạng của các người chơi, từ mạnh nhất đến yếu nhất trên mặt sân đó.

Luật của giải đấu của Vito khá đặc biệt. Tổng cộng sẽ có ~N - 1~ trận đấu được diễn ra. Trong mỗi trận đấu, hai người chơi chưa bị loại sẽ thi đấu với nhau trên một mặt sân cụ thể. Người chơi yếu hơn trên mặt sân đó sẽ thua trận đấu và bị loại khỏi giải đấu. Người duy nhất còn lại trong giải đấu sau tất cả ~N - 1~ trận đấu sẽ là người chiến thắng của giải đấu.

Vito là một người có ảnh hưởng và có thể điều chỉnh kết quả của giải đấu. Cụ thể, trong mỗi trận đấu của giải đấu, Vito có thể chọn cả hai người chơi và mặt sân của trận đấu. Tất nhiên, anh chỉ có thể chọn những người chơi chưa bị loại.

Vito thường xuyên cập nhật thống kê trong sổ sách của mình bằng cách đôi khi hoán đổi vị trí của hai người chơi trong danh sách xếp hạng của một mặt sân cụ thể. Bên cạnh đó, Vito có nhiều bạn bè, một số trong số họ đến gặp anh với những câu hỏi như thế này: Người chơi ~X~ là cháu của tôi, liệu có khả năng anh ta sẽ thắng giải đấu không (nháy mắt)? Để trả lời các câu hỏi của họ, Vito đã đưa ra cho bạn một đề nghị khó từ chối. Bạn cần viết một chương trình cập nhật danh sách xếp hạng và trả lời các câu hỏi của bạn bè Vito dựa trên danh sách xếp hạng tại thời điểm đó.

Input

• Dòng đầu tiên chứa các số nguyên ~N~ và ~Q~ ~(1 \leq N, Q \leq 100 000)~, số người chơi và số sự kiện.
• Mỗi trong ba dòng tiếp theo chứa một hoán vị của các số nguyên ~1, 2, …, N~ — thứ hạng của người chơi trên một mặt sân cụ thể, từ mạnh nhất đến yếu nhất.
• Mỗi dòng trong số ~Q~ dòng sau thuộc một trong các loại sau:

~1 X~, với ~1 \leq X \leq N~ — Bạn của Vito muốn biết liệu người chơi X có thể thắng giải đấu không. ~2 P A B~, với ~1 \leq P \leq 3~ và ~1 \leq A \ne B \leq N~ — Vito nhận ra rằng anh nên hoán đổi vị trí của người chơi ~A~ và ~B~ trong danh sách xếp hạng thứ ~P~.

Output

Đối với mỗi truy vấn loại ~1~, in ~DA~ hoặc ~NE~ (từ tiếng Croatia cho “YES” và “NO”) trong một dòng riêng biệt.

Chú thích

• ~7 \%~ số test thỏa mãn ~N \leq 15, Q \leq 10~.
• ~11 \%~ số test thỏa mãn ~N \leq 1000, Q \leq 10~.
• ~12 \%~ số test thỏa mãn ~Q \leq 10~.
• ~21 \%~ số test thỏa mãn chỉ có truy vấn loại ~1~.

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

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

Chú thích

Trong test đầu tiên, Nếu tất cả các trận đấu đều diễn ra trên mặt sân thứ nhất, người chơi 1 sẽ thắng giải đấu.

Ví dụ về một giải đấu mà người chơi 4 thắng:

• Người chơi 3 và 4 thi đấu trên mặt sân thứ ba - người chơi 4 thắng.
• Người chơi 1 và 2 thi đấu trên mặt sân thứ nhất - người chơi 1 thắng.
• Người chơi 1 và 4 thi đấu trên mặt sân thứ ba - người chơi 4 thắng.
• Sau khi cập nhật danh sách xếp hạng của mặt sân thứ ba (thứ hạng mới: 2 1 3 4), người chơi 4 là người yếu nhất trên tất cả các mặt sân và do đó không thể thắng giải đấu.