Harryxun/testdata huggingface dataset:
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, M = mapint()
S = list(input())
T = list(input())
from math import gcd

leng = N*M//gcd(N, M)

for i in range(1, leng+1):
    if (i-1)%(leng//N)==0 and(i-1)%(leng//M)==0:
        if S[(i-1)//(leng//N)]!=T[(i-1)//(leng//M)]:
            print(-1)
            break
else:
    print(leng)

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

N, M = mapint()
S = list(input())
T = list(input())
from math import gcd

leng = N*M//gcd(N, M)
step = (leng//N)*(leng//M)//gcd((leng//N), (leng//M))

for i in range(1, leng+1, step):
    if (i-1)%(leng//N)==0 and(i-1)%(leng//M)==0:
        if S[(i-1)//(leng//N)]!=T[(i-1)//(leng//M)]:
            print(-1)
            break
else:
    print(leng)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
Xs = list(map(int, input().split()))
from math import gcd

lis = []
for x in Xs:
    lis.append(abs(x-X))

G = 0
for l in lis:
    G = gcd(l, G)
print(G)

Fixed submission:
N, X = map(int, input().split())
Xs = list(map(int, input().split()))
from fractions import gcd

lis = []
for x in Xs:
    lis.append(abs(x-X))

G = 0
for l in lis:
    G = gcd(l, G)
print(G)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

query = []
for i in range(H):
    if i%2==0:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))]
    else:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))][::-1]
    query += lis

odd = 0
move = []
last = (0, 0)
for i, (w, q) in enumerate(query):
    if not odd and q%2==0:
        continue
    if odd:
        move.append((*last, i//H+1, w+1))
        if q%2==1:
            odd = 0
        else:
            last = (i//H+1, w+1)
    else:
        if q%2==1:
            odd = 1
            last = (i//H+1, w+1)

print(len(move))
for l in move:
    print(*l)



Fixed submission:
H, W = map(int, input().split())

query = []
for i in range(H):
    if i%2==0:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))]
    else:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))][::-1]
    query += lis

odd = 0
move = []
last = (0, 0)
for i, (w, q) in enumerate(query):
    if odd:
        move.append((last[0], last[1], i//W+1, w+1))
        if q%2==1:
            odd = 0
        else:
            last = (i//W+1, w+1)
    else:
        if q%2==1:
            odd = 1
            last = (i//W+1, w+1)

print(len(move))
for l in move:
    print(*l)

Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

query = []
for i in range(H):
    if i%2==0:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))]
    else:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))][::-1]
    query += lis

