프로그래밍 시험

시간 제한3초메모리 제한128 MB

요약

각 질의마다 문자열 S의 두 부분 문자열이 서로 애너그램인지 판정해 DA 또는 NE를 출력한다.

난이도: 보통10점 중 4점
유형: 누적 합, 해시맵, 문자열
정답자: 아직 제출이 없습니다

문제

레티치야는 프로그래밍 시험을 준비하고 있다. 문제를 많이 풀었지만 아직 한 문제가 남아서 너에게 도움을 청했다.

문자열 $S$ 와 $Q$ 개의 질의가 주어진다. 각 질의마다 양의 정수 $A$ , $B$ , $C$ , $D$ 가 주어진다. $S$ 의 $A$ 번째 문자부터 $B$ 번째 문자까지를 이어 붙인 문자열을 $X$ , $C$ 번째 문자부터 $D$ 번째 문자까지를 이어 붙인 문자열을 $Y$ 라고 하자.

각 질의마다 $Y$ 의 문자를 재배열해서 $X$ 를 만들 수 있는지 판단하라.

입력

첫째 줄에 문자열 $S$ 가 주어진다. $S$ 는 영어 소문자로만 이루어져 있고, 길이는 $1 \le |S| \le 50000$ 이다. $|S|$ 는 $S$ 의 문자 개수를 뜻한다.

둘째 줄에 질의의 개수 $Q$ 가 주어진다. $(1 \le Q \le 50000)$

다음 $Q$ 개의 줄에 네 정수 $A$ , $B$ , $C$ , $D$ 가 주어진다. $(1 \le A \le B \le |S|,\ 1 \le C \le D \le |S|)$

출력

각 질의마다 한 줄에 답을 출력한다. $Y$ 를 재배열해서 $X$ 를 만들 수 있으면 DA를, 만들 수 없으면 NE를 출력한다. DA와 NE는 크로아티아어로 각각 예와 아니오를 뜻한다.

힌트

세 번째 예제의 첫 번째 질의에서는 $X$ 가 vovo, $Y$ 가 devo이다. 두 번째 질의에서는 $X$ 가 odev, $Y$ 가 devo이다.

예제3

예제 1
입력
```
kileanimal
2
2 2 7 7
1 4 6 7
```
예상 출력
```
DA
NE
```
예제 2
입력
```
abababba
2
3 5 1 3
1 2 7 8
```
예상 출력
```
DA
DA
```
예제 3
입력
```
vodevovode
2
5 8 3 6
2 5 3 6
```
예상 출력
```
NE
DA
```