Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

S=list(ns())
S.reverse()

modmap=[[0]*10 for i in range(10**5)]
for i in range(10):
    modmap[0][i]=i

for i in range(1,10**5):
    for j in range(10):
        modmap[i][j]=(modmap[i-1][j]*10)%13


q_list=[]
moda=0
for i in range(len(S)):
    if(S[i]=='?'):
        q_list.append(i)
    else:
        moda=(moda+modmap[i][int(S[i])])%13


modlist=[[0]*13 for i in range(len(q_list))]
mlist=[i for i in range(13)]

for i in range(10):
    modlist[0][modmap[q_list[0]][i]]=1

for i in range(1,len(q_list)):
    for j in range(10):
        tmpmod=modmap[q_list[i]][j]
        for k in range(13):
            modlist[i][(tmpmod+k)%13]+=(modlist[i-1][k]%(10**9+7))

print(modlist[len(q_list)-1][mlist[5-moda]]%(10**9+7))

Fixed submission:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

A,B=nm()

print((A+B)//2 if (A+B)%2==0 else 'IMPOSSIBLE')

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

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

S=list(ns())
S.reverse()

modmap=[[0]*10 for i in range(10**5)]
for i in range(10):
    modmap[0][i]=i

for i in range(1,10**5):
    for j in range(10):
        modmap[i][j]=(modmap[i-1][j]*10)%13


q_list=[]
moda=0
for i in range(len(S)):
    if(S[i]=='?'):
        q_list.append(i)
    else:
        moda=(moda+modmap[i][int(S[i])])%13


modlist=[[0]*13 for i in range(len(q_list))]
mlist=[i for i in range(13)]

for i in range(10):
    modlist[0][modmap[q_list[0]][i]]=1

for i in range(1,len(q_list)):
    for j in range(10):
        tmpmod=modmap[q_list[i]][j]
        for k in range(13):
            modlist[i][(tmpmod+k)%13]+=modlist[i-1][k]

print(modlist[len(q_list)-1][mlist[5-moda]]%(10**9+7))


Fixed submission:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

A,B=nm()

print((A+B)//2 if (A+B)%2==0 else 'IMPOSSIBLE')
Buggy python submission (verdict: Runtime Error):
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

p=[0]*3
p[0]=ns()
p[1]=ns()
p[2]=ns()
turn='A'
d={'A':0,'B':1,'C':2}

while(len[p[d[turn]]]==0):
	tmp=p[d[turn]][0]
	p[d[turn]][0]=[]	
	turn=tmp


print(d[turn])


Fixed submission:
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

p=[0]*3
p[0]=list(ns())
p[1]=list(ns())
p[2]=list(ns())
turn='a'
d={'a':0,'b':1,'c':2}

hand=p[d[turn]]
ch=len(hand)
while(ch!=0):
  turn=p[d[turn]].pop(0)
  hand=p[d[turn]]
  ch=len(hand)


print(turn.upper())
Buggy python submission (verdict: Runtime Error):
def main():
    n,x=map(int,input().split())
    a,b=n-x,x
    if(a<b):
       a,b=b,a
    path_length = calc_path(a,b,n)
    print(path_length)

def  calc_path(a1,b1,c1):
    q , mod=divmod(a1,b1)
    count=0
    if mod==0:
         c2=c1+2*b1*q-b1
         return c2
    else:
        count=count+1
        c2=c1+2*b1*q
        a2=a1-b1*q
        b2=b1
        if(a2<b2):
           a2,b2=b2,a2
        return calc_path(a2,b2,c2)
if __name__=='__main__':
  main()


Fixed submission:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=sum(l[0::2])
print(ans)

Buggy python submission (verdict: Runtime Error):
def main():
    n,x=map(int,input().split())
    a,b=n-x,x
    if(a<b):
       a,b=b,a
    path_length = calc_path(a,b,n)
    print(path_length)

def  calc_path(a1,b1,c1):
    q , mod=divmod(a1,b1)
    count=0
    if mod==0:
         c2=c1+b1*(q+1)
         return c2
    else:
        count=count+1
        c2=c1+b1*(q+1)
        a2=a1-b1*q
        b2=b1
        if(a2<b2):
           a2,b2=b2,a2
        return calc_path(a2,b2,c2)
if __name__=='__main__':
  main()


Fixed submission:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=sum(l[0::2])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))

mul = 1
for i in range(k):
    mul *= a[i]
pre = mul

