intervale

Cosmin and Lensu were strolling on the dangerous beaches of Egypt when they spotted a shark carrying a string s. Since Harry Potter had taught them how to communicate with animals, Cosmin and Lensu tamed the shark, making it give them the string of characters. They want to keep it, but the shark said it would take it back if they did not answer several questions posed by it.

Task

Given a string s and $T$ queries of the form $left, \ right$, the shark asks if the letters in the sequence $[left, \ right]$ of the string s can be rearranged to form a palindromic word.

Input data

The first line contains the natural number $T$, and the second line contains the string s, representing the number of questions posed by the shark. The next $T$ lines contain two numbers, $left$ and $right$, representing the start and end of the sequence in question. The numbers on the same line are separated by a space.

Output data

Print $T$ lines, each line $i \ (1 ≤ i ≤ T)$ containing a single word, $“DA”$ or $“NU”$, the answer to the $i$-th question posed by the shark.

Constraints and clarifications

• The string s consists only of lowercase English letters;
• $2 \leq |S| \leq 5,000,000$, where $|S|$ represents the length of the given string;
• $1 \leq T \leq 1,000,000$;
• $1 \leq left \leq right \leq |S|$;

Note

Due to the very large input data, the following instructions should be used at the beginning of the program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example

stdin

2
zabac
2 4
3 5

stdout

DA
NU

Explanation

The letters in the sequence [2, 4] already form a palindromic word in the given order, so the answer to the first question is $“DA”$.
The letters in the sequence [3, 5], specifically a, b, and c, cannot be rearranged to form a palindromic word. Therefore, the answer to the second question is $“NU”$.