信息学冬令营以一场传统舞蹈结束。共有 $n$ 名学生参加。每名学生都有一个 $1$ 到 $n$ 之间的唯一编号。

首先，指挥 Krešo 命令学生们围成一个圆圈，使得每名学生都与另外两名学生手拉手。

Alenka 想知道，是否可以通过让恰好一对相邻的学生松开手，从而将圆圈断开，使得断开后形成的学生序列按其编号排序。例如，如果他们的顺序是 $3\ 4\ 1\ 2$，那么可以在编号为 $4$ 和 $1$ 的学生之间断开圆圈；但如果他们的顺序是 $2\ 1\ 4\ 3$，则无法通过这种方式断开圆圈。

在夜晚，Krešo 将给出 $q$ 条指令。在每条指令中，他将命令两名学生交换位置。每次交换后，你需要帮助 Alenka 回答她的问题。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 300\,000$)，分别表示学生人数和交换次数。

第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le n$)，描述了学生在圆圈中的初始位置。

接下来的 $q$ 行，每行包含两个整数 $x_i, y_i$ ($1 \le x_i, y_i \le n, x_i \neq y_i$)，描述了 Krešo 的第 $i$ 条指令，即编号为 $x_i$ 和 $y_i$ 的学生交换位置。

输出格式

在 $q$ 行中的第 $i$ 行，输出执行完第 $i$ 次交换后 Alenka 问题的答案。如果答案是肯定的，输出 DA，否则输出 NE。

子任务

样例

输入格式 1

5 2
2 3 4 5 1
1 3
3 1

输出格式 1

NE
DA

输入格式 2

4 2
2 3 1 4
4 2
3 4

输出格式 2

NE
DA

说明

第二个样例的解释： 学生在开始时、第一次交换后以及第二次交换后的状态。

输入格式 3

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

输出格式 3

NE
NE
DA
NE
DA