Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
l,n,*ki=map(int,open(0).read().split())
fmax=rmax=0
fl=[]

for ii in range(n):
    f=0
    x=ki[ii:]
    lx=n-ii
    for i in x[:(lx+1)//2]:
        f+=i*2
    for i in x[(lx+1)//2:]:
        f+=(l-i)*2
    if lx%2:
        sa = x[lx//2]
    else:
        sa = l - x[lx // 2]
    f-=sa
    fl.append(f)

for ii in range(n):
    r=0
    x=ki[:n-ii]
    lx=n-ii
    for i in x[:lx//2]:
        r += i * 2
    for i in x[lx//2:]:
        r+=(l-i)*2
    if lx%2:
        sa = l - x[(lx-1) // 2]
    else:
        sa = x[(lx-1)//2]
    r-=sa
    fl.append(r)

print(max(fl))

Fixed submission:
ln, kn, *ki = map(int, open(0).read().split())
# 順回転
pa = ki[-1]
ky = [pa]
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += ki[kn - ys] * 2 + ln - ki[-(ys // 2)] * 2
    # 要素数が奇数の場合
    else:
        pa += ki[kn - ys] * 2 - ki[-(ys // 2) - 1] + ln - ki[-(ys // 2)]
    ky.append(pa)
    kigu *= -1

# 逆回転
pa = ln - ki[0]
ky.append(pa)
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += (ln-ki[ys - 1]) * 2 - ln + ki[ys // 2 - 1] * 2
    # 要素数が奇数の場合
    else:
        pa += (ln-ki[ys - 1]) * 2+ki[ys//2]-ln+ki[ys//2-1]
    ky.append(pa)
    kigu *= -1

print(max(ky))

Buggy python submission (verdict: Time Limit Exceeded):
l,n,*ki=map(int,open(0).read().split())
fmax=rmax=0

for ii in range(n):
    f=0
    x=ki[ii:]
    lx=n-ii
    for i in x[:(lx+1)//2]:
        f+=i*2
    for i in x[(lx+1)//2:]:
        f+=(l-i)*2
    if lx%2:
        sa = x[lx//2]
    else:
        sa = l - x[lx // 2]
    f-=sa
    fmax=max(fmax,f)

for ii in range(n):
    r=0
    x=ki[:n-ii]
    lx=n-ii
    for i in x[:lx//2]:
        r += i * 2
    for i in x[lx//2:]:
        r+=(l-i)*2
    if lx%2:
        sa = l - x[(lx-1) // 2]
    else:
        sa = x[(lx-1)//2]
    r-=sa
    rmax=max(rmax,r)

print(max(fmax,rmax))

Fixed submission:
ln, kn, *ki = map(int, open(0).read().split())
# 順回転
pa = ki[-1]
ky = [pa]
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += ki[kn - ys] * 2 + ln - ki[-(ys // 2)] * 2
    # 要素数が奇数の場合
    else:
        pa += ki[kn - ys] * 2 - ki[-(ys // 2) - 1] + ln - ki[-(ys // 2)]
    ky.append(pa)
    kigu *= -1

# 逆回転
pa = ln - ki[0]
ky.append(pa)
kigu = 1
for ys in range(2, kn + 1):
    # 要素数が偶数の場合
    if kigu == 1:
        pa += (ln-ki[ys - 1]) * 2 - ln + ki[ys // 2 - 1] * 2
    # 要素数が奇数の場合
    else:
        pa += (ln-ki[ys - 1]) * 2+ki[ys//2]-ln+ki[ys//2-1]
    ky.append(pa)
    kigu *= -1

print(max(ky))
Buggy python submission (verdict: Runtime Error):
sou = lambda n: 2 ** (n + 2) - 3
ptn = lambda n: 2 ** (n + 1) - 1


def pate(lv, x):
    if x == 0:
        return 0
    if x < 0:
        return -1
    else:
        for i in range(lv + 1):
            if x < lv - i + sou(i): break
        i -= 1
        re = ptn(i) + 1 + pate(i, x - (lv - i + sou(i) + 1))
        return re


lv, x = map(int, input().split())
print(pate(lv, x))


Fixed submission:
sou = lambda n: 2 ** (n + 2) - 3
ptn = lambda n: 2 ** (n + 1) - 1


def pate(lv, x):
    if x == 0:
        return 0
    if x < 0:
        return -1
    else:
        for i in range(lv + 1):
            if x < lv - i + sou(i):
                i -= 1
                re = ptn(i) + 1 + pate(i, x - (lv - i + sou(i) + 1))
                return re
        else:
            return ptn(lv)


lv, x = map(int, input().split())
print(pate(lv, x))
Buggy python submission (verdict: Runtime Error):
if input()="1":
  print("Hello World")
else:
  a=int(input())
  b=int(input())
  print(a+b)
  

Fixed submission:
if input()=="1":
  print("Hello World")
else:
  a=int(input())
  b=int(input())
  print(a+b)
Buggy python submission (verdict: Runtime Error):
import numpy as np

n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mod = np.zeros(m,dtype="i4")
ans = 0
for a in aa:
    mod=np.roll(mod,a)
    mod[a] += 1
    ans += mod[0]
print(ans)


Fixed submission:
n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mod = {}
ans = 0
zi = 0
for a in aa:
    zi = (zi - a) % m
    ai = (zi + a) % m
    mod.setdefault(ai,0)
    mod[ai] += 1
    ans += mod.get(zi,0)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mods = {0: 0}
ans = 0
for a in aa:
    new_mods = {}
    for mod, cnt in mods.items():
        new_mods[(mod + a) % m] = cnt
    new_mods.setdefault(a, 0)
    new_mods[a] += 1
    mods = new_mods
    ans += mods.get(0, 0)
print(ans)


Fixed submission:
n, m = map(int, input().split())
aa = [int(ak) % m for ak in input().split()]
mod = {}
ans = 0
zi = 0
for a in aa:
    zi = (zi - a) % m
    ai = (zi + a) % m
    mod.setdefault(ai,0)
    mod[ai] += 1
    ans += mod.get(zi,0)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
aa = list(map(int, input().split()))
bit = [[0] * 21 for _ in range(n)]
for i, a in enumerate(aa):
    for j in range(21):
        a, m = divmod(a, 2)
        if m: bit[i][j] = 1
#for x in bit:
#    print(x)
last = [-1] * 21
L = R = 0
ans = 0
while R < n:
    out = []
    nextL = []
    for j in range(21):
        if bit[R][j]:
            if last[j] == -1:
                last[j] = R
            else:
                out.append(j)
                nextL.append(last[j])
                last[j] = R
    #    print(L,R,ans,last)
    if out:
        #        print(out)
        d1 = R - L
        L = max(nextL) + 1
        d2 = R - L + 1
        #        print(d1,d2,(d1+d2)*(d1-d2+1)//2)
        ans += (d1 + d2) * (d1 - d2 + 1) // 2
        for j in range(21):
            if last[j] < L:
                last[j] = -1
    R += 1
d = n - L
ans += d * (d + 1) // 2
print(ans)


Fixed submission:
n = int(input())
aa = list(map(int, input().split()))
bit = [[0] * 21 for _ in range(n)]
for i, a in enumerate(aa):
    for j in range(21):
        a, m = divmod(a, 2)
        if m: bit[i][j] = 1
#for x in bit:
#    print(x)
last = [-1] * 21
L = R = 0
ans = 0
while R < n:
    out = []
    nextL = []
    for j in range(21):
        if bit[R][j]:
            if last[j] == -1:
                last[j] = R
            else:
                out.append(j)
                nextL.append(last[j])
                last[j] = R
    #    print(L,R,ans,last)
    if out:
        #        print(out)
        d1 = R - L
        L = max(nextL) + 1
        d2 = R - L + 1
        #        print(d1,d2,(d1+d2)*(d1-d2+1)//2)
        ans += (d1 + d2) * (d1 - d2 + 1) // 2
        for j in range(21):
            if last[j] < L:
                last[j] = -1
    R += 1
d = n - L
ans += d * (d + 1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, n + 1):
            t = s[l:r]
            i = bisect.bisect_right(dp, t)
            if i>0:
                if t == dp[i-1]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()


Fixed submission:
import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, min(n + 1, l + 6)):
            t = s[l:r]
            i = bisect.bisect_right(dp, t)
            if i > 0:
                if t == dp[i - 1]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()

Buggy python submission (verdict: Runtime Error):
import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, n + 1):
            t = s[l:r]
            i = bisect.bisect_left(dp, t)
            if t == dp[i]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()


Fixed submission:
import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, min(n + 1, l + 6)):
            t = s[l:r]
            i = bisect.bisect_right(dp, t)
            if i > 0:
                if t == dp[i - 1]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, n + 1):
            t = s[l:r]
            if t in dp: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()


Fixed submission:
import bisect

def main():
    s = input()
    k = int(input())
    n = len(s)
    dp = []
    for l in range(n):
        for r in range(l + 1, min(n + 1, l + 6)):
            t = s[l:r]
            i = bisect.bisect_right(dp, t)
            if i > 0:
                if t == dp[i - 1]: continue
            if len(dp) < k:
                bisect.insort(dp, t)
            elif t < dp[-1]:
                dp.pop()
                bisect.insort(dp, t)
    print(dp[-1])

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def main():
    inf = 5000
    n = int(input()[:-1])
    # iより前に色cのj以上が何個あるかがcnts[c][i][j]
    cnts = [[[0] * (n + 1) for _ in range(2 * n + 1)] for __ in range(2)]
    pos = [[0] * n for _ in range(2)]
    for i in range(n * 2):
        c, a = input().split()
        c = (c == "W") * 1
        a = int(a) - 1
        pos[c][a] = i
        for cc in range(2):
            for j in range(n):
                if c == cc and a >= j:
                    cnts[cc][i + 1][j] = cnts[cc][i][j] + 1
                else:
                    cnts[cc][i + 1][j] = cnts[cc][i][j]
    #    for x in cnts:
    #        print(x)
    #    print(pos)

    dp = [[inf] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for w in range(1, n + 1):
        i = pos[1][w - 1]
        dp[0][w] = dp[0][w - 1] + cnts[0][i][0] + cnts[1][i][w - 1]
    for b in range(1, n + 1):
        i = pos[0][b - 1]
        dp[b][0] = dp[b - 1][0] + cnts[0][i][b - 1] + cnts[1][i][0]
    for b in range(1, n + 1):
        for w in range(1, n + 1):
            bi = pos[0][b - 1]
            wi = pos[1][w - 1]
            dp[b][w] = min(dp[b - 1][w] + cnts[0][bi][b - 1] + cnts[1][bi][w],
                           dp[b][w - 1] + cnts[0][wi][b] + cnts[1][wi][w - 1])
    print(dp[n][n])

main()


Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def main():
    inf = 5000
    n = int(input()[:-1])
    # iより前に色cのj以上が何個あるかがcnts[c][i][j]
    cnts = [[[0] * (n + 1) for _ in range(2 * n + 1)] for __ in range(2)]
    pos = [[0] * n for _ in range(2)]
    for i in range(n * 2):
        c, a = input().split()
        c = (c == "W") * 1
        a = int(a) - 1
        pos[c][a] = i
        for cc in range(2):
            for j in range(n):
                if c == cc and a >= j:
                    cnts[cc][i + 1][j] = cnts[cc][i][j] + 1
                else:
                    cnts[cc][i + 1][j] = cnts[cc][i][j]
    #    for x in cnts:
    #        print(x)
    #    print(pos)

    dp = [[inf] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for w in range(1, n + 1):
        i = pos[1][w - 1]
        dp[0][w] = dp[0][w - 1] + cnts[0][i][0] + cnts[1][i][w - 1]
    for b in range(1, n + 1):
        i = pos[0][b - 1]
        dp[b][0] = dp[b - 1][0] + cnts[0][i][b - 1] + cnts[1][i][0]
    for b in range(1, n + 1):
        for w in range(1, n + 1):
            bi = pos[0][b - 1]
            wi = pos[1][w - 1]
            dp[b][w] = min(dp[b - 1][w] + cnts[0][bi][b - 1] + cnts[1][bi][w],
                           dp[b][w - 1] + cnts[0][wi][b] + cnts[1][wi][w - 1])
    print(dp[n][n])

main()
Buggy python submission (verdict: Runtime Error):
def main():
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
              107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
              227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283]
    n=int(input())
    if n%2:
        print(*primes[1:n+1])
    else:
        print(*primes[n])

main()


Fixed submission:
def main():
    primes = [11, 31, 41, 61, 71, 101, 131, 151, 181, 191, 211, 241, 251, 271, 281, 311, 331, 401, 421, 431, 461, 491,
              521, 541, 571, 601, 631, 641, 661, 691, 701, 751, 761, 811, 821, 881, 911, 941, 971, 991, 1021, 1031,
              1051, 1061, 1091, 1151, 1171, 1181, 1201, 1231, 1291, 1301, 1321, 1361, 1381, 1451, 1471, 1481, 1511,
              1531]
    n = int(input())
    print(*primes[:n])

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
to=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=MI1()
    to[u].append(v)
    to[v].append(u)

def far(u,pu=-1,d=0):
    res_u,res_d=u,d
    for v in to[u]:
        if v==pu:continue
        u0,d0=far(v,u,d+1)
        if d0>res_d:
            res_d=d0
            res_u=u0
    return res_u,res_d

s,_=far(0)
t,dist=far(s)
#print(s,t,dist)

def makepath(u,pu,t):
    for v in to[u]:
        if v==pu:continue
        path.append(v)
        if v==t or makepath(v,u,t):return True
        path.pop()
    return False

path=[s]
makepath(s,-1,t)
#print(path)

leg=[]
for u in path[1:-1]:leg.append(len(to[u])-2)
#print(leg)

if sum(leg)+dist+1!=n:
    print(-1)
    exit()

ans=[]
ans.append(1)
u=2
for l in leg:
    for v in range(u+1,u+1+l):
        ans.append(v)
    ans.append(u)
    u+=l+1
ans.append(u)

leg.reverse()
ans2=[]
ans2.append(1)
u=2
for l in leg:
    for v in range(u+1,u+1+l):
        ans2.append(v)
    ans2.append(u)
    u+=l+1
ans2.append(u)

if ans2<ans:ans=ans2
print(*ans)


Fixed submission:
import sys

#sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n=II()
to=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=MI1()
    to[u].append(v)
    to[v].append(u)
#print(to)

def far(u):
    stack=[(u,-1,0)]
    mxd=mxu=-1
    while stack:
        u,pu,d=stack.pop()
        if d>mxd:
            mxd=d
            mxu=u
        for v in to[u]:
            if v==pu:continue
            stack.append((v,u,d+1))
    return mxu,mxd

s,_=far(0)
t,dist=far(s)
#print(s,t,dist)

def makepath(u,t):
    stack=[(u,-1)]
    while stack:
        u,pu=stack.pop()
        while path and path[-1]!=pu:path.pop()
        path.append(u)
        if u==t:return
        for v in to[u]:
            if v==pu:continue
            stack.append((v,u))

path=[s]
makepath(s,t)
#print(path)

leg=[]
for u in path[1:-1]:leg.append(len(to[u])-2)
#print(leg)

if sum(leg)+dist+1!=n:
    print(-1)
    exit()

ans=[]
ans.append(1)
u=2
for l in leg:
    for v in range(u+1,u+1+l):
        ans.append(v)
    ans.append(u)
    u+=l+1
ans.append(u)

leg.reverse()
ans2=[]
ans2.append(1)
u=2
for l in leg:
    for v in range(u+1,u+1+l):
        ans2.append(v)
    ans2.append(u)
    u+=l+1
ans2.append(u)

if ans2<ans:ans=ans2
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def dfs(i=0, cnt=0):
        if i == n: return cnt
        bx, by = b[i]
        res = dfs(i + 1, cnt)
        for j in range(n):
            if fin[j]: continue
            rx, ry = r[j]
            if rx >= bx: break
            if ry < by:
                fin[j] = True
                tmp = dfs(i + 1, cnt + 1)
                fin[j] = False
                res = max(res, tmp)
        return res

    n = int(input())
    r = [list(map(int, input().split())) for _ in range(n)]
    b = [list(map(int, input().split())) for _ in range(n)]
    r.sort(key=itemgetter(0, 1))
    b.sort(key=itemgetter(0, 1))
    # print(r)
    # print(b)
    fin = [False] * n
    print(dfs())

main()


Fixed submission:
from heapq import *
from bisect import *
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    hp = []
    for _ in range(n):
        a, b = map(int, input().split())
        heappush(hp, [a, 1, b])
    for _ in range(n):
        a, b = map(int, input().split())
        heappush(hp, [a, 0, b])
    yy = []
    ans = 0
    while hp:
        x, q, y = heappop(hp)
        if q:
            insort(yy, y)
        else:
            i = bisect_left(yy, y)
            if i > 0:
                del yy[i - 1]
                ans += 1
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def dfs(i=0, cnt=0):
        if i == n: return cnt
        bx, by = b[i]
        res = dfs(i + 1, cnt)
        for j in range(n):
            if fin[j]: continue
            rx, ry = r[j]
            if rx >= bx: break
            if ry < by:
                fin[j] = True
                tmp = dfs(i + 1, cnt + 1)
                fin[j] = False
                res = max(res, tmp)
        return res

    n = int(input())
    r = [list(map(int, input().split())) for _ in range(n)]
    b = [list(map(int, input().split())) for _ in range(n)]
    r.sort(key=itemgetter(0, 1))
    b.sort(key=itemgetter(0, 1))
    # print(r)
    # print(b)
    fin = [False] * n
    print(dfs())

main()


Fixed submission:
from heapq import *
from bisect import *
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    hp = []
    for _ in range(n):
        a, b = map(int, input().split())
        heappush(hp, [a, 1, b])
    for _ in range(n):
        a, b = map(int, input().split())
        heappush(hp, [a, 0, b])
    yy = []
    ans = 0
    while hp:
        x, q, y = heappop(hp)
        if q:
            insort(yy, y)
        else:
            i = bisect_left(yy, y)
            if i > 0:
                del yy[i - 1]
                ans += 1
    print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a<2*k:return a%2^(k%2==0)
        if a%k==0:return a//k
        a-=a//k+1

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a%k==0:return a//k
        once=a//k+1
        seg=a%k
        cnt=(seg+once-1)//once
        a-=cnt*once

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")

Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a%k==0:return a//k
        a-=a//k+1

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def grundy(a,k):
    while 1:
        if a<k:return 0
        if a%k==0:return a//k
        once=a//k+1
        seg=a%k
        cnt=(seg+once-1)//once
        a-=cnt*once

win=0
for _ in range(II()):
    a,k=MI()
    win^=grundy(a,k)

if win:print("Takahashi")
else:print("Aoki")
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k2 = k * 2
    t = [[0] * k2 for _ in range(k2)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        x = (x + k) % k2
        y = (y + k) % k2
        t[x][y] += 1
    # p2D(t)
    # print()
    for i in range(k2):
        ti = t[i]
        for j in range(1, k2):
            ti[j] += ti[j - 1]
    for j in range(k2):
        for i in range(1, k2):
            t[i][j] += t[i - 1][j]
    # p2D(t)
    ans = 0
    for i in range(k - 1, k2):
        for j in range(k - 1, k2):
            cur = t[i][j]
            if i - k >= 0: cur -= t[i - k][j]
            if j - k >= 0: cur -= t[i][j - k]
            if i >= k and j >= k: cur += t[i - k][j - k]
            ans=max(ans,cur,n-cur)
    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n, k = map(int, input().split())
    k2 = k * 2
    t = [[0] * k2 for _ in range(k2)]
    for _ in range(n):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "W": x += k
        x %= k2
        y %= k2
        t[x][y] += 1
        x = (x + k) % k2
        y = (y + k) % k2
        t[x][y] += 1
    # p2D(t)
    # print()
    for i in range(k2):
        ti = t[i]
        for j in range(1, k2):
            ti[j] += ti[j - 1]
    for j in range(k2):
        for i in range(1, k2):
            t[i][j] += t[i - 1][j]
    # p2D(t)
    ans = 0
    for i in range(k - 1, k2):
        for j in range(k - 1, k2):
            cur = t[i][j]
            if i - k >= 0: cur -= t[i - k][j]
            if j - k >= 0: cur -= t[i][j - k]
            if i >= k and j >= k: cur += t[i - k][j - k]
            ans=max(ans,cur,n-cur)
    print(ans)

main()