ans = []
for i in range(k, n):
    mul *= a[i]
    mul //= a[i-k]
    if pre < mul:
        ans.append("Yes")
    else:
        ans.append("No")
    pre = mul
print("\n".join(ans))

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = []
for i in range(k, n):
    if a[i-k] < a[i]:
        ans.append("Yes")
    else:
        ans.append("No")
print("\n".join(ans))
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()
COUNT = x.count('1')
mod1 = COUNT - 1
mod2 = COUNT + 1

# その桁に1が立っていた時の余り
mod = [[0, 0] for _ in range(n+1)]
mult = 1
mod[0][0] = 1 % mod1
mod[0][1] = 1 % mod2
for i in range(1, n+1):
    mod[i][0] = (mod[i-1][0] * (2 % mod1)) % mod1
    mod[i][1] = (mod[i-1][1] * (2 % mod2)) % mod2

all_mod1 = 0
all_mod2 = 0
for i in range(n):
    if x[i] == '1':
        all_mod1 = (all_mod1 + mod[n-1-i][0])
        all_mod2 = (all_mod2 + mod[n-1-i][1])
all_mod1 %= mod1
all_mod2 %= mod2

def popcount(idx):
    idx -= 1
    ret = 0
    if x[idx] == '1':
        ret = (all_mod1 - mod[n-1-idx][0]) % mod1
    else:
        ret = (all_mod2 + mod[n-1-idx][1]) % mod2
    return ret

bit_cnt_table = [0 for _ in range(n+1)]
bit_cnt_table[1] = 1
base = 0
i = 2
while i <= n:
    if i % (2 ** base) == 0:
        base += 1
    bit_cnt_table[i] = 1 + bit_cnt_table[i - 2**(base)]
    i += 1

def func(num):
    if bit_cnt_table[num] == 0:
        return 0
    return num % bit_cnt_table[num]

f = [-1 for _ in range(n+1)]
f[0] = 0
f[1] = 1
for i in range(2, n+1):
    tmp = func(i)
    f[i] = 1 + f[tmp]
# print("all_mod", all_mod1, all_mod2)
ans = []
for i in range(1, n+1):
    p = popcount(i)
    ans_i = 1 + f[p]
    # print(i, p, ans_i)
    ans.append(str(ans_i))
print("\n".join(ans))
# print(f)
# print(bit_cnt_table)

Fixed submission:
n = int(input())
x = input()
COUNT = x.count('1')
mod1 = COUNT - 1
mod2 = COUNT + 1

# その桁に1が立っていた時の余り
mod = [[0, 0] for _ in range(n+1)]
mult = 1
if mod1 != 0:
    mod[0][0] = 1 % mod1
mod[0][1] = 1 % mod2
for i in range(1, n+1):
    if mod1 != 0:
        mod[i][0] = (mod[i-1][0] * (2 % mod1)) % mod1
    mod[i][1] = (mod[i-1][1] * (2 % mod2)) % mod2

all_mod1 = 0
all_mod2 = 0
for i in range(n):
    if x[i] == '1':
        if mod1 != 0:
            all_mod1 = (all_mod1 + mod[n-1-i][0])
        all_mod2 = (all_mod2 + mod[n-1-i][1])
if mod1 != 0:
    all_mod1 %= mod1
all_mod2 %= mod2

def popcount(idx):
    idx -= 1
    ret = 0
    if x[idx] == '1':
        if mod1 != 0:
            ret = (all_mod1 - mod[n-1-idx][0]) % mod1
        else:
            ret = -1
    else:
        ret = (all_mod2 + mod[n-1-idx][1]) % mod2
    return ret

bit_cnt_table = [0 for _ in range(n+1)]
bit_cnt_table[1] = 1
base = 0
i = 2
while i <= n:
    if i % (2 ** base) == 0:
        base += 1
    bit_cnt_table[i] = 1 + bit_cnt_table[i - 2**(base)]
    i += 1

def func(num):
    if bit_cnt_table[num] == 0:
        return 0
    return num % bit_cnt_table[num]

f = [-1 for _ in range(n+1)]
f[0] = 0
f[1] = 1
for i in range(2, n+1):
    tmp = func(i)
    f[i] = 1 + f[tmp]
# print("all_mod", all_mod1, all_mod2)
ans = []
for i in range(1, n+1):
    p = popcount(i)
    if p == -1:
        ans_i = 0
    else:
        ans_i = 1 + f[p]
    # print(i, p, ans_i)
    ans.append(str(ans_i))
