Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key = lambda x: -x[0])
ab.sort(key = lambda x: -x[1])
f = [0] * M
cnt, ans = 0, 0
bit = BIT(M+1)
for a, b in ab:
    if M-a >= 0 and bit.sum(M-a+1) - bit.sum(0, 1) <= M-a:
        ans += b
        cnt += 1
        if cnt == M:
            break
        bit.add(M-a+1, 1)
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from fractions import Fraction

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(N+1)]
    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(N)]
ab.sort(key = lambda x: x[0])
ab.sort(key = lambda x: -x[1])
ans = 0
# print(ab)
uf = UnionFind(M+2)
bit = BIT(M)
ub = M+1
for a, b in ab:
    # print([bit.sum(i) for i in range(1, M+1)])
    i = M-a+1
    # print(bit.sum(i), i, ub)
    if 0 < i and bit.sum(i) < i:
        ans += b
        if bit.sum(i-1) == bit.sum(i):
            bit.add(i, 1)
            uf.unite(i, i+1)
        else:
            lb, ub = 0, i
            while lb+1 < ub:
                mid = (lb+ub)//2
                if uf.same(mid, ub):
                    ub = mid
                else:
                    lb = mid
            bit.add(lb, 1)
            uf.unite(lb, ub)
# print([bit.sum(i) for i in range(1, M+1)])
# print()
print(ans)
n,k = map(int,input().split())
H= list(map(int,input().split()))
H.sort()
for i in range(k):
  H.pop()
cont=0
for i in range(len(H)):
  while H[i]>0:
    H[i]-=1
    cont+=1
print(cont)


### FIXED CODE ###

n,k = map(int,input().split())
H= list(map(int,input().split()))
if(k<n):
  H.sort()
  for i in range(k):
    H.pop()
  cont=0
  for i in range(len(H)):
    cont+= H[i]
  print(cont)
else:
  print(0)
from sys import stdin
n,m = map(int,stdin.readline().split()
print("Yes" if n==m else "No")

### FIXED CODE ###

from sys import stdin
n,m = map(int,stdin.readline().split())
print("Yes" if n==m else "No")
from bisect import insort_left
n = int(input())
s = input()
q = int(input())
dic = {}
for ind, c in enumerate(s):
    if c in dic:
        dic[c].append(ind)
    else:
        dic[c] = [ind]

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        find_c = False
        for c, li in dic.items():
            if a in li:
                li.remove(a)
            if c==b:
                insort_left(li, a)
                find_c = True
        if not find_c:
            dic[b] = [a]
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li[0]<=b and li[-1]>=a:
                tmp += 1
        print(tmp)

### FIXED CODE ###

from bisect import insort_left, bisect_left
n = int(input())
s = list(input())
Q = int(input())
query = [input() for _ in range(Q)]
dic = {chr(i+ord('a')):[] for i in range(26)}
for ind, c in enumerate(s):
    dic[c].append(ind)

for q in query:
    t, a, b = q.split()
    a = int(a)-1
    if t=='1':
        if s[a]==b:
            continue
        ind = bisect_left(dic[s[a]], a)
        dic[s[a]].pop(ind)
        insort_left(dic[b], a)
        s[a] = b
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li and a<=li[-1] and li[bisect_left(li, a)] <= b:
                tmp += 1
        print(tmp)
import sys
import bisect

def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())


def main():
  X,N = LI()[:]
  P = LI()
  P.sort()
  print(X,N)
  print(P)

  if N==0:
    print(X)
    exit()
    
  index = bisect.bisect_left(P, X)
  
  l = index
  r = index
  for i in range(0,100):
    up = X + i
    down = X - i
    
    if l < 0:
      print(down)
      break
    
    if r > N:
      print(up)
      break
     
    # Left優先
    if P[l] != down:
      print(down)
      break
     
    if P[r] != up:
      print(up)
      break
    
    l -= 1
    r += 1
    
