Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                print(V[i+1],V[i],x)
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())
Rp = {}
Lp = {}
Rm = {}
Lm = {}
U = []
R = []
L = []
D = []

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        U.append((x,y))
    elif u == "D":    
        D.append((x,y))
    elif u == "R":   
        if x+y in Rp:
            Rp[x+y].append((x,y))
        else:
            Rp[x+y] = [(x,y)]
        if x-y in Rm:
            Rm[x-y].append((x,y))
        else:
            Rm[x-y] = [(x,y)]
        R.append((y,x))
        
    else:
        if x+y in Lp:
            Lp[x+y].append((x,y))
        else:
            Lp[x+y] = [(x,y)]
        if x-y in Lm:
            Lm[x-y].append((x,y))
        else:
            Lm[x-y] = [(x,y)]
        L.append((y,x))

ans = float("INF")

for x,y in U:
    if x+y in Rp:
        for nx,ny in Rp[x+y]:
            if ny >= y:
                ans = min(ans,abs(ny-y)*10)
    if x-y in Lm:
        for nx,ny in Lm[x-y]:
            if ny >= y:
                ans = min(ans,abs(ny-y)*10)
for x,y in D:
    if x+y in Lp:
        for nx,ny in Lp[x+y]:
            if y >= ny:
                ans = min(ans,abs(ny-y)*10)
    if x-y in Rm:
        for nx,ny in Rm[x-y]:
            if y >= ny:
                ans = min(ans,abs(ny-y)*10)

def syaku(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        x,y = A[i]
        if i > 0 and x == A[i-1][0]:
            if len(l) > 0:
                for nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(y-ny)*5)
        else:
            l = []
            while b < lb and B[b][0] <= x:
                if B[b][0] == x:
                    if y >= B[b][1]:
                        count = min(count,abs(y-B[b][1])*5)
                    l.append(B[b])
                b += 1
    return count


D.sort()
U.sort()
L.sort()
R.sort()
ans = min(ans,syaku(D,U))
ans = min(ans,syaku(L,R))

if ans == float("INF"):
    print("SAFE")
else:
    print(ans)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())
Rp = []
Lp = []
Up = []
Dp = []


for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":
        Up.append((x+y,x-y,x,y))
        
    elif u == "D":
        Dp.append((x+y,x-y,x,y))
        
    elif u == "R":   
        Rp.append((x+y,x-y,x,y))
        
    else:
        Lp.append((x+y,x-y,x,y))

