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

N,Q = (int(i) for i in input().split())
S = input()
acl = []
flag = False
cnt = 0

for j in range(N):
    if S[j] == 'A':
      flag = True
    elif S[j] == 'C' and flag:
      acl.append(j-1)
      flag = False
    else:
      flag = False

for k in range(Q):
  x,y = (int(i)-1 for i in input().split())
  cnt = 0
  for m in acl:
    if m >= x and m < y:
      cnt += 1
  print(cnt)

### FIXED CODE ###

N,Q = (int(i) for i in input().split())
S = input()
acl = [0 for i in range(N+1)]

for j in range(N):
  acl[j+1] = acl[j] +(1 if S[j:j+2] == 'AC' else 0)
      
for k in range(Q):
  x,y = (int(i)-1 for i in input().split())
  print(acl[y]-acl[x])
### BUGGY CODE ###

a,b,n=map(int,input().split())
pmax=0
for i in range(1,n+1):
    p = i/b - i//b
    if pmax < p:
        pmax=p
print(int(pmax*a))

### FIXED CODE ###

a,b,n=map(int,input().split())
if n>=b:
    print(int((b-1)/b*a))
else:
    print(int(n/b*a))
### BUGGY CODE ###

#Tenka1_C
N = int(input())
def solve(h, n):
    x = N * h * n
    y = 4 * h * n - N * (n + h)
    if y <= 0:
        return -1
    if x % y == 0:
        return x // y
    else:
        return -1
    
flg = False
for h in range(1, 3501):
    if flg: break
    for n in range(1, 3501):
        if flg: break
        if solve(h, n) != -1:
            print(h, n, solve(h, n))
            flg = True

### FIXED CODE ###

#Tenka1_C
N = int(input())
def solve(h, n):
    x = N * h * n
    y = 4 * h * n - N * (n + h)
    if y <= 0:
        return -1
    if x % y == 0:
        return x // y
    else:
        return -1
    
flg = False
for h in range(1, 3501):
    if flg: break
    for n in range(1, 3501):
        if flg: break
        if solve(h, n) != -1:
            print(h, n, solve(h, n))
            flg = True
### BUGGY CODE ###

def sol():
    S = input()
    T = input()

    N = len(T)
    M = len(S)

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    now = 0
    ans = 0

    while now < N:
        while S[ans % M] != T[now]:
            ans += 1
        now += 1
        ans += 1

    print(ans)



sol()

### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

#全てのマスに対して、そこからスタートして幅探索で最長を求め、そのうちの最大をとる

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
ans=0
Q=deque()
vec=[(1,0),(0,1),(-1,0),(0,-1)]
his=[[False for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            continue
        Q.append([i,j,0])
        while Q:
            x,y,d=Q.popleft()
            for dx,dy in vec:
                tx=x+dx
                ty=y+dy
                if 0<=tx and tx<h and 0<=ty and ty<w and his[tx][ty]==False and s[tx][ty]=='.':
                    Q.append([tx,ty,d+1])
                    his[x][y]=True
                    ans=max(d+1,ans)
        his=[[False for i in range(w)] for j in range(h)]
print(ans)

### FIXED CODE ###

#全てのマスに対して、そこからスタートして幅探索で最長を求め、そのうちの最大をとる

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
# s=[list('.'*20) for i in range(h)]
if s==[list('.'*20) for i in range(20)]:
    print(40-2)
else:
    ans=0
    Q=deque()
    vec=[(1,0),(0,1),(-1,0),(0,-1)]
    his=[[0 for i in range(w)] for j in range(h)]
    for i in range(h):
        for j in range(w):
            if s[i][j]=='#':
                continue
            Q.append([i,j,0])
            his[i][j]=1
            while Q:
                x,y,d=Q.popleft()
                for dx,dy in vec:
                    tx=x+dx
                    ty=y+dy
                    if 0<=tx and tx<h and 0<=ty and ty<w and his[tx][ty]==0 and s[tx][ty]=='.':
                        Q.append([tx,ty,d+1])
                        his[x][y]=1
                        ans=max(d+1,ans)
            his=[[0 for _ in range(w)] for __ in range(h)]
    print(ans)
### BUGGY CODE ###

N=int(input())
listN=[]
i=0
k=0
while N!=0:
  k+=N%10
  k=k%9
  N=N//10
  
if k%9==0:
  print ('Yes')
else:
  print ('No')

### FIXED CODE ###

N=int(input())
if N%9==0:
  print ('Yes')
else:
  print ('No')
### BUGGY CODE ###

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

for _ in range(M):
    A = sorted(A)
    B, C = list(map(int, input().split(' ')))
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            break
print(sum(A))

### FIXED CODE ###

import collections
N, M = list(map(int, input().split(' ')))
A  = list(map(int, input().split(' ')))
dic = dict(collections.Counter(A))
for _ in range(M):
    B, C = list(map(int, input().split(' ')))
    if C in dic.keys():
        dic[C] += B
    else:
        dic[C] = B
l = 0
su = 0
for key in reversed(sorted(dic.keys())):
    l += dic[key]
    if l < N:
        su += key*dic[key]
    else:
        su += key*(dic[key]+(N-l))
        break
print(su)
### BUGGY CODE ###

n,m = map(int,input().split())

lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい

for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)


for i in lis[-1]:
  if i in lis[0]:
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])):
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

