Descripción

Después del tremendo éxito que tuvo el lenguaje de programación Halk-E. Eduardo ha decidido abrir un aeropuerto. Por supuesto, todo aeropuerto necesita de un buen controlador de tráfico aéreo, y por eso Eduardo ha decidido pedirle ayuda al mejor controlador de tráfico aéreo que él conoce: su amigo Alben.

Alben es un brillante controlador de tráfico aéreo pero en estos días ha estado ocupado escribiendo los informes mensuales del aeropuerto. Por eso necesita colaboración de alguien para que controle el tráfico durante algunas horas.

En la pantalla de su radar, hay ~N~ aviones numerados ~1, 2, ..., N~, todos volando a la misma altitud. Cada uno de los aviones vuela a una velocidad constante de ~0.1~ por segundo en una dirección constante. Las coordenadas actuales del avión numerado ~i~ son ~(X_i, Y_i)~, y la dirección del avión es la siguiente:

• si ~U_i~ es U, vuela en la dirección positiva de ~y~
• si ~U_i~ es R, vuela en la dirección positiva de ~x~
• si ~U_i~ es D, vuela en la dirección negativa de ~y~
• si ~U_i~ es L, vuela en la dirección negativa de ~x~

Para ayudar a Alben en su trabajo, determina si hay un par de aviones que chocarán entre sí si siguen volando como lo están haciendo ahora.

Si hay tal par, encuentra el número de segundos después de los cuales ocurrirá la primera colisión. Suponemos que los aviones son tan pequeños que solo chocan cuando alcanzan las mismas coordenadas simultáneamente.

Entrada

La primera línea de la entrada contiene un entero ~N~ (~1 \le N \leq 200000~), la cantidad de aviones en el aeropuerto.

Le siguen ~N~ líneas cada una de ellas contienen tres enteros, ~X_i~, ~Y_i~, ~U_i~ (~0 \le X_i, Y_i \le 200000~), la posición actual del i-ésimo avión y la dirección hacia la cuál está volando actualmente.

Se garantiza que las posiciones actuales de los ~N~ aviones, (~X_i, Y_i~), son todas distintas.

Salida

Si hay un par de aviones que chocarán entre sí si siguen volando como lo están haciendo ahora, imprime un entero que represente el número de segundos después del cual ocurrirá la primera colisión.

Si no hay tal par, imprime SAFE.

Casos de Prueba

• 20% de los casos de prueba N <= 2000
• otros 20% de los casos los aviones solo viajan en direcciones opuestas {(L,R) o (U,D)}
• el 60% restante sin restricciones adicionales

Ejemplos

Entrada 1

2
11 1 U
11 47 D

Salida 1

230

Si los aviones siguen volando como lo están haciendo ahora, dos aviones numerados ~1~ y ~2~ alcanzarán las coordenadas ~(11,24)~ simultáneamente y chocarán.

Entrada 2

4
20 30 U
30 20 R
20 10 D
10 20 L

Salida 2

SAFE

Ningún par de aviones chocará.

Entrada 3

8
168 224 U
130 175 R
111 198 D
121 188 L
201 116 U
112 121 R
145 239 D
185 107 L

Salida 3

100