if __name__ == '__main__':
	main()


### FIXED CODE ###

import sys
import bisect

def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())


def main():
  X,N = LI()[:]
  if N > 0:
    P = LI()
    P.sort()
  else:
    print(X)
    exit()
  
  #print(X,N)
  #print(P)
  
  index = bisect.bisect_left(P, X)
  #print("index=",index)
  if index >= N :
    print(X)
    exit()
    
  l = index
  r = index
  for i in range(0,200):
    up = X + i
    down = X - i
    
    #print("l=",l,"r=",r)
     
    # Left優先
    if l < 0 or P[l] != down:
      print(down)
      break

    if r >= N or P[r] != up:
      print(up)
      break
    
    l -= 1
    r += 1
    
if __name__ == '__main__':
	main()
import sys
sys.setrecursionlimit(10**4)

n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5+1)
n = int(input())
if n==1:
  print(0)
  exit()
from collections import defaultdict
edge = defaultdict(list)
for i in range(n-1):
  u, v, w = list(map(int, input().split()))
  edge[u].append((v, w))
  edge[v].append((u, w))
graph = [-1 for i in range(n+1)]

def dfs(x, c):
  nexts = edge.get(x)
  if nexts is None:
    return
  if graph[x]!=-1:
    return
  else:
    graph[x] = c
  for y, w in nexts:
    if w%2:
      dfs(y, not c)
    else:
      dfs(y, c)

