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

N, Q = map(int, input().split())  # 複数数値入力
S = list(input())  # 一文字ずつ格納
L = []
R = []

for i in range(Q):
    l, r = map(int, input().split())  # 複数数値入力
    L.append(l)
    R.append(r)

for i in range(Q):
    list = S[L[i]-1:]
    list = list[:R[i]-L[i]+1]
    flg = 0
    ans = 0

    for j in list:
        if j == "A":
            flg = 1
        elif j == "C" and flg == 1:
            ans += 1
            flg = 0
        else:
            flg = 0

    print(ans)


### FIXED CODE ###

import numpy as np

N, Q = map(int, input().split())  # 複数数値入力
S = list(input())  # 一文字ずつ格納

dp = [0] * N
i = 0
flg = False
for str in S:
    if str == "C" and flg == True:
        dp[i] = dp[i - 1] + 1
        flg = False
    elif str == "A":
        flg = True
        dp[i] = dp[i-1]
    else:
        flg = False
        dp[i] = dp[i-1]
    i += 1

for i in range(Q):
    l, r = map(int, input().split())  # 複数数値入力
    print(dp[r-1]-dp[l-1])
### BUGGY CODE ###

m,n=map(int,input().split())
mn=m**n
if mn<=1000000007:
    print(mn)
else:
    print(mn%1000000007)


### FIXED CODE ###

m,n=map(int,input().split())
print(pow(m,n,1000000007))
### BUGGY CODE ###

from sys import stdin


def get_result(data):
    N = data[0][0]
    A = data[1]
    dp = [[0]*(N+1) for _ in range(N+1)]
    B = [[A[i], i] for i in range(N)]
    B = sorted(B, reverse=True)
    for i in range(N):
        for j in range(N-i):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + B[i+j][0] * (B[i+j][1] - i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + B[i+j][0] * ((N-1-j) - B[i+j][1]))

    res = 0
    for i in range(N):
        res = max(res, dp[i][N-i])
    return res


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    N = data[0][0]
    A = data[1]
    dp = [[0]*(N+1) for _ in range(N+1)]
    B = [[A[i], i] for i in range(N)]
    B = sorted(B, reverse=True)
    for i in range(N):
        for j in range(N-i):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + B[i+j][0] * (B[i+j][1] - i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + B[i+j][0] * ((N-1-j) - B[i+j][1]))

    res = 0
    for i in range(N):
        res = max(res, dp[i][N-i])
    return res


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)
### BUGGY CODE ###

N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]