odd = 0
move = []
last = (0, 0)
for i, (w, q) in enumerate(query):
    if not odd and q%2==0:
        continue
    if odd:
        move.append((*last, i//H+1, w+1))
        if q%2==1:
            odd = 0
        else:
            last = (i//H+1, w+1)
    else:
        if q%2==1:
            odd = 1
            last = (i//H+1, w+1)

print(len(move))
for l in move:
    print(*l)



Fixed submission:
H, W = map(int, input().split())

query = []
for i in range(H):
    if i%2==0:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))]
    else:
        lis = [(i, j) for i, j in enumerate(list(map(int, input().split())))][::-1]
    query += lis

odd = 0
move = []
last = (0, 0)
for i, (w, q) in enumerate(query):
    if odd:
        move.append((last[0], last[1], i//W+1, w+1))
        if q%2==1:
            odd = 0
        else:
            last = (i//W+1, w+1)
    else:
        if q%2==1:
            odd = 1
            last = (i//W+1, w+1)

print(len(move))
for l in move:
    print(*l)
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, K = mapint()
Xs = list(mapint())

from bisect import bisect_left
pos = []
neg = []

for x in Xs:
    if x>=0:
        pos.append(x)
    else:
        neg.append(-x)

neg = neg[::-1]

ans = 10**18
if len(pos)>=K:
    ans = min(ans, pos[K-1])
if len(neg)>=K:
    ans = min(ans, neg[K-1])
lenp = len(pos)
lenn = len(neg)
for i in range(min(lenp, K)):
    if K-(i+1)<=lenn:
        ans = min(ans, pos[i]*2+neg[K-i-2])
for i in range(min(lenn, K)):
    if K-(i+1)<=lenp:
        ans = min(ans, neg[i]*2+pos[K-i-2])
print(ans)

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

N, K = mapint()
Xs = list(mapint())

pos = []
neg = []

for x in Xs:
    if x>=0:
        pos.append(x)
    else:
        neg.append(-x)

neg = neg[::-1]

ans = 10**18
if len(pos)>=K:
    ans = min(ans, pos[K-1])
if len(neg)>=K:
    ans = min(ans, neg[K-1])
lenp = len(pos)
lenn = len(neg)
if lenn>0:
    for i in range(min(lenp, K)):
        if K-(i+1)<=lenn:
            ans = min(ans, pos[i]*2+neg[K-i-2])
if lenp>0:
    for i in range(min(lenn, K)):
        if K-(i+1)<=lenp:
            ans = min(ans, neg[i]*2+pos[K-i-2])
print(ans)
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)

A, B, C, K = mapint()
for _ in range(K):
    A, B, C = B+C, A+C, A+B
    if abs(A-B)>10**18:
        print('Unfair')
        break
    if A-B==0:
        print(0)
        break
else:
    print(A-B)

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

A, B, C, K = mapint()
if K%2==0:
    print(A-B)
else:
    print(B-A)
Buggy python submission (verdict: Runtime Error):
s = str(input())
K = int(input())

lis = list(set(list(s)))
lis.sort()

ans_lis = []
for i in range(min(5, len(lis))):
    i = lis[i]
    s2 = s
    while 1:
        idx = s2.find(i)
        if idx==-1:
            break
        ans_lis += [s2[idx:idx+l+1] for l in range(min(5, len(s2)-idx-1))]
        s2 = s2[idx+1:]
ans_lis = list(set(ans_lis))
ans_lis.sort()
print(ans_lis[4])

Fixed submission:
s = str(input())
K = int(input())

lis = list(set(list(s)))
lis.sort()

ans_lis = []
for i in range(min(5, len(lis))):
    i = lis[i]
    s2 = s
    while 1:
        idx = s2.find(i)
        if idx==-1:
            break
        ans_lis += [s2[idx:idx+l+1] for l in range(min(5, len(s2)-idx))]
        s2 = s2[idx+1:]
ans_lis = list(set(ans_lis))
ans_lis.sort()
print(ans_lis[K-1])
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
Input = open('input.txt')
def input(): return Input.readline()
def mapint(): return map(int, input().split())

N, C = mapint()
xv = [list(mapint()) for _ in range(N)]
righthand = [0]*N
lefthand = [0]*N
nowv = 0
maxv = -10**18
for i, (x, v) in enumerate(xv):
    nowv += v
    maxv = max(maxv, nowv-x)
    righthand[i] = maxv
nowv = 0
maxv = -10**18
for i, (x, v) in enumerate(xv[::-1]):
    nowv += v
    maxv = max(maxv, nowv-(C-x))
    lefthand[i] = maxv

xv = [(0, 0)] + xv +[(C, 0)]
righthand = [0]+righthand
lefthand = [0]+lefthand
rmax = 0
for i in range(N+1):
    rmax = max(rmax, righthand[i]-xv[i][0]+lefthand[N-i])
lmax = 0
for i in range(N):
    lmax = max(lmax, lefthand[i]-(C-xv[-i-1][0])+righthand[N-i])
print(rmax, lmax)

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

N, C = mapint()
xv = [list(mapint()) for _ in range(N)]
righthand = [0]*N
lefthand = [0]*N
nowv = 0
maxv = -10**18
for i, (x, v) in enumerate(xv):
    nowv += v
    maxv = max(maxv, nowv-x)
    righthand[i] = maxv
nowv = 0
maxv = -10**18
for i, (x, v) in enumerate(xv[::-1]):
    nowv += v
    maxv = max(maxv, nowv-(C-x))
    lefthand[i] = maxv
 
xv = [(0, 0)] + xv +[(C, 0)]
righthand = [0]+righthand
lefthand = [0]+lefthand
rmax = 0
for i in range(N+1):
    rmax = max(rmax, righthand[i]-xv[i][0]+lefthand[N-i])
lmax = 0
for i in range(N):
    lmax = max(lmax, lefthand[i]-(C-xv[-i-1][0])+righthand[N-i])
print(max(rmax, lmax))
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)

S = list(input())
check = [0]*26
if len(S)==26:
    else:
        end = S[-1]
        for i in range(24, -1, -1):
            if ord(S[i])<ord(end):
                S[i] = end
                print(''.join(S[:i+1]))
                break
        else:
            if S[0]=='z':
                print(-1)
            else:
                print(chr(ord(S[0])+1))
else:
    for s in S:
        check[ord(s)-97] = 1
    for i in range(26):
        if not check[i]:
            S.append(chr(i+97))
            break
    print(''.join(S))



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

S = list(input())
# while 1:
if len(S)==26:
    end = S[-1]
    lis = [end]
    for i in range(24, -1, -1):
        if ord(S[i])<ord(end):
            for s in lis:
                if ord(S[i])<ord(s):
                    S[i] = s
                    break
            S = S[:i+1]
            print(''.join(S))
            break
        else:
            lis.append(S[i])
            end = S[i]
    else:
        if S[0]=='z':
            print(-1)
        else:
            S = [chr(ord(S[0])+1)]
            print(S[0])
else:
    check = [0]*26
    for s in S:
        check[ord(s)-97] = 1
    for i in range(26):
        if not check[i]:
            S.append(chr(i+97))
            break
    print(''.join(S))
Buggy python submission (verdict: Runtime Error):
N = int(input())

T, X, B = 0, 0, 0

for _ in range(N):
    t, x, y = map(int, input().split())
    dist = abs(x-X)+abs(y-Y)
    time = t-T
    if time<dist or time%2!=dist%2:
        print('No')
        break
    T, X, Y = t, x, y
else:
    print('Yes')

Fixed submission:
N = int(input())

bt, bx, by = 0, 0, 0

for _ in range(N):
    t, x, y = map(int, input().split())
    dist = abs(x-bx)+abs(y-by)
    time = t-bt
    if time<dist or time%2!=dist%2:
        print('No')
        break
    bt, bx, by = t, x, y
else:
    print('Yes')
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)

s = list(input())
t = list(input())
s.sort()
t.sort(reverse=True)

lens = len(s)
for i in range(lens):
    if s[i]<t[i]:
        print('Yes')
        exit()
    elif s[i]>t[i]:
        print('No')
        exit()
else:
    if len(t)==len(s):
        print('No')
    else:
        print('Yes')

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

s = list(input())
t = list(input())
s.sort()
t.sort(reverse=True)

lens = len(s)
lent = len(t)
for i in range(lens):
    if i==lent:
        print('No')
        exit()
    if s[i]<t[i]:
        print('Yes')
        exit()
    elif s[i]>t[i]:
        print('No')
        exit()
else:
    if len(t)==len(s):
        print('No')
    else:
        print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
N = int(input())
upper = sorted(list(map(int, input().split())))
middle = sorted(list(map(int, input().split())))
lower = list(map(int, input().split()))

ans = 0
for l in lower:
    idx = bisect_left(middle, l)
    if idx>=1:
        for m in middle[:idx]:
            idx2 = bisect_left(upper, m)
            ans += idx2
print(ans)

Fixed submission:
from bisect import bisect_left, bisect_right
N = int(input())
upper = sorted(list(map(int, input().split())))
middle = list(map(int, input().split()))
lower = sorted(list(map(int, input().split())))

ans = 0
for m in middle:
    idx_u = bisect_left(upper, m)
    idx_l = N-bisect_right(lower, m)
    ans += idx_u*idx_l
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
N = int(input())
upper = sorted(list(map(int, input().split())))
middle = sorted(list(map(int, input().split())))
lower = list(map(int, input().split()))

ans = 0
for l in lower:
    idx = bisect_left(middle, l)
    if idx>=1:
        for m in middle[:idx]:
            idx2 = bisect_left(upper, m)
            ans += idx2
print(ans)

Fixed submission:
from bisect import bisect_left, bisect_right
N = int(input())
upper = sorted(list(map(int, input().split())))
middle = list(map(int, input().split()))
lower = sorted(list(map(int, input().split())))

ans = 0
for m in middle:
    idx_u = bisect_left(upper, m)
    idx_l = N-bisect_right(lower, m)
    ans += idx_u*idx_l
print(ans)
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())
query = [[0]*N for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1][b-1] = c
    query[b-1][a-1] = c

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in enumerate(lis):
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

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())
query = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

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())
query = [[0]*N for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1][b-1] = c
    query[b-1][a-1] = c

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in enumerate(lis):
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])

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())
query = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = mapint()
    query[a-1].append((b-1, c))
    query[b-1].append((a-1, c))

