Dãy Học Sinh

Trường Học Mùa Đông kết thúc bằng một điệu nhảy truyền thống. Có \(n\) học sinh tham gia, mỗi học sinh có nhãn duy nhất từ \(1\) đến \(n\).

Ban đầu, nhạc trưởng Krešo sắp xếp các học sinh thành một vòng tròn sao cho mỗi học sinh nắm tay hai học sinh khác (tức là một chuỗi vòng). Alenka tự hỏi liệu có thể "phá vòng" bằng cách để đúng một cặp hai học sinh kề nhau buông tay (tức cắt một vị trí trên vòng) sao cho thứ tự tuyến tính mới của các học sinh (từ một đầu tới đầu kia của đoạn vừa mở) là tăng dần theo nhãn (tức là 1,2,3,…,n). Ví dụ, nếu thứ tự trên vòng (theo chiều đi vòng) là 3 4 1 2 thì có thể cắt giữa 4 và 1 để được dãy 1 2 3 4 --- hợp lệ. Nhưng nếu thứ tự là 2 1 4 3 thì không có cách cắt nào để được dãy tăng dần.

Trong đêm khiêu vũ, Krešo sẽ đưa ra \(q\) chỉ thị. Mỗi chỉ thị yêu cầu hoán đổi vị trí hai học sinh (theo nhãn của họ). Sau mỗi lần hoán đổi, bạn cần trả lời câu hỏi của Alenka: liệu có thể phá vòng bằng đúng một lần buông tay để được dãy tăng dần hay không.

Input

Dòng đầu chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 300000\)) --- số học sinh và số lần hoán vị.

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) --- thứ tự các nhãn học sinh trên vòng theo chiều kim đồng hồ (hoặc ngược chiều tùy quy ước). Các \(a_i\) là một hoán vị của \(1\dots n\).

Mỗi trong \(q\) dòng tiếp theo chứa hai số nguyên \(x_i, y_i\) (\(1 \le x_i, y_i \le n\), \(x_i \ne y_i\)) --- nhãn hai học sinh sẽ hoán đổi vị trí trong thao tác thứ \(i\).

Output

Sau mỗi thao tác in ra một dòng; nếu sau thao tác đó tồn tại một cách cắt vòng (tức buông tay tại đúng một cặp kề nhau) để nhận được dãy \(1,2,\dots,n\) theo thứ tự, in DA; ngược lại in NE.:

Example

5 2
2 3 4 5 1
1 3
3 1

NE
DA

4 2
2 3 1 4
4 2
3 4

NE
DA

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

NE
NE
DA
NE
DA

Scoring

• Subtask 1 (20 điểm): \(n, q \le 500\).
• Subtask 2 (30 điểm): \(n, q \le 5000\).
• Subtask 3 (50 điểm): Không có ràng buộc thêm.