T, A = 0, 0
for t, a in TA:
    if T == 0 and A == 0:
        T = t
        A = a
        continue
    if t == a:
        M = max(T, A)
        T = M
        A = M
    elif t < a:
        n = 0
        while n < T or a * (n // t) < A:
            n += t
        T = n
        A = a * (T // t)
    else:
        n = 0
        while n < A or t * (n // a) < T:
            n += a
        A = n
        T = t * (A // a)
print(A + T)

### FIXED CODE ###

N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]

T, A = 0, 0
for t, a in TA:
    if T == 0 and A == 0:
        T = t
        A = a
        continue
    if t == a:
        M = max(T, A)
        T = M
        A = M
    elif t < a:
        n = max((T // t) * t, (A // a) * t)
        while n < T or a * (n // t) < A:
            n += t
        T = n
        A = a * (T // t)
    else:
        n = max((A // a) * a, (T // t) * a)
        while n < A or t * (n // a) < T:
            n += a
        A = n
        T = t * (A // a)
print(A + T)
### BUGGY CODE ###

import itertools

a, b = map(int, input().split())
c = []
for i in range(1, a + 1):
    if i % b == 0 or i % b == b / 2:
        c.append(i)
d = 0
for i in itertools.product(c, repeat=3):
    if (i[0] + i[1]) % b == 0 and (i[0] + i[2]) % b == 0 and (i[1] + i[2]) % b == 0:
        d += 1
print(d)


### FIXED CODE ###

a, b = map(int, input().split())
c = []
d = []
for i in range(1, a + 1):
    if i % b == 0:
        c.append(i)
    elif i % b == b / 2:
        d.append(i)
e = 0
print(len(c) * len(c) * len(c) + len(d) * len(d) * len(d))
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            s[i][j] = min(i,N-1-i,j,N-1-j)

    r = [[1] * N for _ in range(N)]

    ans = 0
    for p in P:
        x = (p-1)//N
        y = (p-1) % N
        ans += s[x][y]
        r[x][y] = 0
        q = collections.deque()
        q.append((x,y))
        while q:
            a,b = q.pop()
            nc = s[a][b] + r[a][b]
            for da,db in ((1,0),(0,1),(-1,0),(0,-1)):
                na = a + da; nb = b + db
                if 0 < na < N-1 and 0 < nb < N-1:
                    if s[na][nb] <= nc: continue
                    s[na][nb] = nc
                    q.append((na,nb))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

from itertools import permutations, product

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

indices_R = [i for i in range(N) if S[i] == "R"]
indices_G = [i for i in range(N) if S[i] == "G"]
indices_B = [i for i in range(N) if S[i] == "B"]

count = 0
for ijk in product(indices_R, indices_G, indices_B):
    i, j, k = sorted(ijk)
    if j - i != k - j:
        count += 1

print(count)

### FIXED CODE ###

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

r_num = S.count("R")
g_num = S.count("G")
b_num = S.count("B")

count = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j * 2 - i
        if k >= N:
            continue
        si, sj, sk = S[i], S[j], S[k]
        if si != sj and sj != sk and sk != si:
            count += 1

print(r_num * g_num * b_num - count)
### BUGGY CODE ###

n,k=map(int,input().split())
hl=list(map(int,input().split()))
dp=[0]
for i in range(1,n):
    t=[]
    for j in range(1,min(i+1,k+1)):
        t.append(dp[i-j]+abs(hl[i-j]-hl[i]))
    dp.append(min(t))
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
hl=list(map(int,input().split()))
dp=[0]
for i in range(1,n):
    t=[]
    for j in range(1,min(i+1,k+1)):
        t.append(dp[i-j]+abs(hl[i-j]-hl[i]))
    dp.append(min(t))
print(dp[-1])
### BUGGY CODE ###

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
step = []
for l,r in LR:
    for i in range(l,r+1):
        step.append(i)
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if ma[i] != 0:
        for j in step:
            if i+j < N:
                ma[i+j] += ma[i]
print(ma[N-1]%mod)

### FIXED CODE ###

N,K = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(K)]
LR.sort()
mod = 998244353
ma = [0] * N
ma[0] = 1
for i in range(N):
    if i >1:
        ma[i] += ma[i-1]
    p = ma[i]%mod
    if p != 0:
        for l,r in LR:
            if i+l <N:
                ma[i+l] += p
            else:
                break
            if i+r+1<N:
                ma[i+r+1] -= p
print(ma[N-1]%mod)
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

for i in range(n):
    temp = 0
    if(max(a) == a[i]):
        temp = a[i]
        a[i] = 0
        print(max(a))
        a[i] = temp
    else: print(max(a))

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

maxR = [0] * n
maxL = [0] * n
maximum = 0
for i in range(n):
    maximum = max(maximum,a[i])
    maxL[i] = maximum
maximum = 0
for i in range(n):
    maximum = max(maximum,a[n-i-1])
    maxR[n-i-1] = maximum



for i in range(n):
    if i == 0:
        print(maxR[1])
    elif i == n-1:
        print(maxL[n-2])
    else:
        print(max(maxL[i-1],maxR[i+1]))
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = [[] for _ in range(N)]
for i in range(N-1):
    a,b = inpl()
    a-=1; b-=1
    lines[a].append((b,i))
    lines[b].append((a,i))


def dfs(s,b,v):
    if s == v:
        return set()
    else:
        for t,i in lines[s]:
            if t == b:
                continue
            ret = dfs(t,s,v)
            if ret is not None:
                ret.add(i)
                return ret

        return None


M = inp()
mm = [] # i 番目の条件は mm[i] のラインのどこかに +1 をする
for m in range(M):
    u,v = inpl()
    u-=1; v-=1
    mm.append(dfs(u,-1,v))



dp = [0] * (1<<M)
dp[0] = 1

for i in range(N-1):
    # line i を白くした場合
    # dp[:] = dp[:]
    # line i を黒くした場合
    tmp = 0
    for b,m in enumerate(mm):
        if i in m:
            tmp += (1<<b)

    for b in reversed(range(1<<M)):
        dp[b | tmp] += dp[b]



print(dp[-1])


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = [[] for _ in range(N)]
for i in range(N-1):
    a,b = inpl()
    a-=1; b-=1
    lines[a].append((b,i))
    lines[b].append((a,i))


def dfs(s,b,v):
    if s == v:
        return set()
    else:
        for t,i in lines[s]:
            if t == b:
                continue
            ret = dfs(t,s,v)
            if ret is not None:
                ret.add(i)
                return ret

        return None


M = inp()
mm = [] # i 番目の条件は mm[i] のラインのどこかに +1 をする
for m in range(M):
    u,v = inpl()
    u-=1; v-=1
    mm.append(dfs(u,-1,v))



dp = [0] * (1<<M)
dp[0] = 1

for i in range(N-1):
    # line i を白くした場合
    # dp[:] = dp[:]
    # line i を黒くした場合
    tmp = 0
    for b,m in enumerate(mm):
        if i in m:
            tmp += (1<<b)

    for b in reversed(range(1<<M)):
        dp[b | tmp] += dp[b]



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


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()
if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while minsum:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    if not minsum:
        print("Yes")
    else:
        minsum.sort(key=lambda x: x[1])
    #     print(minsum, c)
        i = len(minsum)-1
        update = False
        while minsum:
            m, s = minsum[i]
            if c+m>=0:
                update = True
                minsum.pop(i)
                c += s
                i = len(minsum) - 1
            else:
                i -= 1
                if i<0 and not update:
                    print("No")
                    break
                else:
                    i = len(minsum) - 1
        else:
            print("Yes")

### FIXED CODE ###

def main():
    import queue
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))



    n = int(input())
    minsum = [None] * n # (min, sum)
    for i in range(n):
        tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
        c = 0
        m = 0
        for item in tmp:
            c += item
            m = min(c, m)
        minsum[i] = (m, sum(tmp))
    minsum.sort()

    if sum(item[1] for item in minsum)!=0:
        print("No")
    else:
        minsum1 = [item for item in minsum if item[1]>=0]
        minsum2 = [(item[0]-item[1], -item[1]) for item in minsum if item[1]<0]
        minsum2.sort()
        c = 0
        for m,s in minsum1[::-1]:
            if c+m>=0:
                c += s
            else:
                print("No")
                return
        c = 0
        for m,s in minsum2[::-1]:
            if c+m>=0:
                c+=s
            else:
                print("No")
                return
        print("Yes")
main()
### BUGGY CODE ###

n = int(input())

s = [sorted(list(input())) for _ in range(n)]

c = 0
for i in range(n):
    for j in range(i+1,n):
        if(s[i]==s[j]):c+=1
print(c)

### FIXED CODE ###

def comb(a,b):
    x = 1
    for i in range(a-b+1,a+1):x*=i
    for i in range(1,b+1):x//=i
    return(x)

n = int(input())

dict_num = {}

for _ in range(n):
    s = ''.join(sorted(list(input())))
    if(s in dict_num):dict_num[s]+=1
    else:dict_num[s] = 1

c=0
for k,v in dict_num.items():
    if(v>=2):c += comb(v,2)
print(c)
### BUGGY CODE ###

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

friend = [[0] * n for i in range(n)]
block = [[0] * n for i in range(n)]

not_see = [set() for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    friend[a][b] = 1
    friend[b][a] = 1
    not_see[a].add(b)
    not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    block[c][d] = 1
    block[d][c] = 1
    not_see[c].add(d)
    not_see[d].add(c)

for i in range(n):
    ans = 0
    for j in range(n):
        if i == j:
            continue
        if j in not_see[i]:
            continue
        if same(i, j):
            ans += 1
    print(ans)

### FIXED CODE ###

from collections import defaultdict


# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

not_see = defaultdict(set)

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    if same(a, b):
        not_see[a].add(b)
        not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    if same(c, d):
        not_see[c].add(d)
        not_see[d].add(c)

for i in range(n):
    print(size(i) - len(not_see[i]) - 1)
### BUGGY CODE ###


N,W = map(int,input().split())

wv = []
vmax = 0

for i in range(N):

    w,v = map(int,input().split())

    vmax += v
    wv.append([w,v])


lis = [[0] + [float("inf")] * vmax]

for i in wv:

    new = [0] + [float("inf")] * vmax

    for j in range(vmax+1):

        new[j] = min(new[j] , lis[-1][j])

        if j + i[1] <= vmax:

            new[j + i[1]] = min (new[j + i[1]] , lis[-1][j] + i[0])

    lis.append(new)

#print (lis)

lis[-1].reverse()

for i in range(vmax+1):

    if lis[-1][i] <= W:
        print (vmax - i)
        break

    

### FIXED CODE ###


N,W = map(int,input().split())

wv = []
vmax = 0

for i in range(N):

    w,v = map(int,input().split())

    vmax += v
    wv.append([w,v])


lis = [[0] + [float("inf")] * vmax]

for i in wv:

    new = [0] + [float("inf")] * vmax

    for j in range(vmax+1):

        new[j] = min(new[j] , lis[-1][j])

        if j + i[1] <= vmax:

            new[j + i[1]] = min (new[j + i[1]] , lis[-1][j] + i[0])

    lis.append(new)

#print (lis)

lis[-1].reverse()

for i in range(vmax+1):

    if lis[-1][i] <= W:
        print (vmax - i)
        break
### BUGGY CODE ###

import numpy as np

def red(out,count,N):
    for i in range(count):
        if(len(out)==N):
            break
        out.append("r")
    return out

def blue(out,count,N):
    for i in range(count):
        if(len(out)==N):
            break
        out.append("b")
    return out

NAB=np.array(input().split(" "),dtype=np.int32)

N=NAB[0]
A=NAB[1]
B=NAB[2]

out=[]

while(True):
    if(len(out)==N):
        break
    out=blue(out,A,N)
    out=red(out,B,N)

print(out.count("b"))

### FIXED CODE ###

import numpy as np

NAB=np.array(input().split(" "),dtype=np.int64)

N=NAB[0]
A=NAB[1]
B=NAB[2]

div=int(N//(A+B))
mod=N%(A+B)

blue=0
if(mod<=A):
    blue=mod
else:
    blue=A

print(A*div+blue)
### BUGGY CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

i = 1
while i < M:
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge = np.delete(edge,i,0)
  else:
    i += 1
    if i >= len(edge):
      break
x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))



### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge[i][2] = 0
#print(edge)
x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))
### BUGGY CODE ###

n=int(input())
l=[]
for i in range(500):
  l.append(i**2)
l=set(l)
for i in range(1,n+1):
  ct=0
  for j1 in range(1,int(n**0.5)+2):
    for j2 in range(1,int(n**0.5)+2):
      a=j1+j2
      b=i-j1**2-j2**2-j1*j2
      for k in range(len(l)):
        if a**2+4*b in l:
          k=int((a**2+4*b)**0.5)
          if (a+k)%2==0:
            j3=(-a+k)//2
            if j3>0:
              ct+=1
              break
  print(ct)

### FIXED CODE ###

n=int(input())
l=[]
for i in range(300):
  l.append(i**2)
l=set(l)
for i in range(1,n+1):
  ct=0
  for j1 in range(1,int(n**0.5)+2):
    for j2 in range(1,int(n**0.5)+2):
      a=j1+j2
      b=i-j1**2-j2**2-j1*j2
      if a**2+4*b in l:
        k=int((a**2+4*b)**0.5)
        if (a+k)%2==0:
          j3=(-a+k)//2
          if j3>0:
            ct+=1
  print(ct)
### BUGGY CODE ###

import sys
from collections import defaultdict
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = set()
h_targets = defaultdict(int)
w_targets = defaultdict(int)

for m in range(M):
    h, w = map(int, my_input().split())
    h, w = h - 1, w - 1
    targets.add((h, w))
    h_targets[h] += 1
    w_targets[w] += 1


ans = 0
for h in h_targets.keys():
    for w in w_targets.keys():
        ret = h_targets[h] + w_targets[w] - ((h, w) in targets)
        ans = max(ans, ret)
print(ans)


### FIXED CODE ###

import sys
from collections import Counter
from random import shuffle
my_input = sys.stdin.readline

H, W, M = map(int, my_input().split())
targets = set()
h_targets = []
w_targets = []

for m in range(M):
    h, w = map(int, my_input().split())
    h, w = h - 1, w - 1
    targets.add((h, w))
    h_targets.append(h)
    w_targets.append(w)

h_counter = Counter(h_targets).most_common()
w_counter = Counter(w_targets).most_common()

h_high = h_counter[0][1]
w_high = w_counter[0][1]

h_counter = [[k, v] for k, v in h_counter if v == h_high]
w_counter = [[k, v] for k, v in w_counter if v == w_high]
shuffle(h_counter)
shuffle(w_counter)

highest = h_high + w_high
for hk, hv in h_counter:
    for wk, wv in w_counter:
        if hv + wv < highest:
            break
        if ((hk, wk) not in targets):
            print(highest)
            exit()
print(highest - 1)
### BUGGY CODE ###

import numpy as np
N=int(input())
for i in range(int(np.sqrt(N))):
    a=int(np.sqrt(N))-i
    if N%a==0:
        print(a+N//a-2)
        break

### FIXED CODE ###

import numpy as np
N=int(input())
a=int(np.sqrt(N))
for i in range(int(np.sqrt(N))):
    if N%a==0:
        print(a+N//a-2)
        break
    a-=1
### BUGGY CODE ###

N = int(input())
l = []
istwo = False
for i in range(N):
    a = int(input())
    if a == 2: istwo = True
    l.append(a-1)
flag = [0]*N
flag[0] = 1
flag[1] = 2
cnt = 0
cur_b = 0
while istwo:
    cnt += 1
    next_b = l[cur_b]
    if flag[next_b] == 1:
        print(-1)
        break
    elif flag[next_b] == 2:
        print(cnt)
        break
    else:
        flag[next_b] == 1
        cur_b = next_b

if istwo == False:
    print(-1)

### FIXED CODE ###

N = int(input())
l = [(int(input())-1) for _ in range(N)]
flag = [0]*N
flag[0] = 1
flag[1] = 2
cnt = 0
cur_b = 0
for i in range(N):
    cnt += 1
    next_b = l[cur_b]
    if flag[next_b] == 1:
        print(-1)
        break
    elif flag[next_b] == 2:
        print(cnt)
        break
    else:
        flag[next_b] == 1
        cur_b = next_b
else:print(-1)
### BUGGY CODE ###

s = input()
k = int(input())
st = set()
for j in range(len(s)+1):
    for i in range(j):
        st.add(s[i:j])
for _ in range(k-1):
    m = min(st)
    st = [x for x in st if x != m]
print(min(st))

### FIXED CODE ###

s = input()
k = int(input())
st = set()
for i in range(len(s)):
    j = 1
    while j <= k and i+j <= len(s):
        st.add(s[i:i+j])
        j += 1
for _ in range(k-1):
    m = min(st)
    st = [x for x in st if x != m]
print(min(st))