You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 正在准备编程考试，向你寻求帮助。

给定字符串 $S$ 及 $Q$ 次查询。

每次查询给定正整数 $A,B,C,D$，令字符串 $X$ 由 $S$ 中位置（字符串的位置都从 $1$ 开始计数） $A$ 到 $B$ 之间的字符组成，$Y$ 由 $S$ 中位置 $C$ 到 $D$ 之间的字符组成，你需要判断能否以某种方式重新排列 $Y$ 中的字符使 $X$ 与 $Y$ 相同。

若可以，则输出 DA，否则输出 NE。

输入格式

从 program.in 文件读入数据。

第一行输入包含字符串 $S(1 \le |S| \le 50000)$，由英文字母的小写字母组成。

第二行输入包含正整数 $Q(1 \le Q \le 50000)$。接下来的 $Q$ 行，每行给定正整数 $A,B,C,D$，描述一次询问。

输出格式

输出到 program.out 文件。

对于每个查询，如果可能，输出 DA；如果不可能，则输出 NE。

样例

kileanimal
2
2 2 7 7
1 4 6 7

DA
NE

abababba
2
3 5 1 3
1 2 7 8

DA
DA

vodevovode
2
5 8 3 6
2 5 3 6

NE
DA

说明/提示

样例 1 解释

第一次询问，X="i"，Y="i"，显然 $Y$ 就是 $X$，输出 DA。

第二次询问，X="kile"，Y="ni"，$Y$ 的长度和 $X$ 不相同，不管怎么排列都不可能变成 $X$，所以输出 NE。

数据范围

对于 $50\%$ 的数据满足，$1 \le |S|,Q \le 10^3$。

对于 $100\%$ 的数据满足，$1 \le |S|,Q \le 50000, 1 \le A,B,C,D \le |S|$，并且保证字符串中的所有字符都是小写字母。