print("\n".join(ans))
# print(f)
# print(bit_cnt_table)
Buggy python submission (verdict: Runtime Error):
import sys
input = lambda: sys.stdin.readline().rstrip()
import bisect

def cumsum(a):
   r = [0]
   for v in a:
      r.append(r[-1] + v)
   return r

def solve():
   n, m, k = map(int, input().split())
   a = cumsum(list(map(int, input().split())))
   b = cumsum(list(map(int, input().split())))

   ans = 0
   for a_num, v in enumerate(a):
      tmp = 0
      if k >= v:
         b_num = bisect.bisect_right(b, k - v) - 1
         tmp = a_num + b_num
      ans = max(ans, tmp)
   print(ans)

def solve2():
   n, m, k = map(int, input().split())
   a = list(map(int, input().split()))
   b = list(map(int, input().split()))

   # bの累積和
   b_sums = cumsum(b)
   ans = 0
   a = [0] + a

   j = len(b_sums) - 1
   a_sum = 0
   for i, v in enumerate(a):
      a_sum += v
      while a_sum + b_sums[j] > k:
         j -= 1
         if j < 0:
            break
      ans = max(ans, i + j)
   print(ans)


solve2()


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
import bisect

def cumsum(a):
   r = [0]
   for v in a:
      r.append(r[-1] + v)
   return r

n, m, k = map(int, input().split())
a = cumsum(list(map(int, input().split())))
b = cumsum(list(map(int, input().split())))

ans = 0
for a_num, v in enumerate(a):
   tmp = 0
   if k >= v:
      b_num = bisect.bisect_right(b, k - v) - 1
      tmp = a_num + b_num
   ans = max(ans, tmp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = Counter(a)
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)

Fixed submission:
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
a = sorted(list(set(a)))
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

ans = a[0]
for v in a[1:]:
    ans *= v
if ans > 10**18:
    print(-1)
else:
    print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
for v in a:
    ans *= v
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n, m = map(int, input().split())

s = 1
f = n
ans = []
d = defaultdict(lambda: False)
i = 0

used = []
while i < m:
    # print(s, f, i)
    tmp = abs(s - f)
    a, b = min(tmp, n - tmp), max(tmp, n - tmp)
    if d[a] or d[b]:
        f -= 1
        continue
    d[a] = True
    d[b] = True
    ans.append(f"{s} {f}")
    used.append(s)
    used.append(f)
    s += 1
    f -= 1
    i += 1
f = False
for i in used:
    if i <= 0 or n < i:
        f = True
if f:
    ans = []
    while i < m:
    # print(s, f, i)
    tmp = abs(s - f)
    a, b = min(tmp, n - tmp), max(tmp, n - tmp)
    if d[a] or d[b]:
        s += 1
        continue
    d[a] = True
    d[b] = True
    ans.append(f"{s} {f}")
    used.append(s)
    used.append(f)
    s += 1
    f -= 1
    i += 1

print("\n".join(ans))

Fixed submission:
n, m = map(int, input().split())

s1 = 1
f1 = n // 2
s2 = f1 + 1
f2 = n
if (f1 - s1) % 2 == (f2 - s2) % 2:
    f2 -= 1
ans = []
while f1 > s1:
    ans.append(f"{s1} {f1}")
    s1 += 1
    f1 -= 1

while f2 > s2:
    ans.append(f"{s2} {f2}")
    s2 += 1
    f2 -= 1

print("\n".join(ans[:m]))
Buggy python submission (verdict: Time Limit Exceeded):
import math

k = int(input())

ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            ans += math.gcd(math.gcd(i, j), l)
print(ans)


Fixed submission:
from math import gcd

k = int(input())

ans = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            ans += gcd(gcd(i, j), k)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque, defaultdict
n, x, y = map(int, input().split())

edges = defaultdict(lambda: [])
for i in range(1, n):
    edges[i].append(i+1)
    edges[i+1].append(i)
edges[x].append(y)
edges[y].append(x)

# 幅優先
counter = [0 for i in range(n)]
for i in range(1, n+1):
    d = deque()
    dist = [-1 for _ in range(n+1)]
    d.append((i, -1))
    while len(d) > 0:
        e, pre_dist = d.popleft()
        if dist[e] != -1:
            continue
        else:
            dist[e] = pre_dist + 1
            for next_e in edges[e]:
                if not is_checked[next_e]:
                    d.append((next_e, pre_dist+1))
    for j in range(i+1, n+1):
        counter[dist[j]-1] += 1