Q, K = mapint()
from collections import deque
stack = deque([(K-1, 0, -1)])
dist = [0]*N
while stack:
    now, cnt, per = stack.pop()
    lis = query[now]
    dist[now] = cnt
    for nx, c in lis:
        if nx==per:
            continue
        if c!=0:
            stack.append((nx, cnt+c, now))

for _ in range(Q):
    x, y = mapint()
    print(dist[x-1]+dist[y-1])
Buggy python submission (verdict: Runtime Error):
n = int(input())
As = list(map(str, input().split()))

from collections import deque
b = []
b = deque(b)

for i, a in enumerate(As):
    if i%2==0:
        b.append(a)
    else:
        b.appendleft(a)

if n%2==0:
    print(' '.join(b))
else:
    print(' '.join(b[::-1]))

Fixed submission:
n = int(input())
As = list(map(str, input().split()))

from collections import deque
b = []
b = deque(b)

for i, a in enumerate(As):
    if i%2==0:
        b.append(a)
    else:
        b.appendleft(a)

if n%2==0:
    print(' '.join(b))
else:
    print(' '.join(reversed(b)))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Xs = []
Ys = []
for i in range(N):
    x, y = map(int, input().split())
    Xs.append((x, i))
    Ys.append((y, i))
Xs.sort()
Ys.sort()
Edges = []
for i in range(1, N):
    (x1, v1), (x2, v2) = Xs[i-1], Xs[i]
    Edges.append((abs(x1-x2), v1, v2))
    (y1, v1), (y2, v2) = Ys[i-1], Ys[i]
    Edges.append((abs(y1-y2), v1, v2))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

