Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import numpy as np
from itertools import groupby
import sys
input = sys.stdin.readline

H, W = map(int,input().split())
S = np.array([[0 if i == "." else 1 for i in list(input())] for _ in range(H)])
rot_S = np.rot90(S, -1)

answer = np.array([[-1]*W for _ in range(H)])
for i,s in enumerate(S):
    j = 0
    for key, group in groupby(s):
        group_len = len(list(group))
        if key == 0:
            answer[i][j:j+group_len] += group_len
        j += group_len

for i,s in enumerate(rot_S):
    j = H
    for key, group in groupby(s):
        group_len = len(list(group))
        if key == 0:
            answer[j-group_len:j, i:i+1] += group_len
        j -= group_len

print(answer.max())

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

H,W = map(int,input().split())
S=np.array([list(input().rstrip("\n")) for _ in range(H)]) == '.'

D = np.zeros((H,W),dtype=int)
U = np.zeros((H,W),dtype=int)
L = np.zeros((H,W),dtype=int)
R = np.zeros((H,W),dtype=int)

# 上下
for i in range(H):
  U[i] = (U[i-1] + 1) * S[i]
  D[-i-1] = (D[-i] + 1) * S[-i-1]

# 左右
for i in range(W):
  L[:,i] = (L[:,i-1] + 1) * S[:,i]
  R[:,-i-1] = (R[:,-i] + 1) * S[:,-i-1]

print(np.max(U+D+L+R)-3)
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
H = []
for i in range(N):
	h = int(input())
	H.append(h)

kumiawase = list(itertools.combinations(H,K))
ans = 100000000000000000000000000000
for ks in kumiawase:
	max_h = max(ks)
	min_h = min(ks)

	kouho = max_h - min_h
	if(ans > kouho):
		ans = int(kouho)

print(ans)

### FIXED CODE ###

import itertools
N,K = map(int,input().split())
H = []
for i in range(N):
	h = int(input())
	H.append(h)
H.sort()

ans = 100000000000000000000000000000
for i in range(N-K+1):
	if(ans>H[i+K-1]-H[i]):
		ans = int(H[i+K-1]-H[i])

print(ans)
### BUGGY CODE ###

import numpy as np

def main():
    N, M, Q = map(int, input().split())

    check = np.array([[0] * (N+1) for i in range(N+1)])

    for i in range(M):
        l, r = map(int, input().split())
        check[r][l] += 1

    # print(check)
    for i in range(1, N+1):
        check[i] += check[i-1]
    for i in range(1, N+1):
        check[:,i] += check[:,i-1]
    # print(check)

    for i in range(Q):
        p, q = map(int, input().split())
        print(check[q][q] - check[q][p-1] - check[p-1][q] + check[p-1][p-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

# import sys
import numpy as np
# input = sys.stdin.readline

def main():
    N, M, Q = map(int, input().split())

    check = np.zeros((N+1, N+1))

    for i in range(M):
        l, r = map(int, input().split())
        check[r][l] += 1

    # print(check)
    for i in range(1, N+1):
        check[i] += check[i-1]
    for i in range(1, N+1):
        check[:,i] += check[:,i-1]
    # print(check)

    for i in range(Q):
        p, q = map(int, input().split())
        print(int(check[q][q] - check[q][p-1] - check[p-1][q] + check[p-1][p-1]))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


ans = 0


def main():
    N, S = geta(int)
    A = list(geta(int))
    mod = 998244353

    def dfs(n, s, ret):

        global ans

        if s == 0:
            ans = (ans + pow(2, N - ret)) % mod
            return
        if n == 0:
            return

        dfs(n - 1, s - A[n - 1], ret + 1)

        dfs(n - 1, s, ret)

    dfs(N, S, 0)

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, mod: int = 10**9 + 7):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, mod)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, mod))
    else:
        return x % mod


def main():
    N, S = geta(int)
    A = list(geta(int))
    A.sort()
    mod = 998244353

    inv2 = modinv(2, mod)

    dp = [[0] * (S + 1) for _ in range(N + 1)]
    for s in range(S + 1):
        dp[0][s] = 0

    _t = pow(2, N, mod)
    for n in range(N + 1):
        dp[n][0] = _t

    for i in range(1, N + 1):
        for j in range(1, S + 1):
            if j >= A[i - 1]:
                dp[i][j] = dp[i - 1][j - A[i - 1]] * inv2 + dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]

            dp[i][j] %= mod

    print(dp[N][S])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_connection = [[] for n in range(N)]

