Harryxun/stf_run huggingface dataset:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

n,k,c=sep()
s=input()
c1=[0]*(n+5)
c2=[0]*(n+5)
for i in range(n):
    if s[i]=="x":
        c1[i]=c1[i-1]
    else:
        c1[i]=max(c1[i-1],c1[i-c-1]+1)
for i in range(n-1,-1,-1):
    if s[i]=="x":
        c2[i]=c2[i+1]
    else:
        c2[i]=max(c2[i+1],c2[i+c+1]+1)
ans=[]
if c2[1]==k-1 and s[0]=="o":
    ans.append(1)

for i in range(1,n-1):
    if s[i]=="x":
        continue
    if c1[i-1] + c2[i+1]==k-1:
        ans.append(i+1)

if n!=1:
    if c1[n-2]==k-1 and s[0]=="o":
        ans.append(n)

for i in ans:
    print(i)




### FIXED CODE ###

def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())
import sys
sys.setrecursionlimit(10**6)

n,k,c=sep()
s=input()
c1=[0]*(n+5)
c2=[0]*(n+5)
for i in range(n):
    if s[i]=="x":
        c1[i]=c1[i-1]
    else:
        c1[i]=max(c1[i-1],c1[i-c-1]+1)
for i in range(n-1,-1,-1):
    if s[i]=="x":
        c2[i]=c2[i+1]
    else:
        c2[i]=max(c2[i+1],c2[(i+c+1)%n]+1)
ans=[]
if c2[1]==k-1 and s[0]=="o":
    ans.append(1)

for i in range(1,n-1):
    if s[i]=="x":
        continue
    if c1[i-1] + c2[i+1]==k-1:
        ans.append(i+1)

if n!=1:
    if c1[n-2]==k-1 and s[0]=="o":
        ans.append(n)

for i in ans:
    print(i)
N=int(input())
lst=list(map(int,input().split()))
lst_=sorted(lst)
def f(b):
  ans=0
  for i in range(1,N+1):
    ans+=abs(lst[i-1]-(b+i))
  return ans

