Imeline masin

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

요약

일부가 알려지지 않은 버튼 입력 열을 네 상태 자동기가 읽을 때, 마지막에 켜져 있을 수 있는 전구를 모두 판별합니다.

난이도: 보통10점 중 4점
유형: 시뮬레이션, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Jukul on imeline masin, millel on neli tulukest: punane, roheline, sinine ja kollane. Korraga põleb täpselt üks tuluke. Kui masin tööle panna, siis põleb sellel alguses punane tuluke.

Masinal on lisaks kaks nuppu: $0$ ja $1$ . Nuppe vajutades saab muuta, missugune tuluke põleb:

Kui põleb punane tuluke ja vajutada ükskõik kumba nuppu, siis hakkab põlema roheline tuluke.
Kui põleb roheline tuluke ja vajutada nuppu $0$ , siis hakkab põlema punane tuluke. Kui aga vajutada nuppu $1$ , siis hakkab põlema sinine tuluke.
Kui põleb sinine tuluke ja vajutada nuppu $0$ , siis hakkab põlema kollane tuluke. Kui aga vajutada nuppu $1$ , siis jääb põlema sinine tuluke.
Kui põleb kollane tuluke ja vajutada nuppu $0$ , siis jääb põlema kollane tuluke. Kui aga vajutada nuppu $1$ , siis hakkab põlema punane tuluke.

Juku kirjutas üles ühe nupuvajutuste jada. Tema õde Juta pillas selle paberi poriloiku ja nüüd on mõned sümbolid paberil arusaamatud. Aita Jutal leida kõik võimalused, mis tuluke võiks vajutustejada lõpuks põleda.

입력

Sisendi esimesel real on nupuvajutuste arv $N$ ( $1 \le N \le 10^6$ ).

Teisel real on $N$ tühikutega eraldatud täisarvu, mis on igaüks $0$ , $1$ või $-1$ : nupuvajutuste jada. Arv $0$ tähendab, et vajutati nuppu $0$ . Arv $1$ tähendab, et vajutati nuppu $1$ . Arv $-1$ tähendab, et paber on selle koha pealt märjaks saanud ja Juta ei tea, mis nuppu vajutati: see võis olla $0$ või $1$ .

출력

Väljastada neli rida: üks iga tulukese kohta.

Esimesele reale väljastada 'JAH', kui vajutustejada lõpuks võib põleda punane tuluke, ja 'EI', kui see pole võimalik.

Teisele, kolmandale ja neljandale reale väljastada, kas vajutustejada lõpuks võib põleda roheline, sinine või kollane tuluke.

예제2

예제 1
입력
```
6
1 -1 0 1 0 1
```
예상 출력
```
JAH
EI
JAH
EI
```
예제 2
입력
```
4
-1 -1 -1 -1
```
예상 출력
```
JAH
EI
JAH
JAH
```