{"raw_statement":[{"iden":"problem statement","content":"M-kun is a brilliant air traffic controller.\nOn the display of his radar, there are $N$ airplanes numbered $1, 2, ..., N$, all flying at the same altitude.  \nEach of the airplanes flies at a constant speed of $0.1$ per second in a constant direction. The current coordinates of the airplane numbered $i$ are $(X_i, Y_i)$, and the direction of the airplane is as follows:\n\n*   if $U_i$ is `U`, it flies in the positive $y$ direction;\n*   if $U_i$ is `R`, it flies in the positive $x$ direction;\n*   if $U_i$ is `D`, it flies in the negative $y$ direction;\n*   if $U_i$ is `L`, it flies in the negative $x$ direction.\n\nTo help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now.  \nIf there is such a pair, find the number of seconds after which the first collision will happen.  \nWe assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 200000$\n*   $0 \\leq X_i, Y_i \\leq 200000$\n*   $U_i$ is `U`, `R`, `D`, or `L`.\n*   The current positions of the $N$ airplanes, $(X_i, Y_i)$, are all distinct.\n*   $N$, $X_i$, and $Y_i$ are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$X_1$ $Y_1$ $U_1$\n$X_2$ $Y_2$ $U_2$\n$X_3$ $Y_3$ $U_3$\n$:$\n$X_N$ $Y_N$ $U_N$"},{"iden":"sample input 1","content":"2\n11 1 U\n11 47 D"},{"iden":"sample output 1","content":"230\n\nIf the airplanes keep flying as they are now, two airplanes numbered $1$ and $2$ will reach the coordinates $(11, 24)$ simultaneously and collide."},{"iden":"sample input 2","content":"4\n20 30 U\n30 20 R\n20 10 D\n10 20 L"},{"iden":"sample output 2","content":"SAFE\n\nNo pair of airplanes will collide."},{"iden":"sample input 3","content":"8\n168 224 U\n130 175 R\n111 198 D\n121 188 L\n201 116 U\n112 121 R\n145 239 D\n185 107 L"},{"iden":"sample output 3","content":"100"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}