dfs(1, 0)
for i in range(1, n+1):
  print(int(graph[i]))
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[2::2] = False
        self.is_prime[3::3] = False
        self.is_prime[5::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                self.is_prime[i * i::i] = False
    
    def factorize(self, x, return_all=False):
        assert x >= 2
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0 or return_all:
                result.append((p, exp))
            if p * p > x and return_all is False:
                break
        if x > 1:
            result.append((x, 1))
        return result


N = int(input())
M = 10**9 + 7
A = list(map(int, input().split()))

sieve = SieveOfEratosthenes(max(A))
A = [sieve.factorize(a, return_all=True) for a in A if a >= 2]

lcm = A[0]
for i in range(1, len(A)):
    lcm = [(p, max(e1, e2)) for (p, e1), (_, e2) in zip(lcm, A[i])]

ans = 0
for i in range(len(A)):
    items = [(p, e1 - e2) for (p, e1), (_, e2) in zip(lcm, A[i])]
    b = 1
    for p, e in items:
        b = b * pow(p, e, M) % M
    ans = (ans + b) % M
print(ans)
    

### FIXED CODE ###

import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[2::2] = False
        self.is_prime[3::3] = False
        self.is_prime[5::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x, return_dict=False):
        if x == 1:
            return {1:1} if return_dict else [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        if return_dict:
            result = {p: e for p, e in result}
        return result


N = int(input())
M = 10**9 + 7
A = list(map(int, input().split()))

sieve = SieveOfEratosthenes(10**3)
F = [sieve.factorize(a, return_dict=True) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M

B = [val * pow(a, M - 2, M) % M for a in A]
print(sum(B) % M)
X,N = map(int,input().split())
P = list(map(int,input().split()))

P_n = [i for i in range(1,101,1) if i not in P]
abs_value = [abs(X-P_n[j]) for j in range(len(P_n))]

import sys

min_abs = min(abs_value)
for k in range(len(abs_value)):
    if abs_value[k] == min_abs:
        print(P_n[k])
        sys.exit()

### FIXED CODE ###

X, N = map(int, input().split())
 
p = list(map(int, input().split()))
 
p_none = [i for i in range(110) if i not in p]
p_none_sa = [abs(p_none[i]-X) for i in range(len(p_none))]
 
import sys
 
min_p_none = min(p_none_sa)
for i in range(len(p_none_sa)):
    if p_none_sa[i] == min_p_none:
        print(p_none[i])
        sys.exit()
a = int(input().split())
print(a[1]*a[0], (a[1]+a[0])*2)


### FIXED CODE ###

a, b = map(int, input().split())
print(a * b, (a + b) * 2)
s = list(str(input()))
k = int(input())
zisyo = []
for i in range(len(s)):
    count = 0
    st = s[i]
    zisyo.append(st)
    while count <= n:
        count = count + 1
        try:
            st = st + s[i + count]
            zisyo.append(st)
        except:
            pass
    
zisyosort = list(sorted(list(set(zisyo))))
print(zisyosort[k-1])
        

### FIXED CODE ###


s = str(input())
k = int(input())
kouho = [s]

for i in range(len(s)):
    for plus in range(k+1):
        st = s[i:i + plus]
        kouho.append(st)
so = list(sorted(set(kouho)))
if '' in so:
    so.remove('')
    
print(so[k-1])
N = int(input().split()[0])
D = int(input().split()[1])
count = 0
for i in range(N):
  Xi = int(input().split()[0])
  Yi = int(input().split()[1])
  R = (Xi**2+Yi**2)**(1/2)
  if R<=D:
    count += 1
print(count)

### FIXED CODE ###

ND = input()
N = int(ND.split()[0])
D = int(ND.split()[1])
count = 0
for i in range(N):
  XiYi = input()
  Xi = int(XiYi.split()[0])
  Yi = int(XiYi.split()[1])
  R = (Xi**2+Yi**2)**(1/2)
  if R <= D:
    count += 1
print(count)
# B - 1 21
# https://atcoder.jp/contests/abc086/tasks/abc086_b

a,b = input().split()

c = int(a + b)

i = 0

while i != -1 and c != i:
    if (i * i) == c:
        print("Yes")
        return
    i = i + 1

print("No")


### FIXED CODE ###

# B - 1 21
# https://atcoder.jp/contests/abc086/tasks/abc086_b

import sys

a,b = input().split()

c = int(a + b)

i = 0

while i <= 10000:
    if (i * i) == c:
        print("Yes")
        sys.exit()

    i = i + 1

print("No")
A,B = input().split()
if (len(A)>1 or len(B)>1):
  print(-1) 
else:
  print(A*B)

### FIXED CODE ###

A,B = (int(i) for i in input().split())  
if (A>9) or (B>9):
    print("-1")
else:
    print(A*B)
n, l = map(int, input().split())

s = n*(l-1) + n*(n+1)/2
c = s
j = 1

for i in range(n):
  t = s - ((l-1)-1)
  T = abs(s-t)
  if T < c:
    c = T
    j = i
    
e = l+j
print(int(s-e))
  




### FIXED CODE ###

n = list(input())

if n[0] == n[1]:
  print("Bad")
  exit()
elif n[1] == n[2]:
  print("Bad")
  exit()
elif n[2] == n[3]:
  print("Bad")
  exit()
print('Good')
while True:
    e = int(input())
    if e == 0:
        break
    
    m = e + 1
    y = 0
    while y ** 2 <= e:
        z = 0
        while y ** 2 + z ** 3 <= e:
            x = e - y ** 2 - z ** 3
            m = min(m, x + y + z)
            z += 1
        y += 1
    print(m)


### FIXED CODE ###

import math

while True:
    e = int(input())
    if e == 0:
        break
    
    m = e + 1
    z = 0
    while z <= e:
        z3 = z ** 3
        if z3 > e:
            break
        y = int(math.sqrt(e - z3))
        x = e - y ** 2 - z3
        m = min(m, x + y + z)
        z += 1
    print(m)
# Debug Print
isdbg = False
def dprint(*value,sep=' ',end='\n'):
    if isdbg:
        print(*value,sep=sep,end=end)

# 入力を格納
H,W,N = map(int,input().split())
XY = [[0 for i in range(W)] for i in range(H)]
for i in range(N):
    x1,y1 = map(int,input().split())
    XY[x1-1][y1-1] = 1

# 初期位置
if isdbg:
    for i in range(W):
        for j in range(H):
            dprint(XY[i][j],end='')
        dprint()

x = 0
y = 0
while x < W and XY[x+1][y] != 1:
   #print()

    # 斜め下方向に走査
    mx = x
    my = y
    while mx < W-1 and my < H-1:
        if XY[mx][my] == 0:
            # 高橋君が動けなくなる位置を発見
            if XY[mx+1][my] == 1:
                print(mx+1)
                exit(0)
        else:
            # 途上に1があったらサーチをやめる
            break
        mx +=1
        my +=1

    if isdbg:
        for i in range(W):
            for j in range(H):
                if i == x and j == y:
                    dprint(2,end='')
                else:
                    dprint(XY[i][j],end='')
            dprint()
        dprint("--")

    x = x + 1

### FIXED CODE ###

# Debug Print
isdbg  = False
#isdbg  = True
def dprint(*value,sep=' ',end='\n'):
    if isdbg:
        print(*value,sep=sep,end=end)
    
# 入力を格納
H,W,N = map(int,input().split())

if isdbg:
    XY = [[0 for i in range(W)] for i in range(H)]
BL = {}
for i in range(N):
    x1,y1 = map(int,input().split())
    if isdbg:
        XY[x1-1][y1-1] = 1

    if x1-1 in BL :
        BL[x1-1].append(y1-1)
    else:
        BL[x1-1] = [y1-1]

TL = sorted(BL.items(),key= lambda x: x[0])

# 初期位置
if isdbg:
    for i in range(W):
        for j in range(H):
            dprint(XY[i][j],end='')
        dprint()
#print(TL)

maxr = 1
for i in range(H-1):

    if i+1 in BL:
        l = BL[i+1]
        l.sort()
        #print(l,maxr)
        for ll in l :
            if maxr > ll:
                print(i+1)
                exit(0)
            elif maxr == ll:
                maxr -= 1
                break
            else:
                break
        
    maxr += 1

print(H)
# -*- coding: utf-8 -*-

"""
計算式は以下のように示される
C_n = (1/n)*(1+C_(n-1)) + ((n-1)/n)*C_(n-1)  =  C_(n-1)+(1/n)
"""
import math
N = int(input())
X = list(map(int, input().split()))

def calc(j):
    l = [1.0/i for i in range(1,j+1)]
    return sum(l)

result = []
for i in range(1, N):
    temp = (X[i]-X[i-1])*calc(i)
    result.append(temp)

print(round(sum(result)*math.factorial(N-1))%(10**9+7))

### FIXED CODE ###

# -*- coding: utf-8 -*-

mod = 10**9 +7
N = int(input())
X = list(map(int, input().split()))

factorial=[1]
for i in range(1,N):
    factorial.append(factorial[-1] *i %mod)

ans=0
for i in range(1,N):
    ans = (ans*i + (X[-1]-X[i-1])*factorial[i-1]) %mod

print(ans)
N, R = map(int, input())
if N >= 10:
  print(R)
else:
  print(R + 100 * (10 - N))

### FIXED CODE ###

N, R = map(int, input().split())
if N >= 10:
  print(R)
else:
  print(R + 100 * (10 - N))
A,B= map(int,input().split())
Ans=A*B//1
print(Ans)

### FIXED CODE ###

inputs= list(input().split())
A=int(inputs[0])
B=float(inputs[1])
B=int(B*100+0.5)
Ans=A*B//100
print(Ans)
#Uses python3

import sys

visited = set()

def explore(adj, x, comp, cc):
    visited.add(x)
    if not(cc in comp):
        comp[cc] = []
    comp[cc].append(x)
    for w in adj[x]:
        if not (w in visited):
            explore(adj, w, comp, cc)

def number_of_components(adj, n):
    #visited = [False for _ in range(n)]
    cc = 0
    comp = dict()
    for v in range(n):
        if not(v in visited):
            explore(adj, v, comp, cc)
            cc += 1
    return comp

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
    adj = [[] for _ in range(n)]
    for (a, b) in edges:
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    res = number_of_components(adj, n)
    max_ = 0
    for value in res.values():
        max_ = max(max_, len(value))
    print(max_)
    #print(n - number_of_components(adj, n) - 1)


### FIXED CODE ###

#Uses python3
import sys
import threading

# This code is used to avoid stack overflow issues
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**29)  # new thread will get stack of such size

visited = set()

def explore(adj, x, comp, cc):
    visited.add(x)
    if not(cc in comp):
        comp[cc] = []
    comp[cc].append(x)
    for w in adj[x]:
        if not (w in visited):
            explore(adj, w, comp, cc)

def number_of_components(adj, n):
    #visited = [False for _ in range(n)]
    cc = 0
    comp = dict()
    for v in range(n):
        if not(v in visited):
            explore(adj, v, comp, cc)
            cc += 1
    return comp


def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    res = number_of_components(adj, n)
    max_ = 0
    for value in res.values():
        max_ = max(max_, len(value))
    print(max_)
    #print(n - number_of_components(adj, n) - 1)


threading.Thread(target=main).start()
def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b


def main():
    n = int(input())
    s = int(input())
    if s == 1:
        print(n)
        return
    elif s > n:
        print(-1)
        return
    b = 2
    while b * b <= n:
        if f(b, n) == s:
            print(b)
            return
        b += 1
    p = 1
    while p * p <= n:
        q = s - p
        b = (n - q) // p
        if f(b, n) == s:
            print(b)
            return
        p += 1
    print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b) + n % b


def main():
    n = int(input())
    s = int(input())
    if s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    sqrt = int(math.sqrt(n))
    for b in range(2, sqrt+2):
        if f(b, n) == s:
            print(b)
            return
    for x in range(sqrt, 0, -1):
        if x > s:
            continue
        y = s - x
        b = (n - y) // x
        if b >= 2 and (n - y) % x == 0 and f(b, n) == s:
            print(b)
            return
    print(-1)


if __name__ == "__main__":
    main()
A, B = list(map(int, input()))

x = -1
for i in range(10100)
  if (int(i*0.08) == A) and (int(i*0.1) == B):
    x = i
    break
  
print(x)

### FIXED CODE ###

A, B = list(map(int, input().split()))

x = -1
for i in range(10100):
  if (int(i*0.08) == A) and (int(i*0.1) == B):
    x = i
    break
  
print(x)
N = int(input())
A = list(map(int, input().split()))
B = []

for i in range(N):
    B.append(A[i] - i)

B = sorted(B)
M = B[int((N + 1)/2)]
ans = 0

for i in range(N):
    t = B[i] - M
    if t < 0:
        t = (-1) * t
    ans += t

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = []

for i in range(N):
    B.append(A[i] - i - 1)

B = sorted(B)
M = B[int((N - 1)/2)]
ans = 0

for i in range(N):
    t = B[i] - M
    if t < 0:
        t = (-1) * t
    ans += t

print(ans)
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



def solve(n, k):
    if n % k == 0:
        return n // k
    diff = (n // k) + 1
    target = n - n % k
    r = n % k
    if r % diff == 0:
        return solve(n - r, k)
    n -= r // diff * diff
    return solve(n, k)


n = I()
ret = 0
for i in range(n):
    a, k = LI()
    ret ^= solve(a, k)

print("Takahashi" if ret else "Aoki")


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



def solve(n, k):
    if n % k == 0:
        return n // k
    diff = (n // k) + 1
    target = n - n % k
    if (n - target) % diff == 0:
        return solve(target, k)
    n -= -((-(n - target)) // diff) * diff
    return solve(n, k)


n = I()
ret = 0
for i in range(n):
    a, k = LI()
    ret ^= solve(a, k)

print("Takahashi" if ret else "Aoki")