Language: C++

#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s[2 * 100000 + 1];
int n, cnt, ans, b, c, d, tmp, m, h, w, x[2 * 100000 + 1], y[2 * 100000 + 1],
    sum, k, q;
vector<int> dat1[4 * 100000 + 1], dat2[4 * 100000 + 1], dat31[2 * 100000 + 1],
    dat32[2 * 100000 + 1];
vector<int> dat41[2 * 100000 + 1], dat42[2 * 100000 + 1];

int main(void) {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  ans = LINF;
  rep(i, n) cin >> x[i] >> y[i] >> s[i];
  rep(i, n) {
    if (s[i] == "U") dat1[x[i] + y[i]].p_b(x[i]);
  }
  sort(dat1, dat1 + 4 * 100000);
  rep(i, n) {
    if (s[i] == "R") {
      ll nowx = x[i];
      ll le = 0, ri = Size(dat1[x[i] + y[i]]) - 1, mid;
      if (ri == -1) continue;
      while (ri - le > 1) {
        mid = (le + ri) / 2;
        if (dat1[x[i] + y[i]][mid] < nowx)
          le = mid;
        else
          ri = mid;
      }
      cnt = abs(dat1[x[i] + y[i]][le] - nowx);
      cnt = min(cnt, abs(dat1[x[i] + y[i]][ri] - nowx));
      ans = min(ans, cnt);
    }
  }
  rep(i, n) {
    if (s[i] == "D") dat2[x[i] + y[i]].p_b(x[i]);
  }
  sort(dat2, dat2 + 4 * 100000);
  rep(i, n) {
    if (s[i] == "L") {
      ll nowx = x[i];
      ll le = 0, ri = Size(dat2[x[i] + y[i]]) - 1, mid;
      if (ri == -1) continue;
      while (ri - le > 1) {
        mid = (le + ri) / 2;
        if (dat2[x[i] + y[i]][mid] < nowx)
          le = mid;
        else
          ri = mid;
      }
      cnt = abs(dat2[x[i] + y[i]][le] - nowx);
      cnt = min(cnt, abs(dat2[x[i] + y[i]][ri] - nowx));
      ans = min(ans, cnt);
    }
  }

  //////////
  rep(i, n) {
    if (s[i] == "D") {
      if (x[i] >= y[i])
        dat31[abs(x[i] - y[i])].p_b(x[i]);
      else
        dat32[abs(x[i] - y[i])].p_b(x[i]);
    }
  }
  sort(dat31, dat31 + 4 * 100000);
  sort(dat32, dat32 + 4 * 100000);
  rep(i, n) {
    if (s[i] == "R") {
      ll nowx = x[i];
      if (x[i] >= y[i]) {
        ll le = 0, ri = Size(dat31[abs(x[i] - y[i])]) - 1, mid;
        if (ri == -1) continue;
        while (ri - le > 1) {
          mid = (le + ri) / 2;
          if (dat31[abs(x[i] - y[i])][mid] < nowx)
            le = mid;
          else
            ri = mid;
        }
        cnt = abs(dat31[abs(x[i] - y[i])][le] - nowx);
        cnt = min(cnt, abs(dat31[abs(x[i] - y[i])][ri] - nowx));
        ans = min(ans, cnt);
      } else {
        ll le = 0, ri = Size(dat32[abs(x[i] - y[i])]) - 1, mid;
        if (ri == -1) continue;
        while (ri - le > 1) {
          mid = (le + ri) / 2;
          if (dat32[abs(x[i] - y[i])][mid] < nowx)
            le = mid;
          else
            ri = mid;
        }
        cnt = abs(dat32[abs(x[i] - y[i])][le] - nowx);
        cnt = min(cnt, abs(dat32[abs(x[i] - y[i])][ri] - nowx));
        ans = min(ans, cnt);
      }
    }
  }

  ////
  rep(i, n) {
    if (s[i] == "U") {
      if (x[i] >= y[i])
        dat41[abs(x[i] - y[i])].p_b(x[i]);
      else
        dat42[abs(x[i] - y[i])].p_b(x[i]);
    }
  }
  sort(dat41, dat41 + 4 * 100000);
  sort(dat42, dat42 + 4 * 100000);
  rep(i, n) {
    if (s[i] == "L") {
      ll nowx = x[i];
      if (x[i] >= y[i]) {
        ll le = 0, ri = Size(dat41[abs(x[i] - y[i])]) - 1, mid;
        if (ri == -1) continue;
        while (ri - le > 1) {
          mid = (le + ri) / 2;
          if (dat41[abs(x[i] - y[i])][mid] < nowx)
            le = mid;
          else
            ri = mid;
        }
        cnt = abs(dat41[abs(x[i] - y[i])][le] - nowx);
        cnt = min(cnt, abs(dat41[abs(x[i] - y[i])][ri] - nowx));
        ans = min(ans, cnt);
      } else {
        ll le = 0, ri = Size(dat42[abs(x[i] - y[i])]) - 1, mid;
        if (ri == -1) continue;
        while (ri - le > 1) {
          mid = (le + ri) / 2;
          if (dat42[abs(x[i] - y[i])][mid] < nowx)
            le = mid;
          else
            ri = mid;
        }
        cnt = abs(dat42[abs(x[i] - y[i])][le] - nowx);
        cnt = min(cnt, abs(dat42[abs(x[i] - y[i])][ri] - nowx));
        ans = min(ans, cnt);
      }
    }
  }
  if (ans == LINF)
    Cout("SAFE");
  else
    Cout(ans);
  return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:74:9: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   74 |   ans = LINF;
      |         ^~~~
a.cc:93:16: error: no matching function for call to 'min(int&, long long int)'
   93 |       cnt = min(cnt, abs(dat1[x[i] + y[i]][ri] - nowx));
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:93:16: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   93 |       cnt = min(cnt, abs(dat1[x[i] + y[i]][ri] - nowx));
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:93:16: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   93 |       cnt = min(cnt, abs(dat1[x[i] + y[i]][ri] - nowx));
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:114:16: error: no matching function for call to 'min(int&, long long int)'
  114 |       cnt = min(cnt, abs(dat2[x[i] + y[i]][ri] - nowx));
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:114:16: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  114 |       cnt = min(cnt, abs(dat2[x[i] + y[i]][ri] - nowx));
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:114:16: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  114 |       cnt = min(cnt, abs(dat2[x[i] + y[i]][ri] - nowx));
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:144:18: error: no matching function for call to 'min(int&, long long int)'
  144 |         cnt = min(cnt, abs(dat31[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:144:18: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  144 |         cnt = min(cnt, abs(dat31[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:144:18: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  144 |         cnt = min(cnt, abs(dat31[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:157:18: error: no matching function for call to 'min(int&, long long int)'
  157 |         cnt = min(cnt, abs(dat32[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:157:18: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  157 |         cnt = min(cnt, abs(dat32[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:157:18: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  157 |         cnt = min(cnt, abs(dat32[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:188:18: error: no matching function for call to 'min(int&, long long int)'
  188 |         cnt = min(cnt, abs(dat41[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:188:18: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  188 |         cnt = min(cnt, abs(dat41[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:188:18: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  188 |         cnt = min(cnt, abs(dat41[abs(x[i] - y[i])][ri] - nowx));
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:201:18: error: no matching function for call to 'min(int&, long long int)'
  201 |         cnt =