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

n=int(input())
a=list(map(int,input().split()))
a_s=list(set(a))
cnt=0
for i in a_s:
    if a.count(i)<i:
        cnt+=a.count(i)
    elif a.count(i)>i:
        cnt+=a.count(i)-i
print(cnt)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
a_s=list(set(a))
c_l=Counter(a)

cnt=0
for i in a_s:
    if c_l[i]<i:
        cnt+=c_l[i]
    else:
        cnt+=c_l[i]-i
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
SUM = 0
for i in range(N-1):
    for j in range(i+1,N):
        SUM += A[i]*A[j] % MOD
    SUM %= MOD
print(SUM)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
S = sum(A) % MOD
ans = 0

for x in A:
    S -= x
    S %= MOD
    ans += S * x
    ans %= MOD
ans %= MOD
print(ans)
### BUGGY CODE ###

import numpy as np

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

npdata = np.arange(10**5+1)

kosuu=np.zeros(10**5+1)
kosuumoto=kosuu
for i in range(N):
    a=A[i]
    kosuu[a]+=1

BC_list=[]

for i in range (Q):
    bc=list(map(int,input().split()))
    BC_list.append(bc)
S=0
for i in range(Q):
    b=BC_list[i][0]
    c=BC_list[i][1]
    kosuu[c]=kosuu[c]+kosuu[b]
    kosuu[b]=0
    S=sum(np.multiply(npdata,kosuu))
    print(int(S))

    


### FIXED CODE ###


import numpy as np

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

npdata = np.arange(10**5+1)

kosuu=np.zeros(10**5+1)
kosuumoto=kosuu
for i in range(N):
    a=A[i]
    kosuu[a]+=1
SUM=sum(A)

BC_list=[]

for i in range (Q):
    bc=list(map(int,input().split()))
    BC_list.append(bc)
S=SUM
for i in range(Q):
    b=BC_list[i][0]
    c=BC_list[i][1]
    minus=b*kosuu[b]
    plus=c*kosuu[b]
    kosuu[c]=kosuu[c]+kosuu[b]
    kosuu[b]=0
    S=S-minus+plus
    print(int(S))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=float('inf')
tmp=0
ca=[tmp]
for x in a:
  tmp+=x
  ca.append(tmp)
from bisect import bisect_left as bl
for i in range(2,n-1):
  bc=ca[:i+1]
  de=ca[i+1:]
  de=[0]+[x-ca[i] for x in de]
  sumbc=bc[-1]
  bcidx=bl(bc,sumbc//2)
  p=bc[bcidx]
  q=bc[-1]-bc[bcidx]
  if bcidx>1:
    np=bc[bcidx-1]
    nq=bc[-1]-bc[bcidx-1]
    if abs(p-q)>abs(np-nq):p,q=np,nq

  sumde=de[-1]
  deidx=bl(de,sumde//2)
  r=de[deidx]
  s=de[-1]-de[deidx]
  if deidx>1:
    nr=de[deidx-1]
    ns=de[-1]-de[deidx-1]
    if abs(r-s)>abs(nr-ns):r,s=nr,ns
  ans=min(ans,max(p,q,r,s)-min(p,q,r,s))
print(ans)



### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
a=[0]
c=0
for si in s:
    c+=si
    a.append(c)
ans=[]
f=1
g=3
for i in range(2,n-1):
    while abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans.append(max(ls)-min(ls))
print(min(ans))
### BUGGY CODE ###

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a)

for i in range(n):
  #print(sort[i], l)
  if sort[i] == False:
    continue
  if l[i:] == [False]*len(sort[i:]):
    break
  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[ii] % sort[i] == 0:
      #print("割り切れる")
      l[ii] = False
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False

print(len([x for x in l if x]))
      

### FIXED CODE ###

from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)
#print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:#複数存在考慮
            ans+=1
print(ans)
### BUGGY CODE ###

import math
 
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
 
if K == 0:
  C = 0
else:
  C = int(math.log2(K + 1))
L = [[0 for i in range(50)] for j in range(C + 1)]
 