print("\n".join(list(map(str, counter[1:]))))


Fixed submission:
from collections import deque, defaultdict
n, x, y = map(int, input().split())

edges = defaultdict(lambda: [])
for i in range(1, n):
    edges[i].append(i+1)
    edges[i+1].append(i)
edges[x].append(y)
edges[y].append(x)

# 幅優先
counter = [0 for i in range(n)]
for i in range(1, n+1):
    d = deque()
    is_checked = [False for _ in range(n+1)]
    dist = [-1 for _ in range(n+1)]
    dist[i] = 0
    d.append((i, 0))
    while len(d) > 0:
        e, pre_dist = d.popleft()
        if is_checked[e]:
            continue
        else:
            is_checked[e] = True
            dist[e] = pre_dist + 1
            for next_e in edges[e]:
                if not is_checked[next_e]:
                    d.append((next_e, pre_dist+1))
    for j in range(i+1, n+1):
        counter[dist[j]-1] += 1
print("\n".join(list(map(str, counter[1:]))))
Buggy python submission (verdict: Runtime Error):
from collections import deque
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

reds = deque(p)
greens = deque(q)
uncolor = deque(r)

# できるだけ値が大きいやつを使いたい
ans = 0
red_cnt = 0
green_cnt = 0
while True:
    # print(red_cnt, green_cnt, reds, greens, uncolor)
    if red_cnt == x and green_cnt == y:
        break
    if len(reds) == 0 or red_cnt == x:
        if greens[0] > uncolor[0]:
            eat = greens.popleft()
        else:
            eat = uncolor.popleft()
        ans += eat
        green_cnt += 1
    elif len(greens) == 0 or green_cnt == y:
        if reds[0] > uncolor[0]:
            eat = reds.popleft()
        else:
            eat = uncolor.popleft()
        ans += eat
        red_cnt += 1
    else:
        if red_cnt < x:
            if reds[0] > greens[0]:
                if reds[0] > uncolor[0]:
                    eat = reds.popleft()
                else:
                    eat = uncolor.popleft()
                ans += eat
                red_cnt += 1
            else:
                if greens[0] > uncolor[0]:
                    eat = greens.popleft()
                else:
                    eat = uncolor.popleft()
                ans += eat
                green_cnt += 1
        else:
            if greens[0] > uncolor[0]:
                eat = greens.popleft()
            else:
                eat = uncolor.popleft()
            ans += eat
            green_cnt += 1
print(ans)





Fixed submission:
from collections import deque
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
p = p[:x]
q.sort(reverse=True)
q = q[:y]
r.sort(reverse=True)
apples = p + q + r
apples.sort(reverse=True)
ans = sum(apples[:x+y])

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

n, s = map(int, input().split())
a = list(map(int, input().split()))
p = 998244353

