어떻게 잘라도

문제

절삭기계협회(ACM)가 6인치 두께의 철판을 마치 뜨거운 칼이 젤리(전통을 중시한다면 버터)를 가르듯 잘라내는 새로운 휴대용 레이저를 발표했다. 이 레이저는 절단할 표면 위를 달리도록 프로그래밍된 소형 동력 차량에 장착되어 있다. 차량이 할 수 있는 동작은 두 가지다. 직선으로 전진하면서 그 아래 표면을 잘라 나가거나, 제자리에서 방향을 틀어 다른 쪽을 바라보는 것이다.

레이저가 표면에 닫힌 구멍을 내면 문제가 생긴다. 구멍 안쪽 조각이 아래로 떨어지고 차량이 그 구멍에 빠지기 때문이다. 주어진 명령들을 실행했을 때 차량이 구멍을 내는지, 즉 잘라 온 경로가 스스로와 교차하는지 판정하라. 표면은 무한히 넓고, 레이저가 낸 절단선의 폭은 0이라고 가정한다.

레이저는 (0, 0)에서 시작하며 처음에는 양의 Y 방향을 향한다. 명령은 항상 회전과 이동이 번갈아 나온다. 모든 명령은 상대적이다. 회전은 현재 향하고 있는 방향에서 주어진 각도만큼 반시계 방향으로 도는 것이고(음수이면 시계 방향으로 돈다), 이동은 현재 향한 방향으로 주어진 거리만큼 전진하는 것이다.

예를 들어 다음 명령들을 생각해 보자.

TURN  -90
MOVE   10
TURN   90
MOVE    5
TURN  135
MOVE   10
TURN  -90
MOVE    5

차량은 다음과 같이 움직인다.

-90° 회전. 레이저는 (0, 0)에 그대로 있지만 차량은 이제 양의 X 방향을 향한다.
10만큼 전진. 레이저가 (10, 0)으로 이동한다.
90° 회전. 레이저는 (10, 0)에 그대로 있고, 차량은 다시 양의 Y 방향을 향한다.
5만큼 전진. 레이저가 (10, 5)로 이동한다.
135° 회전. 차량은 이제 음의 XY 방향을 대각선으로 향한다.
10만큼 전진. 이 이동을 끝까지 마치면 레이저는 약 (2.93, -2.07)에 도달하겠지만, 도중에 앞서 낸 절단선 중 하나와 교차하여 구멍이 생기고 차량이 갇힌다. 따라서 이 이동(과 그 뒤의 모든 명령)은 수행할 수 없다.

입력

입력은 최대 20개의 데이터 집합으로 이루어진다. 각 데이터 집합은 실행할 회전/이동 쌍의 개수를 나타내는 정수 $N$이 담긴 줄로 시작한다($1 \le N \le 100$). 0만 있는 줄은 입력의 끝을 뜻한다.

이어지는 $N$개의 줄에는 각각 두 정수 $T$와 $M$이 있다. $T$는 회전할 각도($-179 \le T \le 179$)이고, $M$은 회전한 뒤 전진할 거리($1 \le M \le 100$)이다.

$T$와 $M$은 정수이지만 레이저의 위치는 일반적으로 정수 좌표가 아니다. 데이터는 교차하는 두 절단선은 끝점에서 충분히 떨어진 곳에서 만나고, 교차하지 않는 두 절단선은 서로 뚜렷이 떨어져 있도록 선택되어 있다.

출력

각 데이터 집합에 대해, 구멍을 처음으로 만드는 이동의 번호를 출력하라(예: 세 번째 이동이 구멍을 만들면 3을 출력한다). 구멍이 생긴 뒤의 명령들은 결과와 무관하지만, 입력에서 끝까지 읽어야 한다.

전체 명령을 구멍 없이 모두 수행할 수 있다면 SAFE라는 단어를 출력하라.