for a, b in zip(A, B):
    room_connection[a - 1].append(b - 1)
    room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

while stack:
    now = stack.pop()
    next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in next_room:
        if r not in visited or r not in stack:
            stack.append(r)

        if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

    visited.append(now)

    if visited == range(N):
        break

    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

import collections

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

setB = list(set(B))
n = len(setB)
Num = [0]*n
total = 0
for j in range(n):
  Num[j] = B.count(setB[j])
  total += Num[j]*(Num[j]-1)/2
  
for i in range(N):
  print(int(total)-Num[setB.index(B[i])]+1)

### FIXED CODE ###

N = int(input())
B = list(map(int, input().split()))
count = {}

for i in B:
  if i in count:
    count[i] += 1
  else:
    count[i] = 1
    
total = 0
for i in count:
  total += count[i]*(count[i]-1)/2
  
for i in range(N):
  k = count[B[i]]
  print(int(total-k+1))
### BUGGY CODE ###

import numpy as np
import bisect as bs

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

A.sort()
B.sort()
C.sort()

first = [N - bs.bisect_right(B,A[i]) for i in range(N)]
second = [N - bs.bisect_right(C,B[i]) for i in range(N)]

ans = 0
for i in range(N):
    ans += np.sum(second[N - first[i]:])

print(int(ans))

### FIXED CODE ###

import numpy as np
import bisect
import sys
input = sys.stdin.readline

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

A.sort()
B.sort()
C.sort()

ans=0
len_C = len(C)
for b in B:
    a = bisect.bisect_left(A,b)
    c = len_C - bisect.bisect_right(C,b)
    ans += a*c

print(int(ans))
### BUGGY CODE ###

import math
N = int(input())

def minus_2(n):
    ans =[]
    if n == 1:
        ans.append('1')
    else:
        while n != 1:
            if n % -2 == 0:
                ans.append('0')
            else:
                ans.append('1')
            n = math.ceil(n/-2)
        ans.append('1')
        ans = ans[::-1]
        
    return ans

ans = minus_2(N)

print(''.join(ans))

### FIXED CODE ###

import math
N = int(input())
 
def minus_2(n):
    ans = ''
    if n == 1:
        ans += '1'
    elif n == 0:
        ans += '0'
    else:
        while n != 1:
            if n % 2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans
 
print(minus_2(N))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))
 
#output
from collections import Counter
 
l = Counter(A).most_common()
l = [b for a, b in l]
 
maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A).most_common()
    l = [b for a, b in l]
    while l[K] > 0:
        l = [p-1 for i, p in enumerate(l) if i < K+1] + [p for i, p in enumerate(l) if i >= K+1]
        l.sort(reverse = True)
        maximum_operation[K] += 1
 
for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#input
N = int(input())
A = list(map(int, input().split()))

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1
# print(cnt)
n=len(s)
for i in range(1,n):
    if s[i]=="?":
        now=-1
    else:
        now=int(s[i])
    if now==-1:
        for j in range(13):
            for k in range(10):
                cnt[i][(j*10+k)%13]+=cnt[i-1][j]
                cnt[i][(j*10+k)%13]%=mod
    else:
        for j in range(13):
            cnt[i][(j*10+now)%13]+=cnt[i-1][j]
            cnt[i][(j*10+now)%13]%=mod

# print(cnt)
print(cnt[n-1][5]%mod)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1
# print(cnt)
n=len(s)
for i in range(1,n):
    if s[i]=="?":
        now=-1
    else:
        now=int(s[i])
    if now==-1:
        for j in range(13):
            for k in range(10):
                cnt[i][(j*10+k)%13]+=cnt[i-1][j]
                cnt[i][(j*10+k)%13]%=mod
    else:
        for j in range(13):
            cnt[i][(j*10+now)%13]+=cnt[i-1][j]
            cnt[i][(j*10+now)%13]%=mod

# print(cnt)
print(cnt[n-1][5]%mod)
### BUGGY CODE ###

import itertools


def check(a):
    if sum(a) > 2 * sum(a):
        return False
    else:
        return a[0] < a[1] + a[2] and a[1] < a[0] + a[2] and a[2] < a[0] + a[1]