def syaku(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        xy,_,x,y = A[i]
        if i > 0 and xy == A[i-1][0]:
            if len(l) > 0:
                for nxy,_,nx,ny in l:
                    if ny >= y:
                        count = min(count, abs(x-nx)*10)
        else:
            l = []
            while b < lb and B[b][0] <= xy:
                if B[b][0] == xy:
                    if B[b][3] >= y:
                        count = min(count,abs(x-B[b][2])*10)
                    l.append(B[b])
                b += 1
    return count

def syaku2(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        xy,_,x,y = A[i]
        if i > 0 and xy == A[i-1][0]:
            if len(l) > 0:
                for nxy,_,nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(x-nx)*10)
        else:
            l = []
            while b < lb and B[b][0] <= xy:
                if B[b][0] == xy:
                    if y >= B[b][3]:
                        count = min(count,abs(x-B[b][2])*10)
                    l.append(B[b])
                b += 1
    return count

def syaku3(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        _,_,x,y = A[i]
        if i > 0 and x == A[i-1][2]:
            if len(l) > 0:
                for _,_,nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(y-ny)*5)
        else:
            l = []
            while b < lb and B[b][2] <= x:
                if B[b][2] == x:
                    if y >= B[b][3]:
                        count = min(count,abs(y-B[b][3])*5)
                    l.append(B[b])
                b += 1
    return count

def syaku4(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        _,xy,x,y = A[i]
        if i > 0 and xy == A[i-1][1]:
            if len(l) > 0:
                for _,nxy,nx,ny in l:
                    if ny >= y:
                        count = min(count, abs(x-nx)*10)
        else:
            l = []
            while b < lb and B[b][1] <= xy:
                if B[b][1] == xy:
                    if B[b][3] >= y:
                        count = min(count,abs(x-B[b][2])*10)
                    l.append(B[b])
                b += 1
    return count

def syaku5(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        _,xy,x,y = A[i]
        if i > 0 and xy == A[i-1][1]:
            if len(l) > 0:
                for _,nxy,nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(x-nx)*10)
        else:
            l = []
            while b < lb and B[b][1] <= xy:
                if B[b][1] == xy:
                    if y >= B[b][3]:
                        count = min(count,abs(x-B[b][2])*10)
                    l.append(B[b])
                b += 1
    return count

def syaku6(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        _,_,x,y = A[i]
        if i > 0 and y == A[i-1][3]:
            if len(l) > 0:
                for _,_,nx,ny in l:
                    if x >= nx:
                        count = min(count, abs(x-nx)*5)
        else:
            l = []
            while b < lb and B[b][3] <= y:
                if B[b][3] == y:
                    if x >= B[b][2]:
                        count = min(count,abs(x-B[b][2])*5)
                    l.append(B[b])
                b += 1
    return count
ans = float("INF")
Rp.sort()
Up.sort()
Lp.sort()
Dp.sort()
ans = min(ans,syaku(Up,Rp))
ans = min(ans,syaku2(Dp,Lp))
Rp.sort(key = lambda x: x[1])
Up.sort(key = lambda x: x[1])
Lp.sort(key = lambda x: x[1])
Dp.sort(key = lambda x: x[1])
ans = min(ans,syaku4(Up,Lp))
ans = min(ans,syaku5(Dp,Rp))
Rp.sort(key = lambda x: x[3])
Up.sort(key = lambda x: x[2])
Lp.sort(key = lambda x: x[3])
Dp.sort(key = lambda x: x[2])
ans = min(ans,syaku3(Dp,Up))
ans = min(ans,syaku6(Lp,Rp))

if ans == float("INF"):
    print("SAFE")
else:
    print(ans)


Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


n = int(input())
Rp = []
Rm = []
Lp = []
Lm = []
Up = []
Um = []
Dp = []
Dm = []
U = []
D = []
R = []
L = []

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":
        U.append([x,y])
        Up.append((x+y,x,y))
        Um.append((x-y,x,y))
    elif u == "D":
        D.append([x,y])
        Dp.append((x+y,x,y))
        Dm.append((x-y,x,y))
    elif u == "R":
        R.append([y,x])    
        Rp.append((x+y,x,y))
        Rm.append((x-y,x,y))
    else:
        L.append([y,x])
        Lp.append((x+y,x,y))
        Lm.append((x-y,x,y))

Rp.sort()
Rm.sort()
Up.sort()
Um.sort()
Lp.sort()
Lm.sort()
Dp.sort()
Dm.sort()
U.sort()
D.sort()
R.sort()
L.sort()
ans = float("INF")

def syaku(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        xy,x,y = A[i]
        if i > 0 and xy == A[i-1][0]:
            if len(l) > 0:
                for nxy,nx,ny in l:
                    if ny >= y:
                        count = min(count, abs(x-nx)*10)
        else:
            if i < la-1 and A[i+1][0] == xy:
                l = []
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if B[b][2] >= y:
                            count = min(count,abs(x-B[b][1])*10)
                        l.append(B[b])
                    b += 1
            else:
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if B[b][2] >= y:
                            count = min(count,abs(x-B[b][1])*10)
                        
                    b += 1
    return count

def syaku2(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        xy,x,y = A[i]
        if i > 0 and xy == A[i-1][0]:
            if len(l) > 0:
                for nxy,nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(x-nx)*10)
        else:
            if i < la-1 and A[i+1][0] == xy:
                l = []
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if y >= B[b][2]:
                            count = min(count,abs(x-B[b][1])*10)
                        l.append(B[b])
                    b += 1
            else:
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if y >= B[b][2]:
                            count = min(count,abs(x-B[b][1])*10)
                        
                    b += 1
    return count

def syaku3(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        x,y = A[i]
        if i > 0 and x == A[i-1][0]:
            if len(l) > 0:
                for nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(y-ny)*5)
        else:
            if i < la-1 and A[i+1][1] == x:
                l = []
                while b < lb and B[b][0] <= x:
                    if B[b][0] == x:
                        if y >= B[b][1]:
                            count = min(count,abs(y-B[b][1])*5)
                        l.append(B[b])
                    b += 1
            else:
                while b < lb and B[b][0] <= x:
                    if B[b][0] == x:
                        if y >= B[b][1]:
                            count = min(count,abs(y-B[b][1])*5)
                    b += 1
    return count

ans = min(ans,syaku(Up,Rp))
ans = min(ans,syaku(Um,Lm))
ans = min(ans,syaku2(Dp,Lp))
ans = min(ans,syaku2(Dm,Rm))
ans = min(ans,syaku3(D,U))
ans = min(ans,syaku3(L,R))

if ans == float("INF"):
    print("SAFE")
else:
    print(ans)



Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    Rp = []
    Rm = []
    Lp = []
    Lm = []
    Up = []
    Um = []
    Dp = []
    Dm = []
    U = []
    D = []
    R = []
    L = []

    for i in range(n):
        x,y,u = input().split()
        x,y = int(x), int(y)
        if u == "U":
            U.append([x,y])
            Up.append((x+y,x,y))
            Um.append((x-y,x,y))
        elif u == "D":
            D.append([x,y])
            Dp.append((x+y,x,y))
            Dm.append((x-y,x,y))
        elif u == "R":
            R.append([y,x])    
            Rp.append((x+y,x,y))
            Rm.append((x-y,x,y))
        else:
            L.append([y,x])
            Lp.append((x+y,x,y))
            Lm.append((x-y,x,y))

    Rp.sort()
    Rm.sort()
    Up.sort()
    Um.sort()
    Lp.sort()
    Lm.sort()
    Dp.sort()
    Dm.sort()
    U.sort()
    D.sort()
    R.sort()
    L.sort()
    ans = float("INF")

    def syaku(A,B):
        if A == [] or B == []:
            return float("INF")
        la = len(A)
        lb = len(B)
        count = float("INF")
        b = 0
        for i in range(la):
            xy,x,y = A[i]
            if i > 0 and xy == A[i-1][0]:
                if len(l) > 0:
                    for nxy,nx,ny in l:
                        if ny >= y:
                            count = min(count, abs(x-nx)*10)
            else:
                l = []
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if B[b][2] >= y:
                            count = min(count,abs(x-B[b][1])*10)
                        l.append(B[b])
                    b += 1
        return count

    def syaku2(A,B):
        if A == [] or B == []:
            return float("INF")
        la = len(A)
        lb = len(B)
        count = float("INF")
        b = 0
        for i in range(la):
            xy,x,y = A[i]
            if i > 0 and xy == A[i-1][0]:
                if len(l) > 0:
                    for nxy,nx,ny in l:
                        if y >= ny:
                            count = min(count, abs(x-nx)*10)
            else:
                l = []
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if y >= B[b][2]:
                            count = min(count,abs(x-B[b][1])*10)
                        l.append(B[b])
                    b += 1
        return count

    def syaku3(A,B):
        if A == [] or B == []:
            return float("INF")
        la = len(A)
        lb = len(B)
        count = float("INF")
        b = 0
        for i in range(la):
            x,y = A[i]
            if i > 0 and x == A[i-1][0]:
                if len(l) > 0:
                    for nx,ny in l:
                        if y >= ny:
                            count = min(count, abs(y-ny)*5)
            else:
                l = []
                while b < lb and B[b][0] <= x:
                    if B[b][0] == x:
                        if y >= B[b][1]:
                            count = min(count,abs(y-B[b][1])*5)
                        l.append(B[b])
                    b += 1
        return count
    ans = min(ans,syaku(Up,Rp))
    ans = min(ans,syaku(Um,Lm))
    ans = min(ans,syaku2(Dp,Lp))
    ans = min(ans,syaku2(Dm,Rm))
    ans = min(ans,syaku3(D,U))
    ans = min(ans,syaku3(L,R))

    if ans == float("INF"):
        print("SAFE")
    else:
        print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    Rp = []
    Rm = []
    Lp = []
    Lm = []
    Up = []
    Um = []
    Dp = []
    Dm = []
    U = []
    D = []
    R = []
    L = []

    for i in range(n):
        x,y,u = input().split()
        x,y = int(x), int(y)
        if u == "U":
            U.append([x,y])
            Up.append((x+y,x,y))
            Um.append((x-y,x,y))
        elif u == "D":
            D.append([x,y])
            Dp.append((x+y,x,y))
            Dm.append((x-y,x,y))
        elif u == "R":
            R.append([y,x])    
            Rp.append((x+y,x,y))
            Rm.append((x-y,x,y))
        else:
            L.append([y,x])
            Lp.append((x+y,x,y))
            Lm.append((x-y,x,y))

    Rp.sort()
    Rm.sort()
    Up.sort()
    Um.sort()
    Lp.sort()
    Lm.sort()
    Dp.sort()
    Dm.sort()
    U.sort()
    D.sort()
    R.sort()
    L.sort()
    ans = float("INF")

    def syaku(A,B):
        if A == [] or B == []:
            return float("INF")
        la = len(A)
        lb = len(B)
        count = float("INF")
        b = 0
        for i in range(la):
            xy,x,y = A[i]
            if i > 0 and xy == A[i-1][0]:
                if len(l) > 0:
                    for nxy,nx,ny in l:
                        if ny >= y:
                            count = min(count, abs(x-nx)*10)
            else:
                l = []
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if B[b][2] >= y:
                            count = min(count,abs(x-B[b][1])*10)
                        l.append(B[b])
                    b += 1
        return count

    def syaku2(A,B):
        if A == [] or B == []:
            return float("INF")
        la = len(A)
        lb = len(B)
        count = float("INF")
        b = 0
        for i in range(la):
            xy,x,y = A[i]
            if i > 0 and xy == A[i-1][0]:
                if len(l) > 0:
                    for nxy,nx,ny in l:
                        if y >= ny:
                            count = min(count, abs(x-nx)*10)
            else:
                l = []
                while b < lb and B[b][0] <= xy:
                    if B[b][0] == xy:
                        if y >= B[b][2]:
                            count = min(count,abs(x-B[b][1])*10)
                        l.append(B[b])
                    b += 1
        return count

    def syaku3(A,B):
        if A == [] or B == []:
            return float("INF")
        la = len(A)
        lb = len(B)
        count = float("INF")
        b = 0
        for i in range(la):
            x,y = A[i]
            if i > 0 and x == A[i-1][0]:
                if len(l) > 0:
                    for nx,ny in l:
                        if y >= ny:
                            count = min(count, abs(y-ny)*5)
            else:
                l = []
                while b < lb and B[b][0] <= x:
                    if B[b][0] == x:
                        if y >= B[b][1]:
                            count = min(count,abs(y-B[b][1])*5)
                        l.append(B[b])
                    b += 1
        return count
    ans = min(ans,syaku(Up,Rp))
    ans = min(ans,syaku(Um,Lm))
    ans = min(ans,syaku2(Dp,Lp))
    ans = min(ans,syaku2(Dm,Rm))
    ans = min(ans,syaku3(D,U))
    ans = min(ans,syaku3(L,R))

    if ans == float("INF"):
        print("SAFE")
    else:
        print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())
Rp = []
Rm = []
Lp = []
Lm = []
Up = []
Um = []
Dp = []
Dm = []
U = []
D = []
R = []
L = []

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":
        U.append([x,y])
        Up.append((x+y,x,y))
        Um.append((x-y,x,y))
    elif u == "D":
        D.append([x,y])
        Dp.append((x+y,x,y))
        Dm.append((x-y,x,y))
    elif u == "R":
        R.append([y,x])    
        Rp.append((x+y,x,y))
        Rm.append((x-y,x,y))
    else:
        L.append([y,x])
        Lp.append((x+y,x,y))
        Lm.append((x-y,x,y))

Rp.sort()
Rm.sort()
Up.sort()
Um.sort()
Lp.sort()
Lm.sort()
Dp.sort()
Dm.sort()
U.sort()
D.sort()
R.sort()
L.sort()
ans = float("INF")

def syaku(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        xy,x,y = A[i]
        if i > 0 and xy == A[i-1][0]:
            if len(l) > 0:
                for nxy,nx,ny in l:
                    if ny >= y:
                        count = min(count, abs(x-nx)*10)
        else:
            l = []
            while b < lb and B[b][0] <= xy:
                if B[b][0] == xy:
                    if B[b][2] >= y:
                        count = min(count,abs(x-B[b][1])*10)
                    l.append(B[b])
                b += 1
    return count

def syaku2(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        xy,x,y = A[i]
        if i > 0 and xy == A[i-1][0]:
            if len(l) > 0:
                for nxy,nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(x-nx)*10)
        else:
            l = []
            while b < lb and B[b][0] <= xy:
                if B[b][0] == xy:
                    if y >= B[b][2]:
                        count = min(count,abs(x-B[b][1])*10)
                    l.append(B[b])
                b += 1
    return count

def syaku3(A,B):
    if A == [] or B == []:
        return float("INF")
    la = len(A)
    lb = len(B)
    count = float("INF")
    b = 0
    for i in range(la):
        x,y = A[i]
        if i > 0 and x == A[i-1][0]:
            if len(l) > 0:
                for nx,ny in l:
                    if y >= ny:
                        count = min(count, abs(y-ny)*5)
        else:
            l = []
            while b < lb and B[b][0] <= x:
                if B[b][0] == x:
                    if y >= B[b][1]:
                        count = min(count,abs(y-B[b][1])*5)
                    l.append(B[b])
                b += 1
    return count
ans = min(ans,syaku(Up,Rp))

ans = min(ans,syaku(Um,Lm))

ans = min(ans,syaku2(Dp,Lp))

ans = min(ans,syaku2(Dm,Rm))

ans = min(ans,syaku3(D,U))
ans = min(ans,syaku3(L,R))

if ans == float("INF"):
    print("SAFE")
else:
    print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
UR = defaultdict(list)
UD = defaultdict(list)
UL = defaultdict(list)
DR = defaultdict(list)
DL = defaultdict(list)
RL = defaultdict(list)

for i in range(n):
    x,y,u = input().split()
    x,y = int(x), int(y)
    if u == "U":    
        UD[x].append((y,1))
        UR[x+y].append((x-y,0))
        UL[y-x].append((x+y,1))
    elif u == "D":    
        UD[x].append((y,0))
        DR[y-x].append((x+y,0))
        DL[x+y].append((x-y,1))
    elif u == "R":   
        RL[y].append((x,1))
        DR[y-x].append((x+y,1))
        UR[x+y].append((x-y,1))
        
    else:
        RL[y].append((x,0))
        UL[y-x].append((x+y,0))
        DL[x+y].append((x-y,0))

ans = float("INF")

for x in [UD, UL, UR, DR, DL, RL]:
    for v in x.values():
        V = sorted(v)

        for i in range(len(V)-1):
            if V[i][1] and not V[i+1][1]:
                ans = min(ans,V[i+1][0]-V[i][0])


if ans == float("INF"):
    print("SAFE")
else:
    print(ans*5)