import heapq
heapq.heapify(Edges)
uf = UnionFind(N)
ans = 0
while Edges:
    d, a, b = heapq.heappop(Edges)
    if not uf.same(a, b):
        ans += d
        uf.union(a, b)
print(ans)

Fixed submission:
N = int(input())
Xs = []
Ys = []
for i in range(N):
    x, y = map(int, input().split())
    Xs.append((x, i))
    Ys.append((y, i))
Xs.sort()
Ys.sort()
Edges = []
for i in range(1, N):
    (x1, v1), (x2, v2) = Xs[i-1], Xs[i]
    Edges.append((abs(x1-x2), v1, v2))
    (y1, v1), (y2, v2) = Ys[i-1], Ys[i]
    Edges.append((abs(y1-y2), v1, v2))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

import heapq
heapq.heapify(Edges)
uf = UnionFind(N)
ans = 0
while Edges:
    d, a, b = heapq.heappop(Edges)
    if not uf.same(a, b):
        ans += d
        uf.union(a, b)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())

lis = []
for i in range(N):
    a, b = map(int, input().split())
    lis = lis + [a]*b
lis.sort()

print(lis[K-1])

Fixed submission:
N, K = map(int, input().split())
from itertools import accumulate
from bisect import bisect_left

lis = []
lis = [tuple(map(int, input().split())) for i in range(N)]
lis.sort()
Bs = [y for x, y in lis]
cB = list(accumulate(Bs))