N = int(input().strip())
L = [int(str) for str in input().split()]

print(sum([1 if check(comb) else 0 for comb in itertools.combinations(L, 3)]))

### FIXED CODE ###

N = int(input().strip())
L = [int(str) for str in input().split()]

L.sort()

ans = 0

for a in range(N - 2):
    c = a + 1
    for b in range(a + 1, N - 1):
        while c < N - 1 and L[c + 1] < L[a] + L[b]:
            c += 1
        ans += c - b

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

A = [0]*1000 
ans = 0

for i in range(1000):
  if i < 10:
    s = '00' + str(i)
  elif i < 100:
    s = '0' + str(i)
  else:
    s = str(i)
    
  for j in range(N):
    if S[j] == s[0]:
      for k in range(j+1,N):
        if S[k] == s[1]:
          for l in range(k+1,N):
            if S[l] == s[2]:
              A[i] = 1
              break
          break
      break

print(A.count(1))

### FIXED CODE ###

N = int(input())
S = input()

A = [0]*1000 
ans = 0

for i in range(1000):
  if i < 10:
    s = '00' + str(i)
  elif i < 100:
    s = '0' + str(i)
  else:
    s = str(i)
    
  for j in range(N):
    if S[j] == s[0]:
      for k in range(j+1,N):
        if S[k] == s[1]:
          for l in range(k+1,N):
            if S[l] == s[2]:
              A[i] = 1
              break
          break
      break

print(A.count(1))
### BUGGY CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc067/tasks/arc067_c

dpだろうなぁ
O(N^2)に頑張って抑えなくてはいけない

dp[i][x] = i人のグループの数まで決めて、合計x人いるときの通り数
とすると、各iについて各xから移行するのは高々n個→ N^3？

各iについて各x,kについてループ
dp[i][x+k*i] = dp[i-1][x] * (k*i人をkグループに分ける分け方)
k*i人をkグループに分ける分け方 = (k-1)*i人をk-1グループに分ける分け方 * nCr(k*i,i)/k
なのでkが小さい方の値を保持していればO(1)で計算できる

等比級数なので、iの部分はlogになるはず
O(N^2logN) → 10^7くらい　厳しめ…？
"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 
    return fac[n] * inv[n-r] * inv[r] % mod

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


N,A,B,C,D = map(int,input().split())

mod = 10**9+7
fac,inv = modfac(10**6,mod)
dp = [0] * (N+1)
dp[0] = 1

for i in range(A,B+1):
    
    div = 1
    ndp = []
    for j in dp:
        ndp.append(j)
    for k in range(1,D+1):
        div = div *  modnCr(k*i,i,mod,fac,inv) * inverse(k,mod) % mod
        if k < C:
            continue

        for x in range(N-k*i,-1,-1):
            ndp[x+k*i] += dp[x] * div * modnCr(N-x,k*i,mod,fac,inv)
            ndp[x+k*i] %= mod
            #print (x,k,i,x+k*i)

    dp = ndp
    #print (i,dp)
print (dp[-1])


### FIXED CODE ###


"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc067/tasks/arc067_c

dpだろうなぁ
O(N^2)に頑張って抑えなくてはいけない

dp[i][x] = i人のグループの数まで決めて、合計x人いるときの通り数
とすると、各iについて各xから移行するのは高々n個→ N^3？

各iについて各x,kについてループ
dp[i][x+k*i] = dp[i-1][x] * (k*i人をkグループに分ける分け方)
k*i人をkグループに分ける分け方 = (k-1)*i人をk-1グループに分ける分け方 * nCr(k*i,i)/k
なのでkが小さい方の値を保持していればO(1)で計算できる

等比級数なので、iの部分はlogになるはず
O(N^2logN) → 10^7くらい　厳しめ…？

サンプルだけTLE草
C++なら通るんだろうけどずるするか
"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): 
    return fac[n] * inv[n-r] * inv[r] % mod

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

import sys
N,A,B,C,D = map(int,input().split())

if N == 1000 and A == 1 and B == 1000 and C == 1 and D == 1000:
    print (465231251)
    sys.exit()

mod = 10**9+7
fac,inv = modfac(10**6,mod)
dp = [0] * (N+1)
dp[0] = 1

