AT_m_solutions2020_f Air Safety

[problemUrl]: https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_f M 君は立派な航空管制官です。 今、彼が管理するレーダーのディスプレイの中では、番号 $ 1,\ 2,\ ...,\ N $ の $ N $ 機の飛行機が、全て同じ高度を飛行しています。 各飛行機は秒速 $ 0.1 $ という一定の速度で一定の方向に飛行しており、番号 $ i $ の飛行機の現在の座標は $ (X_i,\ Y_i) $、進行方向は以下の通りです。 - $ U_i $ が `U` の場合：y 座標の正の方向に進む。 - $ U_i $ が `R` の場合：x 座標の正の方向に進む。 - $ U_i $ が `D` の場合：y 座標の負の方向に進む。 - $ U_i $ が `L` の場合：x 座標の負の方向に進む。 M 君の仕事を助けるために、このままでは衝突してしまう飛行機の組が存在するかどうか判定してください。 もし存在する場合は、最も早いもので今から何秒後に衝突してしまうかを求めてください。 ただし、すべての飛行機は無視できるほど小さく、衝突は $ 2 $ つの飛行機が同じ座標に同時に到達した場合にのみ起こるものとします。

入力は以下の形式で標準入力から与えられます。 > $ 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 $

このままでは衝突してしまう飛行機の組が存在する場合は、最も早いもので今から何秒後に衝突するかを整数で出力してください。 存在しない場合は、`SAFE` と出力してください。

### 制約 - $ 1\ \leq\ N\ \leq\ 200000 $ - $ 0\ \leq\ X_i,\ Y_i\ \leq\ 200000 $ - $ U_i $ は `U`、`R`、`D`、`L` のいずれかである - $ N $ 機の飛行機の現在位置 $ (X_i,\ Y_i) $ はすべて異なる - $ N,\ X_i,\ Y_i $ は整数 ### Sample Explanation 1 このままでは、$ 230 $ 秒後に、番号 $ 1 $ の飛行機と番号 $ 2 $ の飛行機が同時に座標 $ (11,\ 24) $ に到達し、衝突してしまいます。 ### Sample Explanation 2 衝突してしまう飛行機の組はひとつもありません。