for i in A:
  for j in range(len(L[0])):
    if i % 2 == 1:
      i -= 1
      L[0][j] += 1
    if i == 0:
      break
    i /= 2
for i in range(1, C + 1):
  for j in range(50):
    L[i][j] = L[0][j]
 
x = pow(2, C)
T = [K for i in range(C + 1)]
for i in range(C, -1, -1):
  for j in range(C + 1):
    if T[j] >= x:
      if j != i and L[j][i] <= N / 2:
        L[j][i] = N - L[j][i]
        T[j] -= x
  x //= 2
 
Ans = [0 for i in range(C + 1)]
x = 1
for i in range(50):
  for j in range(C + 1):
    Ans[j] += L[j][i] * x
  x *= 2
 
print(max(Ans))

### FIXED CODE ###

import math
def main():
  N, K = list(map(int, input().split()))
  A = list(map(int, input().split()))
 
  if K == 0:
    C = 0
  else:
    C = int(math.log2(K + 1))
  L = [[0 for i in range(44)] for j in range(C + 1)]
 
  for i in A:
    for j in range(len(L[0])):
      if i % 2 == 1:
        i -= 1
        L[0][j] += 1
      if i == 0:
        break
      i /= 2
  for i in range(1, C + 1):
    for j in range(44):
      L[i][j] = L[0][j]
 
  x = pow(2, C)
  T = [K for i in range(C + 1)]
  for i in range(C, -1, -1):
    for j in range(C + 1):
      if T[j] >= x:
        if j != i and L[j][i] <= N / 2:
          L[j][i] = N - L[j][i]
          T[j] -= x
    x //= 2
 
  Ans = [0 for i in range(C + 1)]
  x = 1
  for i in range(44):
    for j in range(C + 1):
      Ans[j] += L[j][i] * x
    x *= 2
 
  print(max(Ans))

main()
### BUGGY CODE ###