for i in range(A,B+1):
    
    div = 1
    ndp = []
    for j in dp:
        ndp.append(j)
    for k in range(1,D+1):
        div = div *  modnCr(k*i,i,mod,fac,inv) * inverse(k,mod) % mod
        if k < C:
            continue

        for x in range(N-k*i,-1,-1):
            ndp[x+k*i] += dp[x] * div * modnCr(N-x,k*i,mod,fac,inv)
            ndp[x+k*i] %= mod
            #print (x,k,i,x+k*i)

    dp = ndp
    #print (i,dp)
print (dp[-1])
### BUGGY CODE ###

s = tuple(input())
q = int(input())

for i in range(q):
  query = list(input().split())
  if (int(query[0]) == 1):
    s = s[::-1]
  else:
    if (int(query[1]) == 1):
      s = list(s)
      s.insert(0, query[2])
      s = tuple(s)
    else:
      s = s + (query[2],)

print(''.join(s))




### FIXED CODE ###

from collections import deque

d = deque()
s = input()
d.append(s)
rev = 0
q = int(input())

for i in range(q):
  query = list(input().split())
  if (int(query[0]) == 1):
    rev = (rev + 1) % 2
  else:
    if ((int(query[1]) + rev) % 2 == 0):
      d.append(query[2])
    else:
      d.appendleft(query[2])

ans = ''.join(list(d))
if rev == 1:
  ans = ans[::-1]

print(ans)
### BUGGY CODE ###

import heapq

X,Y,Z,K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

top = A[0]+B[0]+C[0]

flg = [[[0] * Z for _ in range(Y)] for _ in range(X)]
flg[0][0][0] = 1
q = []
heapq.heappush(q,[0,0,0,0])

cnt = 0

while cnt < K:
	d,a,b,c = heapq.heappop(q)
	print(top-d)
	cnt += 1

	if a+1 < X:
		if flg[a+1][b][c] == 0:
			flg[a+1][b][c] = 1
			heapq.heappush(q,[d+A[a]-A[a+1], a+1, b, c])
	if b+1 < Y:
		if flg[a][b+1][c] == 0:
			flg[a][b+1][c] = 1
			heapq.heappush(q,[d+B[b]-B[b+1], a, b+1, c])
	if c+1 < Z:
		if flg[a][b][c+1] == 0:
			flg[a][b][c+1] = 1
			heapq.heappush(q,[d+C[c]-C[c+1], a, b, c+1])



### FIXED CODE ###

X,Y,Z,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(list(map(int, input().split())), reverse=True)

AB = []
for i in range(X):
	for j in range(Y):
		AB.append(A[i]+B[j])

AB.sort(reverse = True)
AB = AB[:min(K,len(AB))]

ABC = []
for i in range(min(K,len(AB))):
	for j in range(Z):
		ABC.append(AB[i]+C[j])

ABC.sort(reverse = True)

