시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 64 MB 44 28 24 68.571%

문제

Little Leticija is preparing for a programming exam. Even though she has solved a lot of tasks, there’s one still left unsolved, so she is asking you for help. You are given the word S and Q queries. In each query, you are given positive integers A, B, C and D. Let’s say that word X consists of letters between positions A and B in word S, and word Y from letters between positions C and D in word S. For each query, you must answer if it is possible to somehow rearrange the letters in word Y and obtain word X.

입력

The first line of input contains the word S (1 ≤ |S| ≤ 50 000). |S| denotes the number of characters in word S, which consists of lowercase letters of the English alphabet. The second line of input contains the positive integer Q (1 ≤ Q ≤ 50 000).

Each of the following Q lines contains four integers A, B, C i D (1 ≤ A ≤ B ≤ |S| and 1 ≤ C ≤ D ≤ |S|) from the task.

출력

For each query, output “DA” (Croatian for yes) if it is possible, and “NE” (Croatian for no) if it is not.

예제 입력 1

kileanimal
2
2 2 7 7
1 4 6 7

예제 출력 1

DA
NE

예제 입력 2

abababba
2
3 5 1 3
1 2 7 8

예제 출력 2

DA
DA

예제 입력 3

vodevovode
2
5 8 3 6
2 5 3 6

예제 출력 3

NE
DA

힌트

Clarification​ ​of​ ​the​ ​third​ ​test​ ​case: In the first query, X=”vovo”, and Y=”devo”. In the second query, X=”odev”, and Y=”devo”.