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

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    mod = 10**9+7
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    nCk = 1
    pw25 = 1
    pw26 = pow(26,K,mod)
    inv26 = pow(26,mod-2,mod)
    for i in range(K+1):
        ret += nCk * pw25 * pw26
        ret %= mod
        nCk *= (i+Nk) * pow(i+1,mod-2,mod)
        nCk %= mod
        pw25 = (pw25*25)%mod
        pw26 = (pw26*inv26)%mod

    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    mod = 10**9+7
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    nCk = 1
    pw25 = 1
    pw26 = pow(26,K,mod)
    inv26 = pow(26,mod-2,mod)
    for i in range(K+1):
        ret += nCk * pw25 * pw26
        ret %= mod
        nCk *= (i+Nk) * pow(i+1,mod-2,mod)
        nCk %= mod
        pw25 = (pw25*25)%mod
        pw26 = (pw26*inv26)%mod

    print(ret)

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

n,q=map(int,input().split())
s=list(input())
ans_list=[]
length=[]

for i in range(q):
  ans=0
  l,r=map(int,input().split())
  sublist=s[l-1:r]
  for j in range(len(sublist)-1):
    if sublist[j]=='A' and sublist[j+1]=='C':
      ans=ans+1
  ans_list.append(ans)
  
for i in range(q):
  print(ans_list[i])

### FIXED CODE ###

N, Q=map(int,input().split())
S=input()
t=[0]*(N+1)
for i in range(N):
  t[i+1]=t[i]+(1 if S[i : i+2]== 'AC' else 0)
for i in range(Q):
  l, r=map(int,input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def pattcount(num):
    if(num == 0): return 1
    if(num < 0): return 0
    result = 1
    ranmax = num // 2 + 1
    for i in range(1, ranmax):
        result += cmb(num-i, i)
    
    return result
    

if __name__ == '__main__':
    n,m = list(map(int, input().split()))

    pattern = 1
    step = 0
    for i in range(m):
        a = int(input())
        pattern *= pattcount(a - 1 - step)
        step = a + 1

    pattern *= pattcount(n - step)

    print(pattern % 1000000007)


### FIXED CODE ###

if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    a = []
    for i in range(m):
        a.append(int(input()))
    a.append(0)
    ac = 0

    step0 = 0
    step1 = 1
    for i in range(1, n+1):
        temp = step0 + step1
        step0 = step1
        step1 = temp
        if(i == a[ac]):
            step1 = 0
            ac += 1

    print(step1 % 1000000007)
### BUGGY CODE ###

A, B, N = map(int, input().split())
max = 0
for x in range(N+1):
  if int(A*x/B) - (A * int(x/B)) > max:
    max = int(A*x/B) - (A * int(x/B))
print(max)

### FIXED CODE ###

def f(a, b, x):
  return int(a*x/b) - (a*int(x/b))
A, B, N = map(int, input().split())
print(f(A, B, min(B-1, N)))
### BUGGY CODE ###

from collections import *
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
S = 2*[(W+4)*"#"]+["##"+input()+"##" for h in range(H)]+2*[(W+4)*"#"]
ans = [(W+4)*[-1] for h in range(H+4)]
ans[ch+1][cw+1] = 0
move = [[-1,0],[1,0],[0,-1],[0,1]]
magic = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,1],[-1,2],[0,-2],[0,2],[1,-2],[1,-1],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]

for h in range(H+4):
  for w in range(W+4):
    if S[h][w]=="#":
      ans[h][w]=-2

P = deque([[ch+1,cw+1]])
Q = deque([])

while 0<len(P):
  x,y = P.popleft()
  Q.append([x,y])
  for dx,dy in move:
    if ans[x+dx][y+dy]==-1:
      ans[x+dx][y+dy] = ans[x][y]
      P.append([x+dx,y+dy])
  
  if len(P)==0:
    while Q:
      x,y = Q.popleft()
      for dx,dy in magic:
        if ans[x+dx][y+dy]==-1:
          ans[x+dx][y+dy] = ans[x][y]+1
          P.append([x+dx,y+dy])

print(ans[dh+1][dw+1])

### FIXED CODE ###

from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math
a,b = map(int,input().split())
ans = 1
nowa = a
nowb = b
for num in range(2,min(a,b)):
  if num > nowa and num > nowb:
    print(ans)
    exit()
  if nowa % num == 0 and nowb % num == 0:
    ans += 1
    while nowa % num == 0 and nowb % num == 0:
      nowa = nowa//num
      nowb = nowb//num
print(ans)

