module mod_two_dim_merge_sort
  implicit none
  integer, private, parameter :: intkind = 4
contains
  logical function less(a, b) result(res)
    integer(intkind), intent(in) :: a(:), b(:)
    res = a(1) < b(1) .or. (a(1) == b(1) .and. a(2) <= b(2))
  end
  subroutine merge_sort(a)
    integer(intkind), intent(inout) :: a(:, :)
    integer :: n, m, l, i, u
    n = size(a, 1)
    m = n
    l = 1
    do while (m > 1)
      do i = 1, m / 2
        u = min(2 * i * l, n)
        call merger(a(2 * (i - 1) * l + 1:(2 * i - 1) * l, :), &
        a((2 * i - 1) * l + 1:u, :))
      end do
      l = 2 * l
      m = (m + 1) / 2
    end do
  end
  subroutine merger(a1, a2)
    integer(intkind), intent(inout) :: a1(:, :), a2(:, :)
    integer(intkind) :: a(size(a1, 1) + size(a2, 1), size(a1, 2))
    integer :: i1, i2, n1, n2
    i1 = 1
    i2 = 1
    n1 = size(a1, 1)
    n2 = size(a2, 1)
    do while (i1 <= n1 .and. i2 <= n2)
      if (less(a1(i1, :), a2(i2, :))) then
        a(i1 + i2 - 1, :) = a1(i1, :)
        i1 = i1 + 1
      else
        a(i1 + i2 - 1, :) = a2(i2, :)
        i2 = i2 + 1
       end if
    end do
    if (i1 <= n1) then
      a(i1 + i2 - 1:n1 + n2, :) = a1(i1:n1, :)
    else
      a(i1 + i2 - 1:n1 + n2, :) = a2(i2:n2, :)
    end if
    a1 = a(1:n1, :)
    a2 = a(n1 + 1:n1 + n2, :)
  end
end module mod_two_dim_merge_sort
program air_safety
  use mod_two_dim_merge_sort
  implicit none
  integer, parameter :: inf = 1e9
  integer :: n, x(200000) = 0, y(200000) = 0, u(200000) = 0, i, j, k, z
  integer :: p(200000, 2) = 0, m(0:400000) = 0, ans = inf
  character(1) :: s
  type t_list
    integer, allocatable :: at(:, :)
  end type
  type(t_list) :: list(0:400000)
  read(*,*) n
  do i = 1, n
    read(*,*) x(i), y(i), s
    select case (s)
    case ('U')
      u(i) = 1
    case ('R')
      u(i) = 2
    case ('D')
      u(i) = 3
    case ('L')
      u(i) = 4
    end select
  end do
  do k = 1, 4
    if (k == 1 .or. k == 2) then
      m = 0
      do i = 1, n
        if (mod(u(i), 2) == 1) then
          m(x(i)) = m(x(i)) + 1
        end if
      end do
      do i = 0, 200000
        if (m(i) == 0) cycle
        allocate(list(i)%at(m(i), 2))
      end do
      m = 0
      do i = 1, n
        if (mod(u(i), 2) == 1) then
          m(x(i)) = m(x(i)) + 1
          list(x(i))%at(m(x(i)), 1) = y(i)
          list(x(i))%at(m(x(i)), 2) = u(i)
        end if
      end do
      do i = 0, 200000
        if (m(i) == 0) cycle
        call merge_sort(list(i)%at(1:m(i), :))
        do j = 1, m(i) - 1
          if (list(i)%at(j + 1, 2) - list(i)%at(j, 2) == 2) then
            ans = min(ans, 5 * (list(i)%at(j + 1, 1) - list(i)%at(j, 1)))
          end if
        end do
        deallocate(list(i)%at)
      end do
    end if
    m = 0
    do i = 1, n
      if (u(i) == 1 .or. u(i) == 2) then
        z = x(i) + y(i)
        m(z) = m(z) + 1
      end if
    end do
    do i = 0, 400000
      if (m(i) == 0) cycle
      allocate(list(i)%at(m(i), 2))
    end do
    m = 0
    do i = 1, n
      if (u(i) == 1 .or. u(i) == 2) then
        z = x(i) + y(i)
        m(z) = m(z) + 1
        list(z)%at(m(z), 1) = y(i)
        list(z)%at(m(z), 2) = u(i)
      end if
    end do
    do i = 0, 400000
      if (m(i) == 0) cycle
      call merge_sort(list(i)%at(1:m(i), :))
      do j = 1, m(i) - 1
        if (list(i)%at(j + 1, 2) - list(i)%at(j, 2) == 1) then
          ans = min(ans, 10 * (list(i)%at(j + 1, 1) - list(i)%at(j, 1)))
        end if
      end do
      deallocate(list(i)%at)
    end do
    do i = 1, n
      u(i) = u(i) + 1
      if (u(i) == 5) u(i) = 1
      z = x(i)
      x(i) = y(i)
      y(i) = 200000 - z
    end do
  end do
  if (ans == inf) then
    write(*,'(a)') 'SAFE'
  else
    write(*,'(i0)') ans
  end if
end program air_safety

Measured memory_bytes: 46704