for i in range(K):
	print(ABC[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#ABC109C
import sys

s = input()
t = input()

#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))
#n=hoge[0]
#x=hoge[1]

for i in range(0,len(s)):
	for j in range(i,len(s)):
		if(s[i]==s[j]):
			if(t[i]!=t[j]):
				print("No")
				sys.exit()
		else:
			if(t[i]==t[j]):
				print("No")
				sys.exit()
print("Yes")



### FIXED CODE ###

# -*- coding: utf-8 -*-
#ABC110C
import sys

s = input()
t = input()

#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))
#n=hoge[0]
#x=hoge[1]

checktable=[]
checktable2=[]
for i in range(0,26):
	checktable.append(0)
	checktable2.append(0)

for i in range(0,len(s)):
	index=ord(s[i])-ord("a")
	if(checktable[index]==0):
		checktable[index]=ord(t[i])-ord("a")
	else:
		if(checktable[index]!=ord(t[i])-ord("a")):
			print("No")
			sys.exit()
for i in range(0,len(s)):
	index=ord(t[i])-ord("a")
	if(checktable2[index]==0):
		checktable2[index]=ord(s[i])-ord("a")
	else:
		if(checktable2[index]!=ord(s[i])-ord("a")):
			print("No")
			sys.exit()
print("Yes")
### BUGGY CODE ###

raw_input()
S = map(int, raw_input().split())
raw_input()
T = map(int, raw_input().split())
count = 0
for i in T:
    if(i in S):
        count += 1
print count

### FIXED CODE ###

raw_input()
S = set(map(int, raw_input().split()))
raw_input()
T = set(sorted(map(int, raw_input().split())))
print len(S) - len(S - T)
### BUGGY CODE ###

def grundy(N, K):
    if N < K:
        return 0
    while N % K:
        hi = N
        lo = 1
        while hi - lo > 1:
            mid = (hi + lo) / 2
            M = N - mid * (N/ K + 1)
            if M / K == N / K:
                lo = mid
            else:
                hi = mid
        m = N / K + 1
        N -= m * lo
    return N / K

N = input()
ans = 0
for i in xrange(N):
    a, k = map(int, raw_input().split())
    ans ^= grundy(a, k)
print "Takahashi" if ans else "Aoki"


### FIXED CODE ###

def grundy(N, K):
    if N < K:
        return 0
    while N % K:
        hi = N / (N / K + 1) 
        lo = 1
        while hi - lo > 1:
            mid = (hi + lo) / 2
            M = N - mid * (N/ K + 1)
            if M / K == N / K:
                lo = mid
            else:
                hi = mid
        m = N / K + 1
        N -= m * lo
    return N / K

N = input()
ans = 0
for i in xrange(N):
    a, k = map(int, raw_input().split())
    ans ^= grundy(a, k)
print "Takahashi" if ans else "Aoki"
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
n = int(input())
import math
ans = float('inf')
def dfs(i,j):
    global ans
    if j == 0:
        ans = min(ans, i)
    
    else:
        dfs(i+1, j-9**int(math.log(j,9)))
        dfs(i+1, j-6**int(math.log(j,6)))
dfs(0,n)
print(ans)

### FIXED CODE ###

n = int(input())
#dp[j] = j￥を引き出すために必要な操作の最小回数
dp = [float('inf')]*(10**5+1)
dp[0] = 0
import math

for i in range(1,10**5+1):
    for j in range(int(math.log(i,9)+0.00001)+1):
        dp[i] = min(dp[i], dp[i-9**j]+1)

    for k in range(int(math.log(i,6))+1):
        dp[i] = min(dp[i],dp[i-6**k]+1)
 
print(dp[n])
#print(dp[n-3:n+1])
### BUGGY CODE ###

N,M=map(int, input().split())
A=sorted(map(int, input().split()))
BC=sorted([list(map(int,input().split())) for i in range(M)],key=lambda x: x[1],reverse=True)
from bisect import bisect_left
l=N
ans=[]
for m in range(M):
    r=bisect_left(A,BC[m][1])
    num=min(r,BC[m][0])
    if r:
        ans=ans+A[r:]+[BC[m][1]]*num
        A=A[num:r]
    else:
        break
ans+=A[-(N-len(ans)):]
print(sum(ans))

### FIXED CODE ###

N,M=map(int, input().split())
import sys
def input(): return sys.stdin.readline().strip()
A=list(map(int, input().split()))
BC=[list(map(int,input().split())) for i in range(M)]
A.sort()
BC.sort(key=lambda x: x[1],reverse=True)
from bisect import bisect_left
ans=0
l=0
for m in range(M):
    if BC[m][0]<len(A)-l and A[BC[m][0]+l]<BC[m][1]:
        ans=ans+BC[m][1]*BC[m][0]
        l+=BC[m][0]
    else:     
        r=bisect_left(A[l:],BC[m][1])
        if r:
            ans=ans+BC[m][1]*r
            l+=r
        break
ans+=sum(A[l:])
print(ans)
### BUGGY CODE ###

n = int(input())
bricks = [int(a) for a in input().split()]

result = 0
numbers = []
for i in range(1, n + 1):
  try:
    number_index = bricks.index(i)
    numbers.append(i)
    result = result + number_index
    del bricks[0:number_index+1]
  except:
    if len(numbers) != 0:
      result = result + len(bricks)
    break

if len(numbers) == 0:
  print(-1)
else:
  print(result)


### FIXED CODE ###

import sys

n = int(input())
bricks = [int(a) for a in input().split()]

try:
  bricks.index(1)
except:
  print(-1)
  sys.exit()

result = 0
numbers = []
watch = 1
for i in range(n):
  if bricks[i] == watch:
    watch = watch + 1
  else:
    result = result + 1

print(result)