dp = [[[0, 0, 0] for _ in range(s+1)] for _ in range(n+1)]
for i in range(n):
    dp[0][0][0] = 1
    for j in range(s+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        if j + a[i] <= s:
            dp[i+1][j+a[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a[i]][2] += dp[i][j][0] + dp[i][j][1]

print(dp[n][s][2] % p)

Fixed submission:
N,S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353

dp = [0] * (S+1)
ans = 0
for i in range(N):
    ndp = dp[:]
    if A[i] <= S:
        ndp[A[i]] = (ndp[A[i]] + i+1) % mod
    for j in range(S):
        if j+A[i] <= S:
            ndp[j+A[i]] = (ndp[j+A[i]] + dp[j]) % mod
    ans = (ans + ndp[S]) % mod
    dp = ndp[:]
print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, s = map(int, input().split())
a = list(map(int, input().split()))
p = 998244353

dp = [[[0, 0, 0] for _ in range(s+1)] for _ in range(n+1)]
for i in range(n):
    dp[0][0][0] = 1
    for j in range(s+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        if j + a[i] <= s:
            dp[i+1][j+a[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a[i]][2] += dp[i][j][0] + dp[i][j][1]

print(dp[n][s][2] % p)

Fixed submission:
N,S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353

dp = [0] * (S+1)
ans = 0
for i in range(N):
    ndp = dp[:]
    if A[i] <= S:
        ndp[A[i]] = (ndp[A[i]] + i+1) % mod
    for j in range(S):
        if j+A[i] <= S:
            ndp[j+A[i]] = (ndp[j+A[i]] + dp[j]) % mod
    ans = (ans + ndp[S]) % mod
    dp = ndp[:]
print (ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
h, w =  map(int, input().split())
s = [[i for i in list(str(input()))] for i in range(h)]
INF = 10**9
dp = [[INF for _ in range(w)] for _ in range(h)]

if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

que = deque()
que.append((0, 0))
while len(que) > 0:
    y, x = que.popleft()
    if y + 1 < h:
        if s[y+1][x] == "#":
            dp[y+1][x] = min(dp[y+1][x], dp[y][x]+1)
        else:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x])
        que.append((y+1, x))
    if x + 1 < w:
        if s[y][x+1] == "#":
            dp[y][x+1] = min(dp[y][x+1], dp[y][x]+1)
        else:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x])
        que.append((y, x+1))
print(dp[h-1][w-1])


Fixed submission:
from collections import deque
h, w =  map(int, input().split())
s = [[i for i in list(str(input()))] for i in range(h)]
INF = 10**9
dp = [[INF for _ in range(w)] for _ in range(h)]


if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
que = deque()
que.append((0, 0))
is_checked = [[False for _ in range(w)] for _ in range(h)]
while len(que) > 0:
    y, x = que.popleft()
    if y + 1 < h:
        if s[y][x] != s[y+1][x]:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x]+1)
        else:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x])
        if not is_checked[y+1][x]:
            que.append((y+1, x))
            is_checked[y+1][x] = True
    if x + 1 < w:
        if s[y][x] != s[y][x+1]:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x]+1)
        else:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x])
        if not is_checked[y][x+1]:
            que.append((y, x+1))
            is_checked[y][x+1] = True
if s[h-1][w-1] == "#":
    dp[h-1][w-1]+=1
print(dp[h-1][w-1]//2)
Buggy python submission (verdict: Runtime Error):
from math import ceil
h, w = map(int, input().split())

if h == 1 or w == 1:
    print(0)
    exit()
if w % 2 == 0:
    ans = (w // 2) * h
else:
    ans = (w // 2) * h + (ceil(h / 2))
print(ans)

Fixed submission:
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14,
     1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input()) - 1
print(l[k])
Buggy python submission (verdict: Time Limit Exceeded):
s = str(input())
f = True
q = int(input())
for i in range(q):
    q = list(map(str, input().split()))
    if int(q[0]) == 1:
        if f:
            f = False
        else:
            f = True
    else:
        f_i = int(q[1])
        if f_i == 1:
            if f:
                s = q[2] + s
            else:
                s = s + q[2]
        else:
            if f:
                s = s + q[2]
            else:
                s = q[2] + s
if f:
    print(s)
else:
    print(s[::-1])

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

s = str(input().rstrip())
ans = deque(list(s))

f = True
q = int(input())
for i in range(q):
    q = list(map(str, input().split()))
    if int(q[0]) == 1:
        if f:
            f = False
        else:
            f = True
    else:
        f_i = int(q[1])
        if f_i == 1:
            if f:
                ans.appendleft(q[2])
            else:
                ans.append(q[2])
        else:
            if f:
                ans.append(q[2])
            else:
                ans.appendleft(q[2])
ans = list(ans)
if f:
    print("".join(ans))
else:
    print("".join(ans[::-1]))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) -  r
        return ans

    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans

bottom = 0
top = 2*(10**18) + 2


while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid - 10**18-1) < k:
        bottom = mid
    else:
        top = mid

print(int(top - 10**18-1))


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
minus = [-x for x in a if x < 0]
plus = [x for x in a if x >= 0]

minus.sort()
plus.sort()

def cnt(x):
    ans = 0
    if x < 0:
        x = -x
        r = 0
        for num in minus[::-1]:
            while r < len(plus) and plus[r] * num < x:
                r += 1
            ans += len(plus) -  r
        return ans

    r = 0
    for num in minus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(minus) and minus[r] * num <= x:
            r += 1
        ans += r
    r = 0
    for num in plus[::-1]:
        if num * num <= x: ans -= 1
        while r < len(plus) and plus[r] * num <= x:
            r += 1
        ans += r
    ans //= 2
    ans += len(minus) * len(plus)
    return ans

bottom = 0
top = 2*(10**18) + 2


while top - bottom > 1:
    mid = (top + bottom) // 2
    if cnt(mid - 10**18-1) < k:
        bottom = mid
    else:
        top = mid

print(int(top - 10**18-1))