### FIXED CODE ###

import fractions
a,b = map(int,input().split())
c = fractions.gcd(a,b)

ans = [1]
while c % 2 == 0:
  ans.append(2)
  c //= 2
i = 3
while c >= i ** 2:
  if c % i == 0:
    ans.append(i)
    c //= i
  else:
    i += 2
if c != 1:
  ans.append(c)
print(len(set(ans)))
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

N,K = list(map(int,input().split()))
h = list(map(int,input().split()))

dq = collections.deque([0])

for i in range(1,N):
    l = []
    if i<K+1:
        for k in range(1,i+1):
            l.append(dq[i-k]+abs(h[i]-h[i-k]))

        dq.append(min(l))
    else:
        for k in range(1,K+1):
            l.append(dq[k]+abs(h[i]-h[i-K+k-1]))
        dq.append(min(l))
        dq.popleft()
print(dq.pop())

### FIXED CODE ###

import collections
import sys
sys.setrecursionlimit(10**7)

N,K = list(map(int,input().split()))
h = list(map(int,input().split()))

dq = collections.deque([0])

for i in range(1,N):
    l = []
    if i<K+1:
        for k in range(1,i+1):
            l.append(dq[i-k]+abs(h[i]-h[i-k]))

        dq.append(min(l))
    else:
        for k in range(1,K+1):
            l.append(dq[k]+abs(h[i]-h[i-K+k-1]))
        dq.append(min(l))
        dq.popleft()
print(dq.pop())
### BUGGY CODE ###

def main() :
    N, M  = list(map(int, input().split()))
    H     = list(map(int, input().split()))
    LEFT  = 0
    RIGHT = 1
    pairs = []

    for itr in range(M) :
        pairs.append(list(map(int, input().split())))

    
    resurt = 0
    for itr in range(N) :
        checkl = []
        for inner_itr in range(N) :
            checkl.append(False)
        
        count = 1
        for inner_itr in range(M) :
            if pairs[inner_itr][LEFT] == (itr + 1) :
                if H[itr] <= H[pairs[inner_itr][RIGHT] - 1] :
                    count = 0
                    break
                elif H[itr] == H[pairs[inner_itr][RIGHT] - 1] :
                    if checkl[RIGHT - 1] == False :
                        count += 1
                        checkl[RIGHT - 1] = True                    

            if pairs[inner_itr][RIGHT] == (itr + 1) :
                if H[itr] <= H[pairs[inner_itr][LEFT] - 1] :
                    count = 0
                    break
                elif H[itr] == H[pairs[inner_itr][LEFT] - 1] :
                    if checkl[LEFT - 1] == False :
                        count += 1
                        checkl[LEFT - 1] = True
        resurt += count
        checkl = None
    
    print(resurt)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import copy

def main():
    N, M  = list(map(int, input().split()))
    H     = list(map(int, input().split()))
    maxH  = np.zeros(N)

    for itr in range(M):
        A, B = list(map(int, input().split()))
        if H[A- 1] == H[B- 1] :
            maxH[A- 1] = copy.copy(H[A- 1]) + 1
            maxH[B- 1] = copy.copy(H[A- 1]) + 1
        elif H[A- 1] > H[B- 1] :
            if maxH[A- 1] < H[A- 1] :
                maxH[A- 1] = copy.copy(H[A- 1])
            if maxH[B- 1] < H[A- 1] :
                maxH[B- 1] = copy.copy(H[A- 1])
        elif H[A- 1] < H[B- 1] :
            if maxH[A- 1] < H[B- 1] :
                maxH[A- 1] = copy.copy(H[B- 1])
            if maxH[B- 1] < H[B- 1] :
                maxH[B- 1] = copy.copy(H[B- 1])
    
    result = 0
    for itr in range(N):
        if H[itr] == maxH[itr] or maxH[itr] == 0:
            result += 1
    #print(maxH)
    print(result)

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

from collections import Counter
import copy

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

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

cnum = []
ans = 0

for k in range(1,n+1):
    cans = []
    dammy = copy.copy(a)
    del dammy[k-1]
    c = Counter(dammy)
    cnum = [c[i] for i in c if c[i] >=2]
    for j in cnum:
        cans.append(combinations_count(j, 2))
    print(sum(cans))


### FIXED CODE ###

from collections import Counter

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

