Problem Description

M-kun is a great air traffic controller.

Currently, within the display of his radar, there are $N$ airplanes flying at the same altitude, numbered $1, 2, ..., N$.
Each airplane is flying at a constant speed of $0.1$ meters per second in a constant direction. The current coordinates of the airplane numbered $i$ are $(X_i, Y_i)$, and its direction of travel is as follows:

• If $U_i$ is U: flying in the positive y-coordinate direction.
• If $U_i$ is R: flying in the positive x-coordinate direction.
• If $U_i$ is D: flying in the negative y-coordinate direction.
• If $U_i$ is L: flying in the negative x-coordinate direction.

To assist M-kun in his work, determine if there are any pairs of airplanes that will collide if they continue flying as they are.
If there are, find out the earliest time from now when they will collide.
Note that all airplanes are so small that they can be ignored, and a collision only occurs when two airplanes reach the same coordinates simultaneously.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X_1 $ $ Y_1 $ $ U_1 $ $ X_2 $ $ Y_2 $ $ U_2 $ $ X_3 $ $ Y_3 $ $ U_3 $ $ : $ $ X_N $ $ Y_N $ $ U_N $

Output Format

If there are pairs of airplanes that will collide, output the integer number of seconds from now when the earliest collision will occur.
If there are no such pairs, output SAFE.

Sample Input and Output

Sample Input #1

2
11 1 U
11 47 D

Sample Output #1

230

Sample Input #2

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

Sample Output #2

SAFE

Sample Input #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

Sample Output #3

100

Notes/Hints

Constraints

• $1 \leq N \leq 200000$
• $0 \leq X_i, Y_i \leq 200000$
• $ U_i $ is one of U, R, D, L
• The current positions $(X_i, Y_i)$ of all $N$ airplanes are distinct
• $ N, X_i, Y_i $ are integers

Sample Explanation 1

If they continue as they are, the airplanes numbered $1$ and $2$ will reach the coordinates $(11, 24)$ simultaneously after $230$ seconds and collide.

Sample Explanation 2

There are no pairs of airplanes that will collide.

见题面 Input 部分

见题面 Output 部分