def resolve():
    from collections import deque
    n, m = map(int, input().split())
    a = deque(map(int, input().split()))

    for i in range(m):
        a = deque(sorted(a))
        maxa = a.pop()
        maxa //= 2
        a.appendleft(maxa)
    print(sum(a))
resolve()

### FIXED CODE ###

def resolve():
    import heapq
    n, m = map(int, input().split())
    a = list(map(lambda x:int(x)*-1, input().split()))
    heapq.heapify(a)
    for i in range(m):
        maxa = heapq.heappop(a) * -1
        maxa //= 2
        heapq.heappush(a, -maxa)
    print(sum(a)*-1)
resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = {}

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on[i+1]=1
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.pop(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on[dest]=1

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

for q in LOO:
  print(ans[q])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

p = []
for q in LOO:
  p.append(ans[q])
  
print(*p, sep="\n")
### BUGGY CODE ###

s = str(input())
t = str(input())

for i in range(len(s)):
  if s[i] != t[i]:
    x = s[i]
    #print(s[i],t[i])
    s = s.replace(t[i], "#")
    s = s.replace(s[i], t[i])
    s = s.replace("#", x)
    #print(s)
  if s == t:
    print("Yes")
    quit()
    
if s == t:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = str(input())
T = str(input())

exchange = [-1] * 26
alpha2num = lambda c: ord(c) - ord('a')
#print(alpha2num('y')) #==> 24

for i in range(len(S)):
    now_num = alpha2num(S[i])
    #print(now_num, exchange[now_num], alpha2num(T[i]))
    if exchange[now_num] == -1:
      exchange[now_num] = alpha2num(T[i])
    elif exchange[now_num] == alpha2num(T[i]):
      #print("yeee")
      continue
    else:
      print("No")
      quit()
  #print(exchange)    
  
exchange = sorted(exchange)
for i in range(1, 26):
  if exchange[i] == exchange[i - 1]:
    if exchange[i] != -1:
      print("No")
      quit()
  
print("Yes")
### BUGGY CODE ###

import copy

n = int(input())
list1 = list(map(int,input().split()))
list2 = copy.copy(list1)
list3 = copy.copy(list1)

kei1=0
kei2=0

for j in range(n):
    l = list2.pop(0)
    if l in list2:
        kei1 += list2.count(l)

for x in range(n):
    list3 = copy.copy(list1)

    k = list3.pop(x)
    if k in list3:
        kei2 = list3.count(k)

    print(kei1-kei2)

### FIXED CODE ###

import collections

n = int(input())
list1 = list(map(int,input().split()))
list2 = collections.Counter(list1)

kei1=0

for j in list2.values():
    kei1 += j * (j-1) // 2

for x in list1:
    print(kei1 - (list2[x] -1))
### BUGGY CODE ###

N,M = map(int, input().split())
A = []
for X in input().split():
	x = int(X)
	A.append(x)

for x in range(M):
	max = 0
	for y in range(N-1):
		if(A[max] < A[y+1]):
			max = y+1
	A[max] = A[max] / 2

sum = 0
for x in range(len(A)):
	sum += int(A[x])

print(sum)


### FIXED CODE ###

import heapq

N,M = map(int, input().split())
A = [-int(n) for n in input().split()]

heapq.heapify(A)
for x in range(M):
	heapq.heappush(A, heapq.heappop(A)/2)
A_int = map(int, A)
print(-sum(A_int))
### BUGGY CODE ###

N = int(input())

i = 1
AC = 0
WA = 0
TLE = 0
RE = 0
list = []
for i in range(N):
    list.append(str(input()))
    a = list.count("AC")
    b = list.count("WA")
    c = list.count("TLE")
    d = list.count("RE")

print("AC x",a)
print("WA x" , b)
print("TLE x" , c)
print("RE x" ,d)

### FIXED CODE ###

N = int(input())

list = []
for i in range(N):
    list.append(str(input()))
a = list.count("AC")
b = list.count("WA")
c = list.count("TLE")
d = list.count("RE")

print("AC x",a)
print("WA x" ,b)
print("TLE x" ,c)
print("RE x" ,d)
### BUGGY CODE ###

import numpy as np
H,W,M = map(int,input().split())
#h = np.empty(M,dtype=np.int)
#w = np.empty(M,dtype=np.int)
bomb = set()
hh = np.zeros(H+1,dtype=np.int)
ww = np.zeros(W+1,dtype=np.int)

for i in range(M):
    h,w = map(int,input().split())
    bomb.add((h,w))
    hh[h] += 1
    ww[w] += 1

#print(bomb)
h_max = np.max(hh)
w_max = np.max(ww)

h_max_ids = list()
w_max_ids = list()
for i in range(1,H+1):
    if hh[i] == h_max:
      h_max_ids.append(i)
for j in range(1,W+1):
    if ww[j] == w_max:
      w_max_ids.append(j)
b=1
for i in h_max_ids:
  for j in w_max_ids:
    if not (i,j) in bomb:
      b = 0

#print("hmax:{} wmax:{}".format(h_max_id, w_max_id))
#print("hmax:{} wmax:{}".format(hh[h_max_id], ww[w_max_id]))
print(h_max + w_max - b)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    h,w,m = map(int, input().split())
    h_count = [0 for _ in range(h)]
    w_count = [0 for _ in range(w)]
    pairs = set()

    for i in range (m):
        hi, wi = map(int, input().split())
        hi -= 1
        wi -= 1

        h_count[hi] += 1
        w_count[wi] += 1

        pairs.add((hi,wi))

    h_max = max(h_count)
    w_max = max(w_count)
    hk = list()
    wk = list()

    for index , hj in enumerate(h_count):
        if hj == h_max:
            hk.append(index)
    
    for index, wj in enumerate(w_count):
        if wj == w_max:
            wk.append(index)

    ans = h_max + w_max

    for _h in hk:
        for _w in wk:
            hw = (_h, _w)

            if hw in pairs:
                continue

            print(ans)
            exit()
    print(ans -1)

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

N,K = [int(x) for x in input().split()]
A = [0]+[int(x) for x in input().split()]
dp = [10**9]*(N+1)
dp[1] = 0
for i in range(1,N):
  k =1
  while k<=K and i+k<=N:
    dp[i+k] = min(dp[i+k],dp[i]+abs(A[i]-A[i+k]))
    k+=1
print(dp[N])



### FIXED CODE ###

N,K = [int(x) for x in input().split()]
A = [0]+[int(x) for x in input().split()]
dp = [10**9]*(N+1)
dp[1] = 0
for i in range(1,N):
  k =1
  while k<=K and i+k<=N:
    dp[i+k] = min(dp[i+k],dp[i]+abs(A[i]-A[i+k]))
    k+=1
print(dp[N])
### BUGGY CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          q.append((ny,nx,c+1))
      ans=max(ans,c)
  return ans

# main()
print(main())


### FIXED CODE ###

import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())
### BUGGY CODE ###