c = Counter(a)
total = sum([v*(v-1)//2 for v in c.values()])
for i in a:
    print(total-(c[i]-1))
### BUGGY CODE ###

N, K = map(int, input().split())
A = [1] + list(map(int, input().split()))

base = 1

for ai in A[:K+1]:
  base *= ai

score = [base]

for i in range(K+1, N+1):
  s = score[-1] // A[i-K] * A[i]
  score.append(s)

for i in range(1, len(score)):
  print('Yes' if score[i] > score[i-1] else 'No')


### FIXED CODE ###

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

for i in range(N - K):
  score_2 = A[i+K]
  score_1 = A[i]
  print('Yes' if score_1 < score_2 else 'No')
### BUGGY CODE ###

n = int(input())
list_ = [int(input()) for _ in range(n)]

print(sum(list_.count(key) % 2 for key in set(list_)))


### FIXED CODE ###

n = int(input())
list_ = [int(input()) for _ in range(n)]

dict_ = dict()
for key in list_:
    dict_[key] = dict_.get(key, 0) + 1
print(sum(num % 2 for num in dict_.values()))
### BUGGY CODE ###

H,W=list(map(int,input().strip().split(' ')))
grid=[]
for _ in range(H):
    grid+=[input()]

block_h=[]
for i in range(H):
    temp=[-1]
    for j in range(W):
        if grid[i][j]=="#":
            temp+=[j]
    temp+=[W]
    block_h+=[temp]

block_c=[]
for j in range(W):
    temp=[-1]
    for i in range(H):
        if grid[i][j]=="#":
            temp+=[i]
    temp+=[H]
    block_c+=[temp]

#print(block_h)
#print(block_c)
import bisect
MAX=0
for i in range(H):
    for j in range(W):
        #print(i,j)
        ans=0
        if grid[i][j]==".":
            post=bisect.bisect_right(block_c[j],i)
            #print(post)
            a1=block_c[j][post-1]
            a2=block_c[j][post]
            ans+=a2-a1-1

            post=bisect.bisect_right(block_h[i],j)
            #print(post)
            a1=block_h[i][post-1]
            a2=block_h[i][post]
            ans+=a2-a1-1            
            MAX=max(MAX,ans)
print(MAX-1)




### FIXED CODE ###

H,W=list(map(int,raw_input().strip().split(' ')))
grid=[]
for _ in xrange(H):
    grid+=[raw_input()]

block_h=[]
for i in xrange(H):
    temp=[-1]
    for j in xrange(W):
        if grid[i][j]=="#":
            temp+=[j]
    temp+=[W]
    block_h+=[temp]

block_c=[]
for j in xrange(W):
    temp=[-1]
    for i in xrange(H):
        if grid[i][j]=="#":
            temp+=[i]
    temp+=[H]
    block_c+=[temp]

#print(block_h)
#print(block_c)
import bisect
MAX=0
for i in xrange(H):
    for j in xrange(W):
        #print(i,j)
        ans=0
        if grid[i][j]==".":
            post=bisect.bisect_right(block_c[j],i)
            #print(post)
            a1=block_c[j][post-1]
            a2=block_c[j][post]
            ans+=a2-a1-1

            post=bisect.bisect_right(block_h[i],j)
            #print(post)
            a1=block_h[i][post-1]
            a2=block_h[i][post]
            ans+=a2-a1-1            
            MAX=max(MAX,ans)
print(MAX-1)
### BUGGY CODE ###

import heapq

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

AB=[]
for i in A:
  for j in B:
    heapq.heappush(AB,-i-j)
#print(AB)

ABC=[]
for i in AB:
  for j in C:
    heapq.heappush(ABC,i-j)

for i in range(min(K,X*Y*Z)):
  print(-heapq.heappop(ABC))
    

### FIXED CODE ###

import heapq

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

AB=[]
for i in A:
  for j in B:
    heapq.heappush(AB,-i-j)
#print(AB)

ABC=[]
for i in range(min(K,X*Y)):
  temp=heapq.heappop(AB)
  for j in C:
    heapq.heappush(ABC,temp-j)

for i in range(min(K,X*Y*Z)):
  print(-heapq.heappop(ABC))
### BUGGY CODE ###

import sys
INF=100000000
def frog(i,K,h,dp):
    global INF
    if dp[i]!=INF:
        return dp[i]
    else:
        cost=[]
        for k in range(1,K+1):
            x=i-k-1
            if x>=0:
                cost.append(frog(i-k,K,h,dp)+abs(h[i-1]-h[x]))
                continue
            break
        dp[i]=min(cost)
        return dp[i]
sys.setrecursionlimit(INF)
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[INF for i in range(N+1)]
dp[1]=0
dp[2]=abs(h[1]-h[0])
print(frog(N,K,h,dp))


### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
h=list(map(int,input().split()))
h=np.array(h)
cost=np.zeros(N+1)
cost[1]=0
cost[2]=abs(h[1]-h[0])
for i in range(3,N+1):
    x=1 if i-K<=1 else i-K
    cost[i]=(cost[x:i]+abs(h[i-1]-h[x-1:i-1])).min()
print(int(cost[N]))
### BUGGY CODE ###

Slist = list(input())
keta = len(Slist)
count = 0
for i in range(keta):
    for j in range(i+3,keta):
        a = Slist[i:j+1]
        if int("".join(a))%2019==0:
            count += 1

print(count)
        
    

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


while ng - ok > 1:
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))


