Игра <<Делимость>>

시간 제한2초메모리 제한1024 MB

요약

두 선수가 번갈아 카드를 가져가며, 자신이 가져간 카드 합이 3의 배수인 사람이 이기는 게임을 최적으로 둘 때의 결과를 판정한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 게임 이론
정답자: 아직 제출이 없습니다

문제

Как-то раз, разбирая вещи на чердаке, Петя нашел странную игру. В начале игры на поле выкладываются карточки с числами. Затем двое игроков по очереди берут себе по одной карте за ход. Игра заканчивается, когда на поле не остается карточек. Выигрывает тот, у кого сумма чисел на карточках делится на три. В случае если сумма чисел делится на три у обоих игроков, объявляется ничья. Также ничья объявляется, если ни у одного игрока сумма не делится на три.

Петя выяснил, что эта игра была довольно популярна когда-то, и что у некоторых его друзей она тоже есть. Единственное отличие состоит в том, что набор карт у всех разный.

Теперь Пете интересно, каков будет исход партии при оптимальной игре. Помогите ему выяснить это.

입력

Первая строка входного файла содержит натуральное число $n$ --- количество карточек ( $1 \le n \le 50$ ). Следующая строка содержит $n$ целых чисел, разделенных пробелами --- значения, написанные на карточках. Все числа во входном файле не превосходят $1000$ по модулю.

출력

В первой строке выходного файла выведите <<FIRST>>, если при оптимальной игре выигрывает первый игрок, <<SECOND>>, если второй. В случае, если при оптимальной игре случается ничья, выведите <<DRAW>>.

예제2

예제 1
입력
```
2
1 3
```
예상 출력
```
FIRST
```
예제 2
입력
```
3
3 6 9
```
예상 출력
```
DRAW
```