Mirko 和 Marko 对他们的名字仅有一个字母不同这一事实感到非常兴奋，因此他们设计了基于这种相似性的题目。对于两个长度相等的数字序列，如果它们在恰好一个位置上的值不同，我们称它们是几乎相等的。对于两个长度相等的数字序列，如果我们能将第一个序列的元素重新排列，使得得到的序列与第二个序列几乎相等，我们就称这两个序列是几乎变位词。例如，序列 $(1, 3, 2)$ 和 $(2, 3, 3)$ 是几乎变位词，因为我们可以将第一个序列的元素重新排列得到序列 $(2, 3, 1)$，而它与第二个序列仅在第三个位置上不同。

给定一个由 $n$ 个整数组成的序列 $x = x_1, x_2, \dots, x_n$ 以及 $q$ 个询问。每个询问包含序列 $x$ 的两个长度相同的连续子序列。对于每个询问，判断这两个子序列是否为几乎变位词。在每个询问中，子序列由其首尾元素的下标给出。具体来说，对于下标 $a$ 和 $b$，$x_a^b$ 表示序列 $x$ 中从第 $a$ 个元素到第 $b$ 个元素的子序列：$x_a^b = x_a, x_{a+1}, \dots, x_b$。每个询问由两对下标 $(a, b)$ 和 $(c, d)$ 组成，它们描述了两个长度相同的子序列。如果子序列 $x_a^b$ 和 $x_c^d$ 是几乎变位词，则该询问的答案为 “DA”，否则为 “NE”。

输入格式

第一行包含两个正整数 $n$ 和 $q$ — 序列 $x$ 的长度和询问的次数。

第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($0 \le x_j \le 10^9$) — 序列 $x$。

接下来的 $q$ 行中，第 $j$ 行包含四个正整数 $a, b, c, d$，描述第 $j$ 个询问，满足 $1 \le a \le b \le n$，$1 \le c \le d \le n$，且 $b - a = d - c$。

输出格式

输出 $q$ 行。在第 $j$ 行中输出第 $j$ 个询问的答案。

子任务

样例

输入样例 1

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

输出样例 1

DA
NE
DA
DA

输入样例 2

10 5
3 3 3 1 2 2 1 2 2 1
2 3 5 6
9 10 5 6
5 6 4 5
5 8 3 6
3 7 5 9

输出样例 2

NE
DA
DA
DA
NE