### FIXED CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))
### BUGGY CODE ###

N , K = map(int, input().split())
h = list(map(int, input().split()))

Dp = [None]*N
Dp[0] = 0
Dp[1] = abs(h[1]-h[0])

for i in range(2,N):
  Dp[i] =min([Dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(K,i)+1)])

print(Dp[N-1])





### FIXED CODE ###

N , K = map(int, input().split())
h = list(map(int, input().split()))

Dp = [None]*N
Dp[0] = 0

for i in range(1,N):
  Dp[i] =min([Dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-K),i)])

print(Dp[-1])
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0

x=0
while x*r<=n:
    y=0
    while y*g<=n-x*r:
        n0=n-x*r-y*g
        if n0 % b == 0:
            ans+=1
        y+=1
    x+=1
print(ans)

### FIXED CODE ###

r0,g0,b0,n=map(int,input().split())
ans=0
l=[r0,g0,b0]
l.sort(reverse=True)
r=l[0]
g=l[1]
b=l[2]
x=0
while x*r<=n:
    y=0
    if g==1:
        ans+=1+n-x*r
        x+=1
        continue
    if b==1:
        ans+=1+(n-x*r)//g
        x+=1
        continue
    while y*g<=n-x*r:
        if (n-x*r-y*g) % b == 0:
            ans+=1
        y+=1
    x+=1
print(ans)
### BUGGY CODE ###

from collections import deque
N= input()
a = raw_input().split()
#print a

d=deque()
for i,val in enumerate(a):
	if i%2==1:
		d.append(val)
	else:
		d.appendleft(val)
else:
	#print d
	d_str=""
	if N%2==0:
		for j in range(N):
			d_str=d_str+d.pop()+" "
	else:
		for j in range(N):
			d_str=d_str+d.popleft()+" "		
	print d_str[0:-1]

### FIXED CODE ###

n= input()
a = map(int,raw_input().split())
#print a

l=[ i for i in range(n)]
l_gusu=l[0::2]
l_kisu=l[1::2]

ans=[]
for i in reversed(list(l_gusu)):
	#print i,a[i]
	ans.append(a[i])

for i in l_kisu:
	ans.append(a[i])


ans_str=""
if n%2==0:
	for i in reversed(list(ans)):
		ans_str+=(str(i)+" ")
	print ans_str.strip()
else:
	for i in ans:
		ans_str+=(str(i)+" ")
	print ans_str.strip()
### BUGGY CODE ###

a = list(map(int, input().split()))
a.sort()

cd = a[0]
b = a[1]%a[0]

while a[0]%cd != 0 or b%cd != 0:
    cd -= 1

print(cd)

### FIXED CODE ###

a = list(map(int, input().split()))
a.sort()

while a[0] > 0:
    b = a[1]%a[0]
    a[1] = a[0]
    a[0] = b
    
print(a[1])
### BUGGY CODE ###

import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)

def main():
    def judge(u=0,b=False):
        bt[u]=b
        res=False
        for ku in range(n):
            if not to[u][ku]:continue
            if bt[ku]==b:
                return True
            if bt[ku]==None:
                res|=judge(ku,not b)
        return res

    def bfs(u):
        hp=[]
        heappush(hp,(0,u))
        while hp:
            d,u=heappop(hp)
            if dis[u]!=-1:continue
            dis[u]=d
            for v in range(n):
                if not to[u][v]:continue
                if dis[v]!=-1:continue
                heappush(hp,(d+1,v))

    n = int(input())
    to = [[c == "1" for c in input()] for _ in range(n)]
    bt=[None]*n
    if judge():
        print(-1)
        exit()
    ans=0
    for u in range(n):
        dis=[-1]*n
        bfs(u)
        ans=max(ans,max(dis)+1)
    print(ans)
main()


### FIXED CODE ###

import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)

