Giới hạn thời gian có thay đổi so với đề gốc. Cụ thể là từ 6s lên 9s.

~Dominik~ có một dãy số nguyên dương gồm ~N~ phần tử, ~p_{1}, p_{2}, ..., p_{N}~. Và dãy ~q_{1}, q_{2}, ..., q_{N}~ là dãy số ~p~ sau khi được sắp xếp tăng dần.

Đồng thời, ~Dominik~ còn có một tập hợp ~S~, là tập hợp chứa những bước hoán đổi hợp lệ. Nếu cặp số gồm hai số nguyên dương ~(X, Y)~ và ~(X, Y) \in S~, thì ~Dominik~ có thể đổi vị trí của hai phần tử ở chỉ số ~X~ và ~Y~ cho nhau. Ban đầu, ~S~ là tập hợp rỗng.

Ta định nghĩa một cặp vị trí ~(A, B)~ được xem là liên kết với nhau khi giá trị từ vị trí ~A~ có thể đến được vị trí ~B~ bằng cách chỉ sử dụng những bước hoán đổi hợp lệ. Biết rằng, mỗi bước hoán đổi hợp lệ có thể dùng với số lần và thứ tự bất kì.

Ngoài ra, một tập hợp những vị trí liên kết với vị trí ~A~ là "đám mây" của ~A~. Và một "đám mây" được xem là tốt khi với mọi vị trí ~j~ trong "đám mây" đó, ta có thể đạt được trạng thái ~p_{j} = q_{j}~ khi chỉ dùng những bước hoán đổi hợp lệ.

~Marin~, bạn của ~Dominik~, đưa ra cho anh ~Q~ yêu cầu, và mỗi yêu cầu thuộc một trong bốn loại sau:

• Loại 1: Đổi chỗ hai giá trị ở vị trí ~A~ và ~B~.
• Loại 2: Thêm vào tập ~S~ cặp số ~(A, B)~, cặp số ~(A, B)~ có thể đã xuất hiện trong ~S~.
• Loại 3: Đưa ra câu trả lời cho yêu cầu: Có thể sắp xếp dãy ~p~ theo thứ tự tăng dần khi chỉ dùng những bước hoán đổi hợp lệ hay không?.
• Loại 4: Đưa ra số lượng cặp hai vị trí khác nhau ~(A, B)~ thỏa mãn:
  • ~a.)~ ~A~ và ~B~ không liên kết với nhau.
  • ~b.)~ Cả đám mây của ~A~ và đám mây của ~B~ đều không tốt.
  • ~c.)~ Nếu thêm ~(A, B)~ vào ~S~, thì đám mây của ~A~ trở thành đám mây tốt. (đám mây mới được tạo thành bằng cách liên kết đám mây của ~B~ và đám mây của ~A~)

Cặp số ~(A, B)~ và ~(B, A)~ được xem là như nhau.

INPUT

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 10^{6})~
• Dòng thứ hai gồm ~N~ số nguyên dương ~p_{1}, p_{2}, ..., p_{N}, (1 \le p_{1}, p_{2}, ..., p_{N} \le 10^{6})~
• Theo sau là ~Q~ dòng theo mẫu sau:
  • Đầu dòng là một số nguyên ~T~, loại của truy vấn và ~T \in~ {1, 2, 3, 4}.
  • Nếu ~T~ là ~1~ hoặc ~2~ thì theo sau là hai số nguyên dương ~A~ và ~B~ ~(1 \le A, B \le N, A \neq B)~.

OUTPUT

Mỗi câu trả lời được in trên một dòng

• Với từng truy vấn thuộc loại ~3~ in ra DA nếu có thể sắp xếp dãy ~p~ theo thứ tự tăng dần, in ra NE nếu không thể.
• Với từng truy vấn thuộc loại ~4~ in ra một số nguyên không âm đúng theo yêu cầu đề bài.

Subtask

• Có ~15~ test thỏa mãn: ~N, Q \le 1000~
• Có ~15~ test còn lại không có thêm điều kiện.

Sample 1

Input

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

Output

1 
NE 
0 
DA

Giải thích cho ví dụ 1:

• Câu trả lời cho yêu cầu đầu tiên là ~1~ vì chỉ có cặp vị trí ~(2, 3)~ thỏa mãn các điều kiện trên.
• Câu trả lời cho yêu cầu thứ hai là NE, do hiện tại tập ~S~ đang rỗng nên không thể chuyển số ~2~ và ~3~ đến vị trí cần thiết.
• Ở yêu cầu thứ ba, chỉ thêm ~(2, 3)~ vào ~S~ và không in ra gì cả.
• Câu trả lời cho yêu cầu thứ tư là ~0~ vì vị trí ~2~ đã được liên kết với vị trí ~3~.
• Câu trả lời cho yêu cầu cuối cùng là DA vì có thể sắp xếp dãy số bằng cách áp dụng một bước hoán đổi hợp lệ là ~(2, 3)~.

Sample 2

Input

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

Output

NE 
1 
DA 
0 

Sample 3

Input

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

Output

NE 
2 
NE 
1 
3 
DA