print(lis[bisect_left(cB, K)][0])
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)

A, B = mapint()
if A>B:
    print('GREATER')
elif A<B:
    print('LESS')
else:
    print('EQUAL')

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

A = int(input())
B = int(input())
if A>B:
    print('GREATER')
elif A<B:
    print('LESS')
else:
    print('EQUAL')
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, A, B = mapint()
Vs = list(mapint())
Vs.sort(reverse=True)
from collections import defaultdict, Counter
from scipy.special import comb

count = defaultdict(int)
c = Counter(Vs)
ans = 0
for i in range(A, B+1):
    val = sum(Vs[:i])/i
    if val>=ans:
        ans = val
        lowest_cnt = 0
        lowest = Vs[i-1]
        for j in range(i):
            if Vs[j]==lowest:
                lowest_cnt += 1
        count[int(ans*2)] += comb(c[lowest], lowest_cnt)

print(ans)
print(count[int(ans*2)])

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

N, A, B = mapint()
Vs = list(mapint())
Vs.sort(reverse=True)
from collections import defaultdict, Counter
from math import factorial, gcd

count = defaultdict(int)
c = Counter(Vs)
ans = 0
ans_2 = (0, 0)
for i in range(A, B+1):
    val = sum(Vs[:i])
    if val/i>=ans-0.000000000000001:
        ans = val/i
        lowest_cnt = 0
        lowest = Vs[i-1]
        for j in range(i):
            if Vs[j]==lowest:
                lowest_cnt += 1
        val, i = val//gcd(val, i), i//gcd(val, i)
        count[(val, i)] += factorial(c[lowest])/factorial(lowest_cnt)/factorial(c[lowest]-lowest_cnt)
        ans_2 = (val, i)

print(ans)
print(round(count[ans_2]))
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)

from collections import defaultdict, deque
Dirc = ('U', 'D', 'R', 'L')
Dirc2 = ('D', 'U', 'L', 'R')
dircn = ((1, 0), (-1, 0), (0, 1), (0, -1))
blocked = defaultdict(int)
sx, sy, tx, ty = mapint()

ans = []
for i in range(4):
    queue = deque([(sx, sy, [])])
    checked = defaultdict(int)
    dirc = Dirc if i%2==0 else Dirc2
    while queue:
        x, y, lis = queue.popleft()
        lis = lis[:]
        flg = 0
        for d, (dy, dx) in zip(dirc, dircn):
            nx, ny = x+dx, y+dy
            if checked[(nx, ny)] or blocked[(nx, ny)]:
                continue
            if nx==sx and ny==sy:
                continue
            if nx==tx and ny==ty:
                flg = 1
                lis.append(d)
                break
            queue.append((nx, ny, lis+[d]))
            checked[(nx, ny)] = 1
        if flg:
            x, y = sx, sy
            for s in lis[:-1]:
                dy, dx = dircn[dirc.index(s)]
                x += dx
                y += dy
                blocked[(x, y)] = 1
            if i%2==0:
                lis = list(reversed(lis))
            ans.extend(lis)
            break
print(''.join(ans))

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

sx, sy, tx, ty = mapint()
ans = ''

ans += 'U'*(ty-sy) + 'R'*(tx-sx)
ans += 'D'*(ty-sy) + 'L'*(tx-sx)
ans += 'L'+'U'*(ty-sy+1)+'R'*(tx-sx+1)+'D'
ans += 'R'+'D'*(ty-sy+1) + 'L'*(tx-sx+1)+'U'

print(ans)