def main():
    def judge(u=0,b=False):
        bt[u]=b
        res=False
        for ku in range(n):
            if not to[u][ku]:continue
            if bt[ku]==b:
                return True
            if bt[ku]==None:
                res|=judge(ku,not b)
        return res

    def bfs(u):
        hp=[]
        heappush(hp,(0,u))
        while hp:
            d,u=heappop(hp)
            for v in range(n):
                if not to[u][v]:continue
                if dis[v]!=-1:continue
                dis[v]=d+1
                heappush(hp,(d+1,v))

    n = int(input())
    to = [[c == "1" for c in input()] for _ in range(n)]
    bt=[None]*n
    if judge():
        print(-1)
        exit()
    ans=0
    for u in range(n):
        dis=[-1]*n
        dis[u]=0
        bfs(u)
        ans=max(ans,max(dis)+1)
    print(ans)
main()
### BUGGY CODE ###

import re
N,A,B = map(int,input().split())
S = input()
motoplayers = []
cnt = 0
for i in S:
    motoplayers.append(i + str(cnt))
    cnt+=1
players = [i for i in motoplayers if not "c" in i]

kaigai = [i for i in players if "b" in i]
del kaigai[B:]
tuukaninzuu = 0
for i in range(N):
    if motoplayers[i] in players:
        if tuukaninzuu < A+B:
            if "b" in motoplayers[i]:
                if motoplayers[i] in kaigai:
                    print("Yes")
                    tuukaninzuu+=1
                    continue
                else:
                    print("No")
                    continue
            else:
                print("Yes")
                tuukaninzuu+=1
                continue
        else:
            print("No")
            continue
    else:
        print("No")
        continue



### FIXED CODE ###

N,A,B = map(int,input().split())
players = list(input())
tuuka = 0
kaigai = 0
for i in players:
    if i == "c":
        print("No")
        continue
    if i == "b" or i == "a":
        if tuuka < A + B:
            if i == "a":
                print("Yes")
                tuuka += 1
                continue
            if i == "b" and kaigai < B:
                print("Yes")
                tuuka += 1
                kaigai += 1
            else:
                print("No")
        else:
            print("No")
### BUGGY CODE ###

H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]

h_value = [0]*(H+1)
w_value = [0]*(W+1)
exist = [ [0 for _ in range(W+1)] for _ in range(H+1)]
for coordinate in hw:
    h_value[coordinate[0]] += 1
    w_value[coordinate[1]] += 1
    exist[coordinate[0]][coordinate[1]] = 1

h_max = max(h_value)
w_max = max(w_value)

h_max_ind = list()
w_max_ind = list()
h_max_ind_exist = [0]*(H+1)
w_max_ind_exist = [0]*(W+1)

for i in range(H+1):
    if h_value[i] == h_max:
        h_max_ind.append(i)
        h_max_ind_exist[i] = 1


for i in range(W+1):
    if w_value[i] == w_max:
        w_max_ind.append(i)
        w_max_ind_exist[i] = 1

# print("put", h_max_ind, w_max_ind)
flag = False
if len(h_max_ind)*len(w_max_ind) > M:
    flag = True
else:
    for h in h_max_ind:
        for w in w_max_ind:
            if exist[h][w] == 0:
                flag = True

if flag:
    print(h_max + w_max)
else:
    print(h_max + w_max - 1)



### FIXED CODE ###

H, W, M = map(int, input().split())
hw = [list(map(int, input().split())) for _ in range(M)]
hw_set = set()
for bomb in hw:
    hw_set.add((bomb[0], bomb[1]))
h_value = [0]*(H+1)
w_value = [0]*(W+1)
# exist = [ [0 for _ in range(W+1)] for _ in range(H+1)]

for coordinate in hw:
    h_value[coordinate[0]] += 1
    w_value[coordinate[1]] += 1
    

h_max = max(h_value)
w_max = max(w_value)

h_max_ind = list()
w_max_ind = list()
h_max_ind_num = 0
w_max_ind_num = 0

for i in range(H+1):
    if h_value[i] == h_max:
        h_max_ind.append(i)
        h_max_ind_num += 1


for i in range(W+1):
    if w_value[i] == w_max:
        w_max_ind.append(i)
        w_max_ind_num += 1

# print("put", h_max_ind, w_max_ind)
flag = False
if (h_max_ind_num * w_max_ind_num) > M:
    flag = True
else:
    for h in h_max_ind:
        for w in w_max_ind:
            if not (h, w) in hw_set:
                flag = True
                break

if flag:
    print(h_max + w_max)
else:
    print(h_max + w_max - 1)