Programming Exam

For each query, decide whether two given substrings of S are anagrams, printing DA or NE.

Medium4Prefix sumHash mapStringNo attempts yetTime limit3sMemory limit128 MB

Description

Examples3

Problem

Leticija is preparing for a programming exam. She has solved many tasks, but one is still unsolved, so she is asking you for help.

You are given a word $S$ and $Q$ queries. Each query gives positive integers $A$ , $B$ , $C$ , $D$ . Let $X$ be the word made of the letters of $S$ from position $A$ to position $B$ , and let $Y$ be the word made of the letters from position $C$ to position $D$ .

For each query, decide whether the letters of $Y$ can be rearranged into $X$ .

Input

The first line contains the word $S$ , which consists of lowercase letters of the English alphabet and satisfies $1 \le |S| \le 50000$ . Here $|S|$ is the number of characters in $S$ .

The second line contains the number of queries $Q$ $(1 \le Q \le 50000)$ .

Each of the next $Q$ lines contains four integers $A$ , $B$ , $C$ , $D$ $(1 \le A \le B \le |S|,\ 1 \le C \le D \le |S|)$ .

Output

For each query, print the answer on its own line. Print DA if the letters of $Y$ can be rearranged into $X$ , and NE if they cannot. DA and NE are Croatian for yes and no.

Note

In the third example, the first query has $X$ equal to vovo and $Y$ equal to devo. The second query has $X$ equal to odev and $Y$ equal to devo.