题目背景

译自 Izborne Pripreme 2018 (Croatian IOI/CEOI Team Selection) D1T2。$\texttt{1s,1G}$。

关于题目名：原文如此（「题目」的克罗地亚语是「zadatak」）。

题目描述

定义长度均为 $k$ 的数列 $[a_1,a_2,\ldots,a_k]$ 和 $[b_1,b_2,\ldots,b_k]$ 几乎相等，当且仅当存在恰好一个 $1\le p\le k$，使得 $a_p\neq b_p$。

定义长度均为 $k$ 的数列 $[a_1,a_2,\ldots,a_k]$ 和 $[b_1,b_2,\ldots,b_k]$ 相似，当且仅当可以通过重排使得 $a,b$ 几乎相等。

给定长度为 $n$ 的数列 $[a_1,a_2,\ldots,a_n]$。$m$ 次询问，每次询问给定 $l_1,r_1,l_2,r_2$，问 $[a_{l_1},a_{{l_1}+1},\ldots,a_{r_1}]$ 与 $[a_{l_2},a_{{l_2}+1},\ldots,a_{r_2}]$ 是否相似。

输入格式

第一行，两个正整数 $n,m$。

第二行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，每行四个正整数 $l_1,r_1,l_2,r_2$，描述一次询问。保证 $r_1-l_1=r_2-l_2$。

输出格式

对于每个询问，输出一行：

如果答案为是的话，输出 $\texttt{DA}$（克罗地亚语「是」）；

否则输出 $\texttt{NE}$（克罗地亚语「否」）。

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

DA
NE
DA
DA

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

NE
DA
DA
DA
NE

提示

对于 $100\%$ 的数据，保证：

• $1\le n,m\le 10^5$；
• $0\le a_i\le 10^9$；
• $1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$；
• $r_1-l_1=r_2-l_2$。