Cho mảng vòng ~a~ độ dài ~n~, mỗi phần tử ~a_i~ ~(2 \le i < n)~ nằm kế bên hai phần tử ~a_{i-1}~ và ~a_{i+1}~, phần tử ~a_1~ kế bên hai phần tử ~a_2~ và ~a_n~, phần tử ~a_n~ kế bên hai phần tử ~a_{n-1}~ và ~a_1~. Các giá trị ~a_i~ nằm trong khoảng từ ~1~ đến ~n~ và đôi một khác nhau.

Có ~q~ truy vấn, mỗi truy vấn bao gồm hai chỉ số ~x~ và ~y~, yêu cầu thực hiện hoán đổi vị trí hai phần tử mang giá trị ~x~ và ~y~, sau đó xác định xem có tồn tại chỉ số ~j~ thỏa mãn dãy ~a_j,a_{j+1},...,a_n,a_1,a_2,...a_{j-1}~ là dãy tăng dần hay không.

Lưu ý rằng thay đổi của việc thực hiện hoán đổi vị trí ở các truy vấn trước đó vẫn được giữ nguyên cho các truy vấn tiếp theo.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 3.10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le n)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ~(1 \le x,y \le n; \; x \neq y)~ thể hiện truy vấn.

Output

• Với mỗi truy vấn, nếu tồn tại chỉ số ~j~ thỏa mãn, in ra ~\text{DA}~, ngược lại in ra ~\text{NE}~.

Samples

Sample Input 1

5 2
2 3 4 5 1
1 3
3 1

Sample Output 1

NE
DA

Sample Input 2

4 2
2 3 1 4
4 2
3 4

Sample Output 2

NE
DA

Sample Input 3

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

Sample Output 3

NE
NE
DA
NE
DA

Scoring

• Subtask ~1~ với ~30\%~ số điểm: ~n,q \le 500~
• Subtask ~2~ với ~30\%~ số điểm: ~n,q \le 5000~
• Subtask ~3~ với ~40\%~ số điểm: Không có ràng buộc gì thêm

Clarification

Hình ảnh minh họa việc hoán đổi vị trí trong ví dụ thứ hai: