Mirko and Marko are thrilled by the fact that their names differ by only one letter, so they are creating problems based on such similarities. Two sequences of numbers of equal length are said to be "almost equal" if they differ at exactly one position. Two sequences of numbers of equal length are said to be "almost anagrams" if the elements of the first sequence can be reordered in some way such that the resulting sequence is almost equal to the second sequence. For example, the sequences $(1, 3, 2)$ and $(2, 3, 3)$ are almost anagrams because we can reorder the elements of the first sequence to get $(2, 3, 1)$, which differs from the second sequence only at the third position.

You are given a sequence of $n$ integers $x = x_1, x_2, \dots, x_n$ and $q$ queries, where each query consists of two equal-length contiguous subsequences of $x$. For each query, determine whether the two sequences are almost anagrams. In each query, the sequences are given by the indices of their first and last elements. Specifically, for indices $a$ and $b$, $x_a^b$ is the sequence of elements of $x$ starting from the $a$-th element up to the $b$-th element: $x_a^b = x_a, x_{a+1}, \dots, x_b$. Each query consists of two pairs of indices $(a, b)$ and $(c, d)$ describing sequences of equal length, and the answer to the query is "DA" if the sequences $x_a^b$ and $x_c^d$ are almost anagrams, or "NE" otherwise.

Input

The first line contains natural numbers $n$ and $q$ — the length of the sequence $x$ and the number of queries. The next line contains $n$ integers $x_1, x_2, \dots, x_n$ ($0 \le x_j \le 10^9$) — the sequence $x$. Each of the next $q$ lines contains four natural numbers $a, b, c, d$ describing the $j$-th query, where $1 \le a \le b \le n$, $1 \le c \le d \le n$, and $b - a = d - c$.

Output

Print $q$ lines. In the $j$-th line, print the answer to the $j$-th query.

Subtasks

Examples

Input 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

Output 1

DA
NE
DA
DA

Input 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

Output 2

NE
DA
DA
DA
NE