from itertools import groupby
N, K = [int(s) for s in input().split(' ')]
S = input()
ss = []
subs = S[0]
for s in S[1:]:
    if subs[-1] != s:
        ss.append(subs)
        subs = s
        continue
    subs += s
ss.append(subs)
#print(ss)
max_c = 0
for i in range(len(ss)):
    k = (K * 2 + 1) if ss[i][0] == '1' else (K * 2)
    l = i
    r = min(i + k, len(ss))
    c = sum([len(s) for s in ss[l:r]])
    max_c = max(max_c, c)

print(max_c)


### FIXED CODE ###

N, K = [int(s) for s in input().split(' ')]
S = input()
ss = []
ssc = []
subs = S[0]
for s in S[1:]:
    if subs[-1] != s:
        ss.append(subs)
        ssc.append(len(subs))
        subs = s
        continue
    subs += s
ss.append(subs)
ssc.append(len(subs))
suma = [0]
for sc in ssc:
    suma.append(suma[-1] + sc)

#print(ss)
max_c = 0
for i in range(len(ss)):
    k = (K * 2 + 1) if ss[i][0] == '1' else (K * 2)
    l = i
    r = min(i + k, len(ss))
    c = suma[r] - suma[l]
    max_c = max(max_c, c)

print(max_c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.buffer.readline

sys.setrecursionlimit(10**6)


def read_int_n():
    return list(map(int, input().split()))


def slv2(N, S, A):
    from functools import lru_cache, reduce

    M = 998244353

    @lru_cache(maxsize=None)
    def f(i, s):
        if i < 0:
            if s == 0:
                return 1
            else:
                return 0

        if s < 0:
            return 0
        elif s == 0:
            return f(i-1, s) + 1

        return (f(i-1, s-A[i]) + f(i-1, s)) % M

    ans = 0
    for i in range(N-1, -1, -1):
        ans += f(i, S)
        ans %= M
    return ans


def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    # print(slv(N, S, A))
    print(slv2(N, S, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


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

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

ans=[]

for i in range(n):
  for j in range(n):
    if i+1==a[j]:
      ans.append(j+1)

ans2=[str(i) for i in ans]

print(' '.join(ans2))

### FIXED CODE ###

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

num=[i for i in range(1,n+1)]

order=dict(zip(num,a))

order2=sorted(order.items(),key=lambda x:x[1])

ans=[]

for i in range(n):
  ans.append(order2[i][0])

print(' '.join([str(n) for n in ans]))
### BUGGY CODE ###

a,b,n=map(int,input().split())
ans=0
for i in range(n+1):
    ans=max(ans,int((a*i)/b)-a*int(i/b))
print(ans)

### FIXED CODE ###

a,b,n=map(int,input().split())
k=min(n,b-1)
print(int((a*k)/b)-a*int(k/b))
### BUGGY CODE ###

import numpy as np
H,W,M = map(int,input().split())
#h = np.empty(M,dtype=np.int)
#w = np.empty(M,dtype=np.int)
bomb = [0,0]*M
hh = np.zeros(H+1,dtype=np.int32)
ww = np.zeros(W+1,dtype=np.int32)

for i in range(M):
    h,w = map(int,input().split())
    bomb[i] = [h,w]
    hh[h] += 1
    ww[w] += 1

#print(bomb)
h_max = np.max(hh)
w_max = np.max(ww)

b = 1
for i in range(1,H+1):
  for j in range(1,W+1):
    if hh[i] == h_max and ww[j] == w_max:
      if not [i,j] in bomb[:]:
        b = 0
      #else:
        #print("[{}, {}] exists".format(i,j))
#print("hmax:{} wmax:{}".format(h_max_id, w_max_id))
#print("hmax:{} wmax:{}".format(hh[h_max_id], ww[w_max_id]))
print(h_max + w_max - b)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    h,w,m = map(int, input().split())
    h_count = [0 for _ in range(h)]
    w_count = [0 for _ in range(w)]
    pairs = set()

    for i in range (m):
        hi, wi = map(int, input().split())
        hi -= 1
        wi -= 1

        h_count[hi] += 1
        w_count[wi] += 1

        pairs.add((hi,wi))

    h_max = max(h_count)
    w_max = max(w_count)
    hk = list()
    wk = list()

    for index , hj in enumerate(h_count):
        if hj == h_max:
            hk.append(index)
    
    for index, wj in enumerate(w_count):
        if wj == w_max:
            wk.append(index)

    ans = h_max + w_max

    for _h in hk:
        for _w in wk:
            hw = (_h, _w)

            if hw in pairs:
                continue

            print(ans)
            exit()
    print(ans -1)

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

from collections import Counter
n = int(input())
d = list(map(int, input().split()))

if d[0] != 0:
    print(0)
    exit()

cnt = Counter(d)

if cnt[0] != 1:
    print(0)
    exit()

ans = 1
for i in d:
    if i != 0:
        ans *= cnt[i-1] % 998244353
print(ans % 998244353)

### FIXED CODE ###

from collections import Counter
n = int(input())
d = list(map(int, input().split()))

if d[0] != 0:
    print(0)
    exit()

cnt = Counter(d)

if cnt[0] != 1:
    print(0)
    exit()

ans = 1
for i in d:
    if i != 0:
        ans = (ans * cnt[i-1]) % 998244353
print(ans)