캠프파이어

마비노기의 캠프파이어는 특유의 따뜻한 분위기로 많은 유저들의 사랑을 받고 있다. 마을에서나, 던전에서나, 유저들이 모여서 대화를 나누는 곳에는 언제나 캠프파이어가 함께 했다. 하지만, 캠프파이어 간의 간격이 너무 가깝다면 큰불로 번질 위험성이 있다고 한다. 그렇기 때문에 이미 설치된 캠프파이어의 근처에 새 캠프파이어를 설치해달라는 요청은 거절되어야 한다. 쏟아지는 캠프파이어 설치 요청을 받아 중재하는 프로그램을 만들어보자.

캠프파이어의 위치는 이차원 평면상의 좌표 $(x, y)$로 표현된다. 각 캠프파이어 간의 직선거리는 최소 $5$ 이상이 되어야 하며, 다른 캠프파이어와의 직선거리가 5보다 가까워질 수 있는 설치 요청은 모두 거절되어야 한다. 시각 $t$에 설치된 캠프파이어는 시각 $t + 300$에 꺼진다. 이미 설치되어있던 캠프파이어를 끄는 처리는 새 캠프파이어의 설치 요청보다 항상 먼저 처리된다. $t = 10$, $(x, y) = (1, 3)$에 캠프파이어가 설치되었다면, $t = 310$이 되는 시점에 설치된 캠프파이어가 꺼지므로, $t = 310$, $(x, y) = (2, 4)$에 캠프파이어를 설치할 수 있다.

입력 형식

입력의 첫 줄에는 캠프파이어 설치를 희망하는 요청의 총 개수 $N$($1 \le N \le 100\,000$)이 주어진다. 이어지는 $N$줄에는 요청시각을 나타내는 정수 $t$($0 \le t \le 10\,000$)와 설치 지점의 좌표를 나타내는 정수 $(x, y)$($-3\,000 \le x, y \le 3\,000$)가 차례로 주어지며, 각 값은 공백으로 구분된다. 각 입력의 요청시각은 감소하지 않는 순서로 주어진다. 같은 시각에 서로 다른 요청들이 올 수 있는데 이런 경우 입력에서 주어진 순서대로 처리한다.

출력 형식

$N$개의 요청 각각에 대해 수락 여부를 한 줄에 하나씩 출력한다. 정상적으로 캠프파이어가 설치되었다면 S_OK를, 요청이 실패했다면 E_FAILED 를 출력한다.

예제

9
0 0 0
0 0 0
2 4 0
4 2 3
7 5 0
12 -3 -4
299 2 3
300 0 0
301 5 2

S_OK
E_FAILED
E_FAILED
E_FAILED
S_OK
S_OK
E_FAILED
S_OK
E_FAILED

채점 방식

전체 입력 케이스들 중 답을 맞춘 입력 케이스 개수에 비례하여 점수를 받는다.

해설