if N%2==1:
  b=lst_[(N-1)//2]-((N-1)//2+1)
  print(f(b))
else:
  b1=lst_[N//2]-(N//2+1)
  b2=lst_[b1-1]-(b1+1)
  print(min(f(b1),f(b2)))

### FIXED CODE ###

import copy
N=int(input())
lst=list(map(int,input().split()))
lst2=copy.copy(lst)
for i in range(1,N+1):
  lst2[i-1]-=i
lst2=sorted(lst2)
b=lst2[N//2]
ans=0
for i in range(N):
  ans+=abs(lst[i]-(b+i+1))
print(ans)
n , m = map(int , input().split())
edge = [[] for _ in range(m) ]
#print(edge)
for _ in range(m):
    a , b = map(int , input().split())
    a -= 1 ; b -= 1
    edge[a].append(b)
    edge[b].append(a)
#print(edge)

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        #print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

ans = 0
visited = [False] * n
visited[0] = True
ans += DFS(0)
print(ans)


### FIXED CODE ###

n , m = map(int , input().split())
edge = [[] for _ in range(n) ]
#print(edge)
for _ in range(m):
    a , b = map(int , input().split())
    a -= 1 ; b -= 1
    edge[a].append(b)
    edge[b].append(a)
#print(edge)

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        #print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

ans = 0
visited = [False] * n
visited[0] = True
ans += DFS(0)
print(ans)
%%test_input https://atcoder.jp/contests/abc096/tasks/abc096_c
# 巡回セールスマン問題？
H, W = map(int, input().split())
mat = [input() for i in range(W)]
mat_t = [''.join(x) for x in zip(*mat)]
def check(mat, t):
    stack = set()
    for i, string in enumerate(mat):
        string = '.' + string + '.'
        for j in range(len(string)):
            if j+3<=len(string):
                if string[j:j+3] == '.#.':
                    if t==False:
                        stack.add((i, j))
                    else:
                        stack.add((j, i))
    return stack

stack1 = check(mat, False)
stack2 = check(mat_t, True)
if stack1 & stack2:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

H, W = map(int, input().split())
mat = [input() for i in range(H)]
mat_t = [''.join(x) for x in zip(*mat)]
def check(mat, t):
    stack = set()
    for i, string in enumerate(mat):
        string = '.' + string + '.'
        for j in range(len(string)):
            if j+3<=len(string):
                if string[j:j+3] == '.#.':
                    if t==False:
                        stack.add((i, j))
                    else:
                        stack.add((j, i))
    return stack

stack1 = check(mat, False)
stack2 = check(mat_t, True)
if stack1 & stack2:
    print('No')
else:
    print('Yes')
W,H,x,y = map(int,input())

menseki = W*H/2
if x==W/2 and y==H/2:
    ans = 1
else:
    ans = 0
print(menseki,ans)


### FIXED CODE ###

W,H,x,y = map(int,input().split())

menseki = W*H/2
if x==W/2 and y==H/2:
    ans = 1
else:
    ans = 0
print(menseki,ans)
White True:
    x = input()
    print x**3

### FIXED CODE ###

x = input()
print x**3
n = int(input())
a = list(map(int, input().split()))
result = 1
checker =False
for j in a:
  if j > 1000000000000000000:
    result = -1
    checker =True
if 0 in a:
  result = 0
  checker=True
while checker==False:
  import numpy as np
  a = np.array(a)
  result = a.prod()
  checker = True
    

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
result = 1
for i in range(len(a)):
  result = result*a[i]
  if result == 0:
    break
  elif result > 1000000000000000000:
    break

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)
import sys, math

def calcSum(AList, B, C, Sum):
    Len = AList[B]
    Sum += (C-B) * Len

    AList[B] = 0
    AList[C] += Len
    return Sum

if(__name__ == "__main__"):

    

    N= int( input().strip() )

    Max = 10**5
    AList = [0] * Max
    A_str = input().strip().split()
    N_Queries = int( input().strip() )

    sum = 0
    for i in range(N):
        value = int(A_str[i])
        AList[value] += 1
        sum += value
    BCs = []
    for i in range(N_Queries):
        BC_str =  input().strip().split()
        BC = [ int(BC_str[0]), int(BC_str[1]) ]
        BCs.append(BC)

    for i in range(N_Queries):
        B= BCs[i][0]
        C= BCs[i][1]
        sum = calcSum(AList, B, C, sum)
        print(sum)


### FIXED CODE ###

import sys, math

def calcSum(AList, B, C, Sum):
    Len = AList[B]
    if(Len == 0):
        return Sum
    Sum += (C-B) * Len

    AList[B] = 0
    AList[C] += Len
    return Sum

if(__name__ == "__main__"):
    N= int( input().strip() )

    Max = int(10**5)+1
    AList = [0] * Max
    A_str = input().strip().split()
    N_Queries = int( input().strip() )

    sum = 0
    for i in range(N):
        value = int(A_str[i])
        AList[value] += 1
        sum += value
    BCs = []
    Sums = [sum]
    for i in range(N_Queries):
        BC_str =  input().strip().split()
        B = int(BC_str[0])
        C = int(BC_str[1])
        Sums.append( calcSum(AList, B, C, Sums[-1]) )
        """
        BC = [ int(BC_str[0]), int(BC_str[1]) ]
        BCs.append(BC)
        """

    for i in range(1, 1+N_Queries):
        print(Sums[i])
N, Q = map(int, input().split())
S = input()
AClst = []
count = 0

for i in range(N-1):
  if S[i:i+2]=="AC":
    c += 1
  AClst.append(c)
AClst.append(c)

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

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AClst = [0]
c = 0

for i in range(N-1):
  if S[i:i+2]=="AC":
    c += 1
  AClst.append(c)

for q in range(Q):
  l, r = map(int, input().split())
  print(AClst[r-1]-AClst[l-1])
import sys

sys.setrecursionlimit(sys.getrecursionlimit())
N = int(input())
A = list(map(int,input().split(" ")))

def gcd (a: int,b: int) -> int:
    if a < b: a,b = b,a
    return a if b == 0 else gcd(b,a%b)
def lcm (a: int,b: int) -> int:
    return a // gcd(a,b) * b

def dfs(i,v,flg):
    if i == N-1:
        if flg:
            return gcd(A[N-1],v)
        else:
            return v
    if flg:
        return dfs(i+1,gcd(A[i],v),True)
    else:
        return max(dfs(i+1,gcd(v,A[i]),False),dfs(i+1,v,True))

if N == 2:
    print(max(A))
    exit(0)
else:
    print(max(dfs(1,A[0],False),dfs(2,A[1],True)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(sys.getrecursionlimit())
N = int(input())
A = list(map(int,input().split(" ")))

def gcd (a: int,b: int) -> int:
    if a < b: a,b = b,a
    return a if b == 0 else gcd(b,a%b)
def lcm (a: int,b: int) -> int:
    return a // gcd(a,b) * b

gcdForward = [0] * N
gcdBackWard = [0] * N
gcdForward[0] =  A[0]
gcdBackWard[N-1] = A[-1]
for i in range(N-1):
    gcdForward[i+1] = gcd(gcdForward[i],A[i+1])
    gcdBackWard[N-i-2] = gcd(gcdBackWard[N-i-1],A[N-i-2])


if N == 2:
    print(max(A))
    exit(0)
else:
    ans = max(gcdBackWard[1],gcdForward[N-2])
    for i in range(1,N-1):
        ans = max(ans,gcd(gcdForward[i-1],gcdBackWard[i+1]))
    print(ans)
from math import sqrt

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    lim = int(sqrt(a))
    divset = set()
    for i in range(1, lim + 1):
        if a % i == 0:
            divset |= {i, a//i}
    return divset

def is_prime(a):
    lim = int(sqrt(a))
    for i in range(2, lim + 1):
        if a != i and a % i == 0: return False
    else: return True

N = int(input())
A = [int(input()) for n in range(N+1)]

gcd_of_A = A[N]
for i in reversed(range(N)):
    if A[N] != 0:
        gcd_of_A = gcd(abs(A[i]), gcd_of_A)

primes = [int(i) for i in range(2, N+1)]
primes = set(primes)
for i in range(2, N+1):
    temp = set()
    for p in primes:
        if p % i > 0 or p == i: temp |= {p}
    primes = temp

ans = []
for p in primes:
    for i in range(p-1):
        coefficient = 0
        index_a = i
        while index_a <= N:
            coefficient += A[index_a] % p
            coefficient %= p
            index_a += p-1
        if coefficient % p > 0: break
    else: ans.append(p)
used = set(ans)

divisor_of_An = divisor(A[N])
for div in divisor_of_An:
    if div > N:
        if is_prime(div):
            if gcd_of_A % div == 0 and div not in used: ans.append(div)
ans.sort()
for a in ans: print(a)

### FIXED CODE ###

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a%b
    return b

def divisor(a):
    i = 1
    divset = set()
    while i * i <= a:
        if a % i == 0: divset |= {i, a//i}
        i += 1
    divset.remove(1)
    return divset

def is_prime(a):
    if a <= 3: 
        prime = [False, False, True, True]
        return prime[a]
    i = 2
    while i * i <= a:
        if a % i == 0: return False
        i += 1
    else: return True

N = int(input())
A = [None] * (N+1)
for i in reversed(range(N+1)):
    A[i] = int(input())

primes_bool = [True] * (N + 1)
primes = []
for p in range(2, N+1):
    if primes_bool[p]:
        primes.append(p)
        p_mult = p * 2
        while p_mult <= N:
            primes_bool[p_mult] = False
            p_mult += p

ans = []
used = set()
gcd_of_A = abs(A[N])
for a in A[:N]:
    if a != 0: gcd_of_A = gcd(abs(a), gcd_of_A)

commondiv = divisor(gcd_of_A)
for d in commondiv:
    if d > 1 and is_prime(d): 
        ans.append(d)
        used |= {d}

for p in primes:
    if A[0] % p == 0:
        for i in range(1, p):
            coefficient = 0
            index_a = i
            while index_a <= N:
                coefficient += A[index_a]
                coefficient %= p
                index_a += p-1
            if coefficient > 0: break
        else:
            if p not in used: ans.append(p)

ans.sort()
for a in ans: print(a)
# -*- coding: utf-8 -*-


def main():
    s = input()
    removed_a = s.replace('A', '')

    if 4 < len(s) < 10 and removed_a != 'KIHBR':
        print('NO')
    else:
        if s.index('K') <= 1 and (s.index('B') - s.index('H')) <= 1 and (len(s) - 1 - s.index('R')) <= 1:
            print('YES')
        else:
            print('NO')


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    from re import search

    s = input()
    removed_a = s.replace('A', '')

    if (len(s) < 5 or len(s) < 10) and removed_a != 'KIHBR':
        print('NO')
    else:
        pattern = r'^A?KIHA?BA?RA?$'
        is_match = search(pattern, s)

        if is_match:
            print('YES')
        else:
            print('NO')


if __name__ == '__main__':
    main()
n,m=map(int,input().split())
a=['.']
a*=n
ans=0
for i in range(m):
    si,ci=input().split()
    si=int(si)
    ci=str(ci)
    if a[si-1]=='.':
        a[si-1]=ci
    else:
        if a[si-1]==ci:
            continue
        else:
            ans=-1
            break

if ans==-1 or a[0]=='0':
    print(-1)
else:
    if a[0]=='.':
        a[0]=1
    for i in range(1,n):
        if a[i]=='.':
            a[i]='0'
    a=''.join(a)
    print(a)

### FIXED CODE ###

n,m=map(int,input().split())
a=['.']
a*=n
ans=0
for i in range(m):
    si,ci=input().split()
    si=int(si)
    ci=str(ci)
    if a[si-1]=='.':
        a[si-1]=ci
    else:
        if a[si-1]==ci:
            continue
        else:
            ans=-1
            break

if ans==-1 or (n>=2 and a[0]=='0'):
    print(-1)
else:
    if n==1 and a[0]=='.':
        a[0]='0'
    elif a[0]=='.':
        a[0]='1'
    for i in range(1,n):
        if a[i]=='.':
            a[i]='0'
    a=''.join(a)
    print(a)
N = int(input())
S =[input() for i in range(N+1)]

s = set(S)

print(len(s))

### FIXED CODE ###

N = int(input())
S =[input() for i in range(N)]

s = set(S)

print(len(s))
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = sorted(list(zip(b, a)))
 
a.sort()
b.sort()
for i in range(n):
  if a[i] > b[i]:
    print('No')
    exit()
    
fir, las = {}, {}
s = [0] * n
for i in range(n):
  fir[a[i]] = min(fir.get(a[i], n), i)
  las[a[i]] = max(fir.get(a[i], 0), i)
  if i > 0 and a[i] <= b[i - 1]:
    s[i] = 1
for i in range(1, n):
  s[i] += s[i - 1]
 
for i, (x, y) in enumerate(l):
  if x >= y:
    if y >= a[i] or s[fir[x]] - s[las[y]] == fir[x] - las[y]:
      print('Yes')
      exit()
 
print('No')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = list(zip(b, a))
 
a.sort()
b.sort()
for i in range(n):
  if a[i] > b[i]:
    print('No')
    exit()

ptr, pos = {}, {}
for i in range(n):
  if i > 0 and a[i] <= b[i - 1]:
    print('Yes')
    exit()
  ptr[l[i][1]] = l[i][0]
  pos[b[i]] = i

sta, now, cnt = a[0], a[0], 1
while True:
  now = a[pos[ptr[now]]]
  if now == sta:
    break
  cnt += 1
if cnt == n:
  print('No')
else:
  print('Yes')
n = int(input())
x_str = input().split()
xs = [int(c) for c in x_str]

xs_len = len(xs)
center = (xs_len - 1)//2

c_xs = xs[:]
c_xs.sort()

for x in xs:
    print(c_xs[center+1] if x <= c_xs[center] else c_xs[center])


### FIXED CODE ###


import numpy as np

n = int(input())
x_str = input().split()
xs = np.array([int(c) for c in x_str])

xs_len = len(xs)
center = (xs_len - 1)//2

c_xs = np.sort(xs)

for x in xs:
    if x <= c_xs[center]:
        print(c_xs[center+1])
    else:
        print(c_xs[center])
n, m = map(int, input().split())
p = list(map(int, input().split()))
uf = [i for i in range(n + 1)]

def dfs(x):
    if uf[x] == x:
        return x
    return dfs(uf[x])

for _ in range(m):
    xy = list(map(int, input().split()))
    rx, ry = dfs(xy[0]), dfs(xy[1])
    if rx != ry:
        uf[rx] = ry
count = 0
for i in range(n):
    num = i + 1
    if p[i] == num or dfs(num) == dfs(p[i]):
        count += 1
print(count)

### FIXED CODE ###

n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
mapp = [[] for _ in range(n + 1)]
for xy in xys:
    mapp[xy[0]].append(xy[1])
    mapp[xy[1]].append(xy[0])

bfs = [0] * (n + 1)
count = 0
for i in range(1, n + 1):
    nexts = mapp[i]
    if not(bfs[i]):
        bfs[i] = i
    for j in nexts:
        if bfs[j]:
            continue
        bfs[j] = i
        nexts += mapp[j]
    if bfs[i] == bfs[p[i - 1]]:
        count += 1
print(count)
def fib(n):
  if F[n] != 0:
    return F[n]
  elif n==0 or n==1:
    F[n] = 1
  else:
    F[n] = fib(n-1) + fib(n-2)

  return F[n]



n = input()
F = []*44
print fib(n)

### FIXED CODE ###

def fib(n):
  if F[n] != 0:
    return F[n]
  elif n==0 or n==1:
    F[n] = 1
  else:
    F[n] = fib(n-1) + fib(n-2)

  return F[n]



n = input()
F = [0 for row in range(n+1)]
print fib(n)
a, b, c, d, e, f = map(int, input().split())
max_concentration = 0
for i in range(0, f + 1, 100 * a):
    for j in range(0, f - i + 1, 100 * b):
        if i == 0 and j == 0:
            continue
        y = min((i + j) * e // 100, f - i - j)
        for k in range(0, y + 1, c):
            for l in range(0, y - k + 1, d):
                concentration = 100 * (k + l) // (i + j + k + l)
                if max_concentration < concentration:
                    max_concentration = concentration
                    res1 = i + j + k + l
                    res2 = k + l
print(str(res1) + ' ' + str(res2))


### FIXED CODE ###

a, b, c, d, e, f = map(int, input().split())
max_concentration = 0
for i in range(0, f + 1, 100 * a):
    for j in range(0, f - i + 1, 100 * b):
        if i == 0 and j == 0:
            continue
        y = min((i + j) * e // 100, f - i - j)
        for k in range(0, y + 1, c):
            for l in range(0, y - k + 1, d):
                concentration = 100 * (k + l) / (i + j + k + l)
                if max_concentration <= concentration:
                    max_concentration = concentration
                    res1 = i + j + k + l
                    res2 = k + l
print(str(res1) + ' ' + str(res2))
import numpy as np
from math import ceil
def powm(a,n,m):
    if n == 0:
        return np.eye(len(a))
    if n%2==0:
        return np.dot(powm(a,n//2,m),powm(a,n//2,m))%m
    else:
        return np.dot(np.dot(powm(a,n//2,m),powm(a,n//2,m)),a)%m

L,A,B,M = map(int,input().split())

C = [0]*18
d = 0
while True:
    C[d] = max(0,min(ceil((10**d-A)/B),L))
    if C[d] == L:
        break
    d += 1

for d in range(17,-1,-1):
    if C[d] != 0:
        C[d] -= C[d-1]

a = np.eye(3)
for d in range(1,18):
    a = np.dot(powm(np.array([[10**d%M,1,0],[0,1,B],[0,0,1]]),C[d],M),a)

ans = int(np.dot(a,np.array([0,A,1]))[0])%M

print(ans)

### FIXED CODE ###

def dot(a,b,m):
    c = [[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                c[i][j] += a[i][k]*b[k][j]
                c[i][j] %= m
    return c
    
def powm(a,n,m):
    if n == 0:
        return [[1,0,0],[0,1,0],[0,0,1]]
    for i in range(3):
        for j in range(3):
            a[i][j] %= m
    r = powm(a,n//2,m)
    if n%2==0:
        return dot(r,r,m)
    else:
        return dot(dot(r,r,m),a,m)

L,A,B,M = map(int,input().split())

a = [[1,0,0],[0,1,0],[0,0,1]]
for d in range(1,19):
    C = min(max(0,(10**d-A-1)//B+1),L)-min(max(0,(10**(d-1)-A-1)//B+1),L)
    a = dot(powm([[pow(10,d,M),1,0],[0,1,B%M],[0,0,1]],C,M),a,M)
ans = (a[0][1]*A%M+a[0][2])%M
print(ans)
from heapq import heapify, heappop

N, K = map(int, input().split())
vl = list(map(int, input().split()))
vr = list(reversed(vl))
sum_L = [0]
for vv in vl:
    sum_L.append(sum_L[-1] + vv)

sum_R = [0]
for vv in vr:
    sum_R.append(sum_R[-1] + vv)

ans = 0
for pick in range(K + 1):
    put = K - pick
    if pick < put: continue
    for left in range(pick + 1):
        right = pick - left

        t = sum_L[left] + sum_R[right]

        q = vl[:left] + vr[:right]
        heapify(q)

        cnt = 0
        while cnt < put and q:
            x = heappop(q)
            t -= x
            cnt += 1
        ans = max(ans, t)
print(ans)


### FIXED CODE ###

from heapq import heapify, heappop

N, K = map(int, input().split())
vl = list(map(int, input().split()))
vr = list(reversed(vl))
sum_L = [0]
for vv in vl:
    sum_L.append(sum_L[-1] + vv)

sum_R = [0]
for vv in vr:
    sum_R.append(sum_R[-1] + vv)

ans = 0
for pick in range(min(K, N) + 1):
    for to_remove in range(K + 1):
        if pick + to_remove > K: break
        for left in range(pick + 1):
            right = pick - left

            t = sum_L[left] + sum_R[right]

            q = vl[:left] + vr[:right]
            heapify(q)

            cnt = 0
            while cnt < to_remove and q:
                t -= heappop(q)
                cnt += 1
            ans = max(ans, t)
print(ans)
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>

using namespace std;


int main() {
    
    long n;
    long q;
    cin >> n;
    vector <long> s;
    vector <long> t;
    for (int i=0;i<n;i++){
        long p;
        cin >> p;
        s.push_back(p);
    }
    cin >> q;
    for(int i=0;i<q;i++){
        long p;
        cin >> p;
        t.push_back(p);
    }
    vector <long>::iterator idx;
    long ans = 0;
    for (int i=0;i<q;i++) {
        idx = lower_bound(s.begin(), s.end(),t[i]);
        if(*idx == t[i]){
            ans += 1;
        }
    }
    cout << ans << endl;
}


### FIXED CODE ###

def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return "NOT_FOUND"

n = int(input())
list_s = list((map(int, input().split())))
q = int(input())
list_t = list((map(int, input().split())))
ans = 0
for numbert in list_t:
    if binarySearch(list_s,numbert) != "NOT_FOUND":
        ans += 1
    
print(ans)
c=[]
for i in range(3):
    ci=input()
    a.append(ci)
print(c[0][0]+c[1][1]+c[2][2])

### FIXED CODE ###

c=[]
for i in range(3):
    ci=input()
    c.append(ci)
print(c[0][0]+c[1][1]+c[2][2])
import sys

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

for i in range(N+1):
    if Y < i * 10000:
        continue
    for j in range(N+1):
        if N == i + j + k and Y == i * 10000 + j * 5000 + k * 1000:
            print(i,j,k)
            sys.exit()
print("-1 -1 -1")


### FIXED CODE ###

import sys

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

for i in range(N+1):
    for j in range(N+1):
        k = N - i - j

        if k >= 0 and Y == i * 10000 + j * 5000 + k * 1000:
            print(i,j,k)
            sys.exit()
print("-1 -1 -1")
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p={(x,y)}
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    l[wx][wy]=1
    p.add((wx,wy))
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":

            p.add((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) ):
                global ans
                ans=1
dfs(x,y,0)

for g,j in p:
    if ans!=min(ans,-((-min(g,w-j-1,h-g-1,j))//k)+1):
        ans=(-((-min(g,w-j-1,h-g-1,j))//k)+1)

print(ans)

### FIXED CODE ###


h,w,k=map(int,input().split())
maze=[]

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
ans=float("INF")
l=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p={(x,y)}
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.add((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

for x,y in p:
    ans=min(ans,(min(x,y,h-1-x,w-1-y)+k-1)//k+1)
print(ans)