Алиса и Боб играют в игру.
Изначально у них есть строка \(s\), состоящая только из символов 0 и 1.
Алиса и Боб ходят по очереди: Алиса делает первый ход, второй делает Боб, третий ход делает Алиса, и так далее. Во время своего хода игрок должен выбрать два соседних различных символа строки \(s\) и удалить их. Например, если \(s = 1011001\), тогда возможны следующие ходы:
- удалить \(s_1\) и \(s_2\): \(\textbf{10}11001 \rightarrow 11001\);
- удалить \(s_2\) и \(s_3\): \(1\textbf{01}1001 \rightarrow 11001\);
- удалить \(s_4\) и \(s_5\): \(101\textbf{10}01 \rightarrow 10101\);
- удалить \(s_6\) и \(s_7\): \(10110\textbf{01} \rightarrow 10110\).
Если игрок не может сделать ход — он проигрывает. Оба игрока играют оптимально. Вам нужно определить, сможет ли Алиса выиграть.
Выходные данные
На каждый набор входных данных выведите ответ в отдельной строке.
Если Алиса может выиграть, выведите DA в любом регистре. Иначе выведите NET в любом регистре.
Примечание
В первом наборе входных данных после хода Алисы строка \(s\) станет пустой и Боб не сможет сделать ход.
Во втором наборе входных данных Алиса не может сделать ход изначально.
В третьем наборе входных данных после хода Алисы строка \(s\) превратится в \(01\). А после хода Боба строка \(s\) станет пустой и Алиса не сможет сделать ход.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
01
1111
0011
|
DA
NET
NET
|