Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))

XYU.sort(key=lambda x:x[1])
for x, y, u in XYU:
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if y<py: break
            if x<px and y>py:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if px>x: break
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if px>x: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if y<py: break
            if py<y:
                ans = min(ans, (y-py)/2)

        for px, py in DR[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and py<y:
                ans = min(ans, x-px)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))

XYU.sort(key=lambda x:x[1])
for x, y, u in XYU:
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if y<py: break
            if x<px and y>py:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if px>x: break
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if px>x: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if y<py: break
            if py<y:
                ans = min(ans, (y-py)/2)

        for px, py in DR[(x-y)]:
            if px>x: break
            if x>px and py<y:
                ans = min(ans, x-px)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))

XYU.sort(key=lambda x:x[1])
for x, y, u in XYU:
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='D':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if y<py: break
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if px>x: break
            if y<py: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if px>x: break
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if px>x: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if y<py: break
            if py<y:
                ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    if u=='U':
        UR[(x+y)].append((x, y))
        UL[(x-y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
        DR[(x-y)].append((x, y))
    XYU.append((x, y, u))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    elif u=='L':
        for px, py in UL[(x-y)]:
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if x>px:
                ans = min(ans, (x-px)/2)
                
    elif u=='D':
        for px, py in UD[x]:
            if py<y:
                ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
UR = {}
URs = set()
UL = {}
ULs = set()
DR = {}
DRs = set()
DL = {}
DLs = set()
LR = {}
LRs = set()
UD = {}
UDs = set()
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        if x+y in URs:
            UR[(x+y)].append((x, y))
        else:
            UR[x+y] = [(x, y)]
            URs.add(x+y)
        if x-y in ULs:
            UL[(x-y)].append((x, y))
        else:
            UL[x-y] = [(x, y)]
            ULs.add(x-y)
        if x in UDs:
            UD[x].append((x, y))
        else:
            UD[x] = [(x, y)]
            UDs.add(x)
    if u=='R':
        if y in LRs:
            LR[y].append((x, y))
        else:
            LRs.add(y)
            LR[y] = [(x, y)]
    if u=='D':
        if x+y in DLs:
            DL[(x+y)].append((x, y))
        else:
            DL[x+y] = [(x, y)]
            DLs.add(x+y)
        if x-y in DRs:
            DR[(x-y)].append((x, y))
        else:
            DR[(x-y)] = [(x, y)]
            DRs.add(x-y)

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        if x+y in URs:
            for px, py in UR[(x+y)]:
                if x<px and y>py:
                    ans = min(ans, px-x)
        
        if x-y in DRs:      
            for px, py in DR[(x-y)]:
                if x<px and py>y:
                    ans = min(ans, px-x)
                
    if u=='L':
        if x-y in ULs:
            for px, py in UL[(x-y)]:
                if px>x: break
                if x>px and y>py:
                    ans = min(ans, x-px)
            
        if x+y in DLs:    
            for px, py in DL[(x+y)]:
                if px>x: break
                if x>px and py>y:
                    ans = min(ans, x-px) 
        
        if y in LRs:      
            for px, py in LR[y]:
                if px>x: break
                if x>px:
                    ans = min(ans, (x-px)/2)
                
    if u=='D':
        if x in UDs:
            for px, py in UD[x]:
                if py<y:
                    ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
UR = {}
URs = set()
UL = {}
ULs = set()
DR = {}
DRs = set()
DL = {}
DLs = set()
LR = {}
LRs = set()
UD = {}
UDs = set()
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        if x+y in URs:
            UR[(x+y)].append((x, y))
        else:
            UR[x+y] = [(x, y)]
            URs.add(x+y)
        if x-y in ULs:
            UL[(x-y)].append((x, y))
        else:
            UL[x-y] = [(x-y)]
            ULs.add(x-y)
        if x in UDs:
            UD[x].append((x, y))
        else:
            UD[x] = [(x, y)]
            UDs.add(x)
    if u=='R':
        if y in LRs:
            LR[y].append((x, y))
        else:
            LRs.add(y)
            LR[y] = [(x, y)]
    if u=='D':
        if x+y in DLs:
            DL[(x+y)].append((x, y))
        else:
            DL[x+y] = [(x, y)]
            DLs.add(x+y)
        if x-y in DRs:
            DR[(x-y)].append((x, y))
        else:
            DR[(x-y)] = [(x, y)]
            DRs.add(x-y)

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        if x+y in URs:
            for px, py in UR[(x+y)]:
                if x<px and y>py:
                    ans = min(ans, px-x)
        
        if x-y in DRs:      
            for px, py in DR[(x-y)]:
                if x<px and py>y:
                    ans = min(ans, px-x)
                
    if u=='L':
        if x-y in ULs:
            for px, py in UL[(x-y)]:
                if px>x: break
                if x>px and y>py:
                    ans = min(ans, x-px)
            
        if x+y in DLs:    
            for px, py in DL[(x+y)]:
                if px>x: break
                if x>px and py>y:
                    ans = min(ans, x-px) 
        
        if y in LRs:      
            for px, py in LR[y]:
                if px>x: break
                if x>px:
                    ans = min(ans, (x-px)/2)
                
    if u=='D':
        if x in UDs:
            for px, py in UD[x]:
                if py<y:
                    ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UR[(x+y)].append((x, y))
        UL[(x-y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if px>x: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if px>x: break
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if px>x: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if py<y:
                ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    x, y = int(x), int(y)
    if u=='U':
        UR[(x+y)].append((x, y))
        UL[(x-y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if x<px: break
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if x<px: break
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if py<y:
                ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    if u=='U':
        UR[(x+y)].append((x, y))
        UL[(x-y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
        DR[(x-y)].append((x, y))
    XYU.append((x, y, u))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if py<y:
                ans = min(ans, (y-py)/2)

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from collections import defaultdict, deque
UR = defaultdict(deque)
UL = defaultdict(deque)
DR = defaultdict(deque)
DL = defaultdict(deque)
LR = defaultdict(deque)
UD = defaultdict(deque)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    if u=='U':
        UR[(x+y)].append((x, y))
        UL[(x-y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
        DR[(x-y)].append((x, y))
    XYU.append((x, y, u))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        for px, py in UR[(x+y)]:
            if x<px and y>py:
                ans = min(ans, px-x)
                
        for px, py in DR[(x-y)]:
            if x<px and py>y:
                ans = min(ans, px-x)
                
    if u=='L':
        for px, py in UL[(x-y)]:
            if x>px and y>py:
                ans = min(ans, x-px)
                
        for px, py in DL[(x+y)]:
            if x>px and py>y:
                ans = min(ans, x-px) 
                
        for px, py in LR[y]:
            if x>px:
                ans = min(ans, (x-px)/2)
                
    if u=='D':
        for px, py in UD[x]:
            if py<y:
                ans = min(ans, (y-py)/2)
for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))



Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XYU = []
from bisect import bisect_left
from collections import defaultdict
UR = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
LR = defaultdict(list)
UD = defaultdict(list)
for _ in range(N):
    x, y, u = input().split()
    x, y = int(x), int(y)
    XYU.append((x, y, u))
XYU.sort()
for x, y, u in XYU:
    if u=='U':
        UL[(x-y)].append((x, y))
    if u=='R':
        LR[y].append((x, y))
    if u=='D':
        DL[(x+y)].append((x, y))
    if u=='U':
        UR[(x+y)].append((x, y))
        UD[x].append((x, y))
    if u=='R':
        DR[(x-y)].append((x, y))

ans = 10**18
def check(x, y, u):
    global ans
    if u=='R':
        leng = len(UR[x+y])
        if leng:
            idx = bisect_left(UR[x+y], (x, y, u))
            if idx<leng:
                ans = min(ans, UR[x+y][idx][0]-x)

    if u=='L':
        leng = len(UL[x-y])
        if leng:
            idx = bisect_left(UL[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-UL[x-y][idx-1][0])
        
        leng = len(DL[x+y])
        if leng:
            idx = bisect_left(DL[x+y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DL[x+y][idx-1][0])
        
        leng = len(LR[y])
        if leng:
            idx = bisect_left(LR[y], (x, y, u))
            if idx>0:
                ans = min(ans, (x-LR[y][idx-1][0])/2)

    if u=='D':
        leng = len(UD[x])
        if leng:
            idx = bisect_left(UD[x], (x, y, u))
            if idx>0:
                ans = min(ans, (y-UD[x][idx-1][1])/2)

        leng = len(DR[x-y])
        if leng:
            idx = bisect_left(DR[x-y], (x, y, u))
            if idx>0:
                ans = min(ans, x-DR[x-y][idx-1][0])

for x, y, u in XYU:
    check(x, y, u)

if ans>=10**16:
    print('SAFE')
else:
    print(int(ans*10))