N, K = map(int, input().split())
wd = [tuple(map(int, input().split())) for i in range(N)]
wd.sort()
d = 0
dp = [0]*N
l = 0
r = wd[0][0] + wd[0][1]*K
while(r - l > 1):
    tmp = (l+r)//2
    num = 0
    for w, d in wd:
        if w <= tmp:
            num += ((tmp - w) // d) + 1
    if num >= K:
        r = tmp
    else:
        l = tmp

print(r)


### FIXED CODE ###

import sys
N, K = map(int, input().split())
input = sys.stdin.readline
wd = [tuple(map(int, input().split())) for i in range(N)]
wd.sort()
d = 0
dp = [0]*N
l = 0
r = wd[0][0] + wd[0][1]*K
while(r - l > 1):
    tmp = (l+r)//2
    num = 0
    for w, d in wd:
        if w <= tmp:
            num += ((tmp - w) // d) + 1
    if num >= K:
        r = tmp
    else:
        l = tmp

print(r)
### BUGGY CODE ###

def isprime(num):
    if num==1:return False
    if num==2:return True
    for i in range(int(num/2)):
        if num%(i+2)==0:
            return False
        else:continue
    return True
    
def ct(num):
    count=0
    for i in range(num):
        if isprime(i+1):count+=1
    return count

def yak(num):
    if isprime(num):return [1,num]
    if num==1: return[1]
    for i in range(int(num/2)):
        if num%(i+2)==0:
            ret=yak(i+2)+yak(num/(i+2))
            ret.remove(1)
            return sorted([int(i) for i in ret])
    
        
while True:
    try:raw=[int(i) for i in input().split(" ")]
    except:break
    a=raw[0]
    print(str(ct(a)))

### FIXED CODE ###


import math

m=999999
s=int(math.sqrt(m)+1)
li=[0]*m
li[0]=1
for i in range(1,s):
    if li[i]==0:
        li[i*2+1::i+1]=[1 for e in range(len(li[i*2+1::i+1]))]
while True:
    try:n=int(input())
    except:break
    print(len([i for i in li[:n:] if i==0]))
### BUGGY CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += a[i] * combinations_count(n-i-1, k-1)

a.reverse()
for i in range(n-k+1):
    res -= a[i] * combinations_count(n-i-1, k-1)

print(res%MOD)

### FIXED CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def mpow(a, n):
    if n == 0:return 1
    if n == 1:return a%MOD
    if n%2 == 1:return (a%MOD * mpow(a, n-1)%MOD)%MOD
    t = mpow(a, n//2)
    return (t*t)%MOD

fac = [1]*(n+1)
inv_fac = [1]*(n+1)
for i in range(n):
    fac[i+1] = (fac[i]*(i+1))%MOD
inv_fac[n] = mpow(fac[n], MOD-2)
for i in range(n, 0, -1):
    inv_fac[i-1] = (inv_fac[i]*i)%MOD

def cmb(n, r):
    if n == 0 and r == 0:return 1
    if n<r or n<0:return 0
    return (fac[n]*(inv_fac[r]*inv_fac[n-r])%MOD)%MOD
 
a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
a.reverse()
for i in range(n-k+1):
    res -= (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
print(res)
### BUGGY CODE ###

import bisect
import numpy as np
n = int(input())
ls = np.array(list(sorted(map(int, input().strip().split()))))

total = 0

for i in range(len(ls) - 2):
    for j in range(i + 1, len(ls) - 1):
        a = ls[i]
        b = ls[j]
        ls2 = ls[j + 1:]
        if a + b == ls2[0]:
            num = 0
        else:
            num = bisect.bisect_right(ls2, a + b)
        total += num

print(total)


### FIXED CODE ###

import bisect


def main(ls):
    total = 0

    for i in range(len(ls) - 2):
        for j in range(i + 1, len(ls) - 1):
            a = ls[i]
            b = ls[j]
            left = j + 1
            num = bisect.bisect_left(ls, a + b) - left
            total += num

    print(total)


_n = input()
ls = list(sorted(map(int, input().strip().split())))

main(ls)
### BUGGY CODE ###

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

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


large = 10**10
time = 0
ans = 0
while len(A) != 0 or len(B) != 0:
    a = large
    b = large

    if len(A)!=0:
        a = A[0]
    if len(B)!=0:
        b = B[0]

    if a < b:
        if time+a > K:
            break
        time += a
        A = A[1:]
        ans += 1
    elif a > b:
        if time+b > K:
            break
        time += b
        B = B[1:]
        ans += 1


print(ans)


### FIXED CODE ###

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

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


new_A = [0]
pre = 0
for a in A:
    if a > K:
        break
    pre += a
    if pre > K:
        break
    new_A.append(pre)

new_B = [0]
pre = 0
for b in B:
    if b > K:
        break
    pre += b
    if pre > K:
        break
    new_B.append(pre)

ans = 0
j = len(new_B) - 1

for i, a in enumerate(new_A):
    while new_B[j] > K - a:
        j -= 1
    ans = max(ans, i+j)

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

nk = input()
nk = nk.split()
n = int(nk[0])
k = int(nk[1])

s = input()

count = 0
now = None
clist = []

for ss in s:
    if now is None:
        if ss == '0':
            clist.append(0)

    if now is None or now == ss:
        count += 1
    else:
        clist.append(count)
        count = 1
    now = ss

clist.append(count)

max_len = k * 2 + 1
max_sum = 0


for i in range(0, len(clist)):
    if i % 2 == 1:
        continue
    j = i + max_len
    try:
        max_sum = max(max_sum, sum(clist[i:j]))
    except:
        pass

print(max_sum)


### FIXED CODE ###

nk = input()
nk = nk.split()
n = int(nk[0])
k = int(nk[1])

s = input()

count = 0
now = None
clist = []

for ss in s:
    if now is None:
        if ss == '0':
            clist.append(0)

    if now is None or now == ss:
        count += 1
    else:
        clist.append(count)
        count = 1
    now = ss

clist.append(count)

max_len = k * 2 + 1
max_sum = 0
clist_len = len(clist)
now_sum = None

for i in range(0, clist_len):
    if i % 2 == 1:
        continue
    j = i + max_len

    if now_sum is None:
        now_sum = sum(clist[i:j])
        max_sum = now_sum
    else:
        now_sum -= sum(clist[(i-2):i])
        now_sum += sum(clist[(j-2):(j)])
        max_sum = max(max_sum, now_sum)

print(max_sum)
### BUGGY CODE ###

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

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i+1
xy.sort()
for i in range(N):
    xy[i][0] = i

# x<xi,y<yi
l1 = [0]*N
# x<xi,y>yi
l2 = [0]*N
# x>xi,y<yi
r1 = [0]*N
# x>xi,y>yi
r2 = [0]*N

bitl = BIT(N)
for i in range(N):
    l1[i] = bitl.sum(xy[i][1])
    l2[i] = i-l1[i]
    bitl.add(xy[i][1],1)

bitr = BIT(N)
for i in range(N):
    r1[N-i-1] = bitr.sum(xy[N-i-1][1])
    r2[N-i-1] = i-r1[N-i-1]
    bitr.add(xy[N-i-1][1],1)

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow(2,N-1,mod)*N%mod
for i in range(N):
    L1 = pow2[l1[i]]
    L2 = pow2[l2[i]]
    R1 = pow2[r1[i]]
    R2 = pow2[r2[i]]
    ans += L1*L2*R1*R2
    ans -= L1*R1
    ans -= L2*R2
    ans -= L1*L2
    ans -= R1*R2
    ans += L1+L2+R1+R2-1
    ans %= mod

print(ans)

### FIXED CODE ###

from operator import itemgetter

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

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

import sys
input = sys.stdin.readline

# s = "AACACTTTTAC"
# print(s.count("AC"))#3

lr=[]
s2 = ""
n, q = map(int, input().split())
s = input()
for i in range(q):
        l,r = map(int, input().split())
        lr.append([l,r])

for i in range(q):
        s2 = s[lr[i][0] - 1:lr[i][1]]
        # print(s2)
        print(s2.count("AC"))

### FIXED CODE ###

import numpy as np
n, q = map(int, input().split())
s = input()
lr = []
for i in range(q):
        l,r = map(int, input().split())
        lr.append([l,r])

n = len(s)
L = 0
R = 1
cntAC = [0] * n

for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        cntAC[i] += 1

# 累積和
cSum = np.cumsum(cntAC)


for _lr in lr:
    if _lr[L] == 1:
        print(cSum[_lr[R]-2])
    else:
        print(cSum[_lr[R]-2] - cSum[_lr[L]-2])
        

"""
ACACTACG
"""
### BUGGY CODE ###

alf=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
N=int(input())
li=[]
mi=[]
for i in range(N):
    s=input()
    temp=[0]*26
    for j in range(10):
        num=alf.index(s[j])
        temp[num]+=1
    if temp in li:
        mi[li.index(temp)]+=1
    else:
        li.append(temp)
        mi.append(1)
ans=0
for m in range(len(mi)):
    ans+=mi[m]*(mi[m]-1)//2
print(ans)


### FIXED CODE ###

N=int(input())
ans=0
li=[]
for i in range(N):
    s=list(input())
    s.sort()
    li.append(s)
li.sort()
temp=1
for j in range(N-1):
    if li[j]==li[j+1]:
        temp+=1
    else:
        ans+=temp*(temp-1)//2
        temp=1
        
ans+=temp*(temp-1)//2
print(ans)
### BUGGY CODE ###

import sys
diction = []
n = int(input())
command = sys.stdin.readlines()
for i in range(n):
    a,b = command[i].split()
    if a == "insert":
        diction.append(b)
    else:
        if b in diction:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

import sys
n = int(input())
dictionary = {}

k = sys.stdin.readlines()


for j in k:
    i = j.split()
    if i[0] == "insert":
        dictionary[i[1]] = 0
    else:
        if i[1] in dictionary:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

s = input()
n = len(s)
n = max((n, 3))
x, y = map(int, input().split())
dpx = [[False] * 2 * (n + 1) for i in range(n)]
dpy = [[False] * 2 * (n + 1) for i in range(n)]

def c(s):
    ret = 0
    while s and s[0] == 'F':
        ret += 1
        s = s[1:]
    if s and s[0] == 'T':
        s = s[1:]
    return s, ret

s, d = c(s)
dpx[0][n] = True
dpx[1][d+n] = True
dpy[0][n] = True
dp = [dpx, dpy]
turn = 0
while s:
    s, d = c(s)
    turn += 1
    nn = n - len(s)
    for i in range(-nn, nn+1):
        if -n <= i + d <= n:
            dp[turn%2][turn//2+1][i+d+n] = dp[turn%2][turn//2+1][i+d+n] \
                    or dp[turn%2][turn//2][i+n]
        if -n <= i - d <= n:
            dp[turn%2][turn//2+1][i-d+n] = dp[turn%2][turn//2+1][i-d+n] \
                    or dp[turn%2][turn//2][i+n]

if dpx[(turn-1)//2+2][x+n] and dpy[(turn-1)//2+1][y+n]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
x, y = map(int, input().split())
hL = len(s)
L = 2 * hL

dp = [[False] * (L + 1) for i in range(2)]
ndp = [False] * (L + 1)

def next(i):
    global s
    while i < hL and s[i] != 'T':
        i += 1
    i += 1
    return i

def c(x):
    global hL
    return x + hL

index = 0
t = 0
js = [1]
dp[0][c(0)] = True
dp[1][c(0)] = True
mini, maxi = 0, 1
while index < hL:
    ni = next(index)
    dx, index = ni - index - 1, ni
    for i in range(mini, maxi):
        for j in js:
            if -hL <= i + j * dx <= hL:
                nx = c(i + j * dx)
                ndp[nx] = ndp[nx] or dp[t][c(i)]
    for i in range(mini, maxi):
        dp[t][c(i)] = False
    dp[t], ndp = ndp, dp[t]
    mini, maxi = mini - dx, maxi + dx
    js = [-1, 1]
    t = (t + 1) % 2
print('Yes' if dp[0][c(x)] and dp[1][c(y)] else 'No')
### BUGGY CODE ###

N = int(input())
P = [i for i in range(1, N + 1)]
print(sum(P) - max(P))

### FIXED CODE ###

N = int(input())
print(N * (N - 1) // 2)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
field = [['#'] * (W + 2)]
for i in range(H):
    field.append(list('#' + input() + '#'))
field.append(['#'] * (W + 2))

def num_to_coo(p):
    h, w = divmod(p, W)
    h += 1
    w += 1
    return h, w

def bfs(s):
    noreach = [1] * (H * W)
    for _ in range(W):
        noreach.append(0)
    q = deque()
    q.append((s, 0))
    while q:
        p, c = q.popleft()
        noreach[p] = 0
        h, w = num_to_coo(p)
        if (field[h - 1][w] == '.') and noreach[p - W]:
            q.append((p - W, c + 1))
        if (field[h + 1][w] == '.') and noreach[p + W]:
            q.append((p + W, c + 1))
        if (field[h][w - 1] == '.') and noreach[p - 1]:
            q.append((p - 1, c + 1))
        if (field[h][w + 1] == '.') and noreach[p + 1]:
            q.append((p + 1, c + 1))
    return c

ans = -1
for s in range(H * W):
    h, w = num_to_coo(s)
    if field[h][w] == '.':
        ans = max(ans, bfs(s))
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
field = ''
for i in range(H):
    field += input()

def bfs(start):
    dist = [0] * (H * W)
    q = deque([start])
    while q:
        p = q.popleft()
        c = dist[p] + 1
        if p - W != start and p - W >= 0 and field[p - W] == '.' and dist[p - W] == 0:
            dist[p - W] = c
            q.append(p - W)
        if p + W != start and p + W < H * W and field[p + W] == '.' and dist[p + W] == 0:
            dist[p + W] = c
            q.append(p + W)
        if p - 1 != start and p - 1 >= 0 and field[p - 1] == '.' and dist[p - 1] == 0 and p % W != 0:
            dist[p - 1] = c
            q.append(p - 1)
        if p + 1 != start and p + 1 < H * W and field[p + 1] == '.' and dist[p + 1] == 0 and p % W != W - 1:
            dist[p + 1] = c
            q.append(p + 1)
    return dist[p]

ans = 0
for s in range(H * W):
    if field[s] == '.':
        ans = max(ans, bfs(s))
print(ans)
### BUGGY CODE ###

N = int(input())
As =[list(map(int, input().split())) for _ in range(N)]
flag1 = False
ans = 0
for i in range(N):
    for j in range(i+1, N):
        flag2 = True
        for k in range(N):
            if k == i or k == j:
                continue
            if As[i][k]+As[k][j] < As[i][j]:
                flag1 = True
                break
            elif As[i][k]+As[k][j] == As[i][j]:
                flag2 = False
        if flag2:
            ans += As[i][j]
        if flag1:
            break
    if flag1:
        break
if not flag1:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
As =[list(map(int, input().split())) for _ in range(N)]
flag1 = False
ans = 0
for i in range(N):
    for j in range(i+1, N):
        flag2 = True
        for k in range(N):
            if k == i or k == j:
                continue
            if As[i][k]+As[k][j] < As[i][j]:
                flag1 = True
                break
            elif As[i][k]+As[k][j] == As[i][j]:
                flag2 = False
        if flag2:
            ans += As[i][j]
        if flag1:
            break
    if flag1:
        break
if not flag1:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 1)

def dfs(i, V, E, num):
    V[i] = num
    for j in E[i]:
        if V[j] > 0:
            continue
        V = dfs(j, V, E, num)
    return V

n, k, l = map(int, input().split())
Er = defaultdict(list)
for i in range(k):
    p, q = map(int, input().split())
    Er[p].append(q)
    Er[q].append(p)
Et = defaultdict(list)
for i in range(l):
    r, s = map(int, input().split())
    Et[r].append(s)
    Et[s].append(r)

Vr_group = [None]
Vr = [0 for _ in range(n + 1)]
j = 1
for i in range(1, n + 1):
    if Vr[i] > 0:
        continue
    Vr = dfs(i, Vr, Er, j)
    Vr_group.append({t for t in range(1, n + 1) if Vr[t] == j})
    j += 1

Vt_group = [None]
Vt = [0 for _ in range(n + 1)]
j = 1
for i in range(1, n + 1):
    if Vt[i] > 0:
        continue
    Vt = dfs(i, Vt, Et, j)
    Vt_group.append({t for t in range(1, n + 1) if Vt[t] == j})
    j += 1

W = [[0 for j in range(len(Vt_group))] for i in range(len(Vr_group))]
for i in range(1, len(Vr_group)):
    for j in range(1, len(Vt_group)):
        W[i][j] = len(Vr_group[i] & Vt_group[j])
ans = []
for i in range(1, n + 1):
    ans.append(W[Vr[i]][Vt[i]])
print(' '.join([str(x) for x in ans]))


### FIXED CODE ###

import sys
from collections import Counter

class UnionFind(object):
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0 for i in range(n + 1)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1

sys.setrecursionlimit(10 ** 5 + 1)

n, k, l = map(int, input().split())
Ur = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    Ur.union(p, q)

Ut = UnionFind(n)
for i in range(l):
    r, s = map(int, input().split())
    Ut.union(r, s)

x = [(Ur.find(i + 1), Ut.find(i + 1)) for i in range(n)]
c = Counter(x)
ans = []
for i in range(n):
    ans.append(c[x[i]])
print(' '.join([str(a) for a in ans]))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
list = [0]*q

for i in range(q):
    start,end=map(int, input().split())
    list[i] = s.count("AC", start-1, end)

for i in list:
    print(i)



### FIXED CODE ###

n, q = map(int, input().split())
s = input()
x = [0]*(n+1)

for i in range(n):
    x[i+1] = x[i] + (1 if s[i:i+2] == "AC" else 0)

for i in range(q):
    l, r = map(int, input().split())
    print(x[r-1] - x[l-1])