Harryxun/stf_run huggingface dataset:
import re
n,m = map(int, input().split())
a = [input().strip() for i in range(n)]
b = [input().strip() for i in range(m)]

mc = n-m+1
tb = [[0]*mc]*mc
ans = False
for ai in range(0, mc):
  if(ans):
    break
  ind = [x.start() for x in re.finditer(b[0], a[ai])]
  for i in ind:
    if(ans):
      break
    for bi in range(1, mc):
      if(a[ai+bi][i:i+m] != b[bi]):
        break
      if(bi==mc-1):
        ans = True
if(ans):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import re
n,m = map(int, input().split())
a = [input().strip() for i in range(n)]
b = [input().strip() for i in range(m)]

mc = n-m+1
ans = False
for ai in range(0, mc):
  if(ans):
    break
  ind = [x.start() for x in re.finditer(b[0], a[ai])]
  if(m==1)and(len(ind)>0):
    ans=True
    break  
  for i in ind:
    if(ans):
      break
    for bi in range(1, m):
      if(a[ai+bi][i:i+m] != b[bi]):
        break
      if(bi==m-1):
        ans = True
        break
if(ans):
  print('Yes')
else:
  print('No')
N,K = map(int,input().split())
a = list(map(int,input().split())

d = []
for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      d.append(a[i]*a[j])
      
print(sorted(d)[K-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
a = np.array(input().split(),np.int64)
a = np.sort(a)
zero = a[a==0]
pos = a[a>0]
neg = a[a<0]

def f(x):
    count = 0
    c = x // pos
    count += np.searchsorted(a, c, side='right').sum()
    count += N*len(zero) if x >= 0 else 0
    c = -(-x // neg)
    count += (N - np.searchsorted(a, c, side='left')).sum()
    count -= a[a*a <= x].size
    count //= 2
    return count

right = 10**18
left = -10**18
while right-left>1:
    mid = (right + left)//2
    if f(mid)<K:
        left = mid
    else:
        right = mid
        
print(right)
k, s = map(int, input().split())
count = 0
for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z and z <= k
        count += 1
print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for X in range(K+1):
  for Y in range(K+1):
    Z = S - X - Y
    if 0 <= Z and Z <= K:
        count += 1
print(count)
n,x = map(int, input().split())
city = []
sub = []
city = list(map(int, input().split()))

for i in range(len(city)):
	sub.append(abs(x - city[i]))

def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, a%b)

p = gcd(sub[0], sub[1])
for i in range(2,len(sub)):
	ans = gcd(p,sub[i])
	p = ans

print(p)

### FIXED CODE ###

n,x = map(int, input().split())
city = []
sub = []
city = list(map(int, input().split()))

for i in range(len(city)):
	sub.append(abs(x - city[i]))

def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, a%b)


if len(sub) == 1:
	print(sub[0])
elif len(sub) == 2:
	print(gcd(sub[0],sub[1]))
else:
	p = gcd(sub[0], sub[1])
	for i in range(2,len(sub)):
		p = gcd(p,sub[i])
	print(p)
def main():
     
    a,b,c,n = list(map(int,re.split(" ",input())))
    N = n
    s = []
    s.append(a)
    s.append(b)
    s.append(c)
    s.sort()
    a,b,c = s
    #print(a,b,c)
    ans = 0
    for i in range(int(N/c)+1):
        for j in range(int((N-i*c)/b)+1):
                if (N - i*c  - j*b)%a == 0:
                    ans += 1

    print(ans)
    
main()

### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    R, G, B, n = LI()
    ans = 0
    for r in range(n // R + 1):
        for g in range((n - r * R) // G + 1):
            b = (n - r * R - g * G) // B
            if r * R + g * G + b * B == n:
                
                ans += 1
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()
INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        while (True):
            update = False
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    update = True
            if not update:break
        return dist
    
    def findneg(self,V,E):
        dist = [0 for _ in range(V)]
        neg = [False for _ in range(V)]
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] == INF:continue
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    neg[v] = True
                    if i == V-1:return True
                if neg[u]:
                    neg[v] = True 
        return neg

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    neg = bf.findneg(N,E)
    if neg[-1]:
        print("inf")
    else:
        dist = bf.bellmanford(0,N,E)
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

INF = float('inf')
class BellmanFord:
    
    def bellmanford(self,s,V,E):
        dist = [INF for _ in range(V)]
        dist[s] = 0
        for i in range(V):
            for e in E:
                u,v,cost = e
                if dist[u] != INF and dist[v] > dist[u] + cost:
                    dist[v] = dist[u]+cost
                    if i == V-1 and v == V-1:
                        return -1
        return dist
    

def main():
    N,M = map(int,input().split())
    E = []
    for _ in range(M):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        E.append((a,b,-c))
    bf = BellmanFord()
    dist = bf.bellmanford(0,N,E)
    if dist == -1:
        print('inf')
    else:
        ans = dist[-1]
        print(-ans)

if __name__ == "__main__":
    main()
n=int(input())
s=input()
print(max(len(set(s[:i])&set(s[i:])) for i in range(1,n-1)))

### FIXED CODE ###

n=int(input())
s=input()
print(max(len(set(s[:i])&set(s[i:])) for i in range(1,n)))
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


a, b = [int(x) for x in input().split(' ')]

g = gcd(a, b)
ret: int = 1
i = 2
while i * i <= g:
    if g % i == 0:
        while g % i == 0:
            g /= i
        ret += 1
    i += 1

if g > 1:
    ret += 1

print(ret)

### FIXED CODE ###

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


a, b = [int(x) for x in input().split(' ')]

g = gcd(a, b)
ret = 1
i = 2
while i * i <= g:
    if g % i == 0:
        while g % i == 0:
            g /= i
        ret += 1
    i += 1

if g > 1:
    ret += 1

print(ret)
while True:
	a,b,e,d,e,f = map(float,raw_input().split())
	x = (e*c-b*f) / (e*a-b*d)
	y = (c*d-a*f) / (b*d-e*a)
	print '%d %d' % (x,y)

### FIXED CODE ###

while True:
	try:
		a,b,c,d,e,f = map(float,raw_input().split())
		x = (e*c-b*f) / (e*a-b*d)
		y = (c*d-a*f) / (b*d-e*a)
		if x == -0.0:
			x = 0
		if y == -0.0:
			y = 0
		print '%.3f %.3f' % (x,y)
	except EOFError:
		break
s=list(input())
t=list(input())
ans=[0 for _ in range(len(s))]
for i in range(len(s)-len(t)+1):
    cnt=0
    for j in range(len(t)):
        if s[i+j]=='?' or s[i+j]==t[j]:
            cnt+=1
    if cnt==len(t):
        ans[i]=i
mark=ans.index(max(ans))
if sum(ans)!=0:
    for j in range(len(s)):
        if mark<=j and j<=mark+len(t):
            s[j]=t[j-mark]
        elif s[j]=='?':
            s[j]='a'
    print(''.join(s))
else:print("UNRESTORABLE")

### FIXED CODE ###

s=list(input())
t=list(input())
ans=[0 for _ in range(len(s))]
for i in range(len(s)-len(t)+1):
    cnt=0
    for j in range(len(t)):
        if s[i+j]=='?' or s[i+j]==t[j]:
            cnt+=1
    if cnt==len(t):
        ans[i]=i+1
mark=ans.index(max(ans))
if sum(ans)!=0:
    for j in range(len(s)):
        if mark<=j and j<mark+len(t):
            s[j]=t[j-mark]
        elif s[j]=='?':
            s[j]='a'
    print(''.join(s))
else:print("UNRESTORABLE")
n = int(input())
a = list(map(int, input().split()))
b = [i+1 for i in range(n)]
c = list(zip(a, b))
c = sorted(c)
s = " ".join(map(lambda x: x[1], c))
print(s)
  

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [i+1 for i in range(n)]
c = list(zip(a, b))
c = sorted(c)
s = " ".join(map(lambda x: str(x[1]), c))
print(s)
S = input()
k = len(S)
win = 0
for i in range(k):
  if S[i] == 'o':
    win = win + 1
if win + 15 - k >= 8:
  print('YES')
else:
  print('NO)

### FIXED CODE ###

S = input()
k = len(S)
win = 0
for i in range(k):
    if S[i] == 'o':
        win = win + 1
if win + 15 - k >= 8:
    print('YES')
else:
    print('NO')
s=input()
print("Yes" if all((i%2==0 and s[i] in "RUD") or (i%!==0 and s[i] in "LUD)) else "No")

### FIXED CODE ###

s=input()
print("Yes" if all((i%2==0 and s[i] in "RUD") or (i%2!=0 and s[i] in "LUD") for i in range(len(s))) else "No")
from collections import*
import functools
import sys
input=sys.stdin.readline
@functools.lru_cache(maxsize=None)
def Knapsack(N,W):
    for i in range(N):
        w,v=map(int,input().split())
        for k,b in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],b+v)
    return max(d.values())
N,W=map(int,input().split())   #pypyで実行！
d=defaultdict(int)
d[0]=0
print(Knapsack(N,W))

### FIXED CODE ###

from collections import*
n,*h=map(int,open(0).read().split())
dp=defaultdict(int)

for i in range(1,n+1):
    dp[i]=float("inf")
dp[0]=0
for i in range(n):
    for j in range(1,3):
        if i+j<n:
            dp[i+j]=min(abs(h[i]-h[i+j])+dp[i],dp[i+j])
        else:
            break
print(dp[n-1])
N,R = map(int,input().split())
if N < 10 :
    print(100*(10-K))
else :
    print(K)

### FIXED CODE ###

N,R = map(int,input().split())
if N < 10 :
    print( R + 100*(10 - N) )
else :
    print( R )
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

m = sum([name[0] == 'M' for name in S])
a = sum([name[0] == 'A' for name in S])
r = sum([name[0] == 'R' for name in S])
c = sum([name[0] == 'C' for name in S])
h = sum([name[0] == 'H' for name in S])

print(m * (a * (r + c + h) + r * (c + h) + c * h) + a * (r * c + c * h) + r * c * h)


### FIXED CODE ###

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


N = int(input())

print(N//3)
def pcmod(n):
    if n==0:
        return 1
    return 1+pcmod(n%bin(n).count('1'))

def main():
    n = int(input())
    x = list(map(int,list(input())))

    m_1 = x.count(1)-1
    m_0 = x.count(1)+1 
    baser_1 = 0
    baser_0 = 0
    for i in range(n):
        baser_1 += x[i] * pow(2,(n-1-i),m_1)
        baser_0 += x[i] * pow(2,(n-1-i),m_0)
        baser_1 %= m_1
        baser_0 %= m_0

    ans = [0]*n

    for i in range(n):
        a = 0
        if x[i]==1:
            t = (baser_1 - pow(2,(n-1-i),m_1))%m_1
            a = pcmod(t)

        if x[i]==0:
            t = (baser_0 + pow(2,(n-1-i),m_0))%m_0
            a = pcmod(t)
        ans[i] = a

    for a in ans:
        print(a)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def pcmod(n):
    if n==0:
        return 1
    return 1+pcmod(n%bin(n).count('1'))

def main():
    n = int(input())
    x = list(map(int,list(input())))

    m_1 = x.count(1)-1
    m_0 = x.count(1)+1 
    baser_1 = 0
    baser_0 = 0
    if m_1!=0:
        for i in range(n):
            baser_1 += x[i] * pow(2,(n-1-i),m_1)
            baser_1 %= m_1
        
    for i in range(n):
        baser_0 += x[i] * pow(2,(n-1-i),m_0)
        baser_0 %= m_0

    ans = [0]*n

    for i in range(n):
        a = 0
        if x[i]==1:
            if m_1==0:
                ans[i] = 0
                continue
            t = (baser_1 - pow(2,(n-1-i),m_1))%m_1
            a = pcmod(t)

        if x[i]==0:
            t = (baser_0 + pow(2,(n-1-i),m_0))%m_0
            a = pcmod(t)
        ans[i] = a

    for a in ans:
        print(a)
if __name__ == "__main__":
    main()
s = input()

l=['K','I','H','B','R']
i=0
ans="YES"
for c in s:
	if c=="A":
		continue
	else:
		if c==l[i]:
			i+=1
		else:
			ans="NO"
			break
print(ans)


### FIXED CODE ###

s = input()

r = "AKIHABARA"
r2 = "KIHBR"
ans = "YES"
if not 5 <= len(s) <= len(r):
    ans = "NO"
if "AA" in s:
    ans = "NO"
if not "KIH" in s:
    ans = "NO"
else:
    rem_A = ""
    for c in s:
        if c != "A":
            rem_A += c
    if not rem_A == r2:
        ans = "NO"
print(ans)
H = int(input())
x = 2
for i in range(40):
  if x < H and x*2 > H:
    ans = x*2 - 1
    break
  x = x*2
    
print(ans)

### FIXED CODE ###

H = int(input())
x = 2
for i in range(41):
  if x <= H and x*2 > H:
    ans = x*2 - 1
    break
  x = x*2
  
if H == 1:
  ans = 1

print(ans)
n=int(input())
l=[0]
if n<200: print(l[100])
ans=chk=0
for i in range(n):
    a=int(input())
    ans+=(a+chk)//2
    if a>0:
         chk=(a+chk)%2
    else:
        chk=0
print(ans)

### FIXED CODE ###

n=int(input())
ans=chk=0
for i in range(n):
    a=int(input())
    ans+=(a+chk)//2
    if a>0:
         chk=(a+chk)%2
    else:
        chk=0
print(ans)
n,m=map(int,input().split())
a=list(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
if a[0]==1:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        dp[i]=0
    else:
        dp[i]=dp[i-1]+dp[i-2]
        dp[i] %= 1000000007
print(dp[n]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
#TLEの対策1. a in listと比べて a in setはめちゃんこ速い!!
a=set([int(input()) for _ in range(m)])

#TLEの対策2.配列ではなく変数を使う(対策1と比べると対して効果なし).
p,q=0,1

for i in range(1,n+1):
    #最新のp,q以前の値は捨てて良い.つまり配列を使用する必要なし.
    p,q=q,(p+q)%(10**9+7)*(not i in a) #n*Trueは1, n*Falseは0を表す.
print(q)
while True:
    n,w=map(int,raw_input().split())
    if n==w==0:break
    L=[0]*w
    for i in range(n):
        v=input()
        L[v/w]+=1
    maxh=max(L)
    r=n-1
    while r>0 and L[r]==0:
        r-=1
    ink=0.01
    for i in range(r+1):
        ink+=float(r-i)/r*float(L[i])/maxh
    print ink

### FIXED CODE ###

while True:
    n,w=map(int,raw_input().split())
    if n==w==0:break
    L=[0]*(w+1)
    for i in range(n):
        v=input()
        L[v/w]+=1
    maxh=max(L)
    r=w
    while r>0 and L[r]==0:
        r-=1
    ink=0.01
    for i in range(r+1):
        if r<>0:
            ink+=float(r-i)/r*float(L[i])/maxh
        else:
            ink+=L[i]
    print ink
a=input()
p=list(map(int,input().split()))
q=list(map(int,input().split()))
cost=0
for i in range(a):
    if p[i] - q[[i] > 0:
        cost += (p[i]-q[i])   
print(n)

### FIXED CODE ###

a=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
cost=0
for i in range(a):
    if p[i] - q[i] > 0:
        cost += (p[i]-q[i])   
print(cost)
#HATAGAYA
count = 0
c = []
S = list(input())
for i in range(len(S)):
  if S[i] == 'A' or S[i] == 'T' or S[i] == 'G' or S[i] == 'C':
    count += 1
  else:
    c.append(count)
    count = 0
print(max(c))

### FIXED CODE ###

count = 0
MAX = 0
S = list(input())
for i in range(len(S)):
  if S[i] == 'A' or S[i] == 'T' or S[i] == 'G' or S[i] == 'C':
    count += 1
    if MAX < count:
        MAX = count
  else:
    count = 0

print(MAX)
import math
       
def koch(n, px, py, qx, qy):
 if n == 0:
  return
        
 s.x = (px*2+qx)/3
 s.y = (py*2+qy)/3
 t.x = (px+qx*2)/3
 t.y = (py+qy*2)/3
 u.x = (t.x-s.x)*math.cos(math.pi/3) - (t.y-s.y)*math.sin(math.pi/3) + s.x
 u.y = (t.x-s.x)*math.sin(math.pi/3) + (t.y-s.y)*math.cos(math.pi/3) + s.y
       
 koch(n-1, px, py, s.x, s.y)
 print s.x, s.y
 koch(n-1, s.x, s.y, u.x, u.y)
 print u.x, u.y
 koch(n-1, u.x, u.y, t.x, t.y)
 print t.x, t.y
 koch(n-1, t.x, t.y, qx, qy)

n = input()
       
px = float(0)
py = float(0)
qx = float(100)
qy = float(0)
       
print px, py
koch(n, px, py, qx, qy)
print qx, qy

### FIXED CODE ###

import math
          
def koch(n, h, i, j, k):
 if n == 0:
  return
           
 sx = (h*2+j)/3
 sy = (i*2+k)/3
 tx = (h+j*2)/3
 ty = (i+k*2)/3
 ux = (tx-sx)*math.cos(math.pi/3) - (ty-sy)*math.sin(math.pi/3) + sx
 uy = (tx-sx)*math.sin(math.pi/3) + (ty-sy)*math.cos(math.pi/3) + sy
          
 koch(n-1, h, i, sx, sy)
 print sx, sy
 koch(n-1, sx, sy, ux, uy)
 print ux, uy
 koch(n-1, ux, uy, tx, ty)
 print tx, ty
 koch(n-1, tx, ty, j, k)
   
n = input()
          
px = float(0)
py = float(0)
qx = float(100)
qy = float(0)
          
print px, py
koch(n, px, py, qx, qy)
print qx, qy
n = int(input())
ans = [-1]*(n+1)
data =[[] for i in range(n+1)]

for i in range(n-1):
    u,v,w = map(int,input().split())
    data[u].append([v,w])
    data[v].append([u,w])

ans[1] = 1
def color(i):
    for v, w in data[i]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

color(1)
for i in range(n):
    print(ans[i+1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

n = int(input())
ans = [-1]*(n+1)
data =[[] for i in range(n+1)]

for i in range(n-1):
    u,v,w = map(int,input().split())
    data[u].append([v,w])
    data[v].append([u,w])

ans[1] = 1
def color(i):
    for v, w in data[i]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

color(1)
for i in range(n):
    print(ans[i+1])
A,B,C,D = map(int,input().split())
list1 = [A,B]
list2 = [C,D]
print(min(list1)+ min(list2))

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
D = int(input())
print(min(A,B)+ min(C,D))
import sys
sys.setrecursionlimit(10**7 + 10)

MOD = 10**9 + 7

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

visited = [False for i in range(n)]
def dfs(v, npv, nppv):
    global visited
    ans = max(k - npv - nppv, 0)
    visited[v] = True
    i = 0
    for nv in e[v]:
        if visited[nv]:
            continue

        ans *= dfs(nv, 1, npv+i)
        ans = ans % MOD
        i += 1

    return ans

for i in range(n):
    if len(e[i]) == 1:
        # print(i)
        s = i
        break

print(dfs(s, 0, 0))

# print(e)


### FIXED CODE ###

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

MOD = 10**9 + 7

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

if n == 1:
    print(k)
else:
    visited = [False for i in range(n)]
    def dfs(v, npv, nppv):
        global visited
        ans = max(k - npv - nppv, 0)
        visited[v] = True
        i = 0
        for nv in e[v]:
            if visited[nv]:
                continue

            ans *= dfs(nv, 1, npv+i)
            ans = ans % MOD
            i += 1

        return ans

    for i in range(n):
        if len(e[i]) == 1:
            # print(i)
            s = i
            break

    print(dfs(s, 0, 0))

    # print(e)
s = input()
k = int(input())
subs = []
for i in range(len(s)):
    for j in range(4):
        if s[i:i+j+1] not in subs:
            subs.append(s[i:i+j+1])
subs = sorted(subs)
print(subs[k-1])

### FIXED CODE ###

s = input()
k = int(input())
subs = []
for i in range(len(s)):
    for j in range(5):
        if s[i:i+j+1] not in subs:
            subs.append(s[i:i+j+1])
subs = sorted(subs)
# print(subs)
print(subs[k-1])
from collections import Counter
import bisect

N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [False]*(10**6+1)
for i in range(N):
    if c[A[i]] == 1:
        ok = True
        l = bisect.bisect_left(A, int(A[i]**0.5)+1)
        for j in range(l+1):
            if A[i] % A[j] == 0 and (d[A[j]] or d[A[i]//A[j]]):
                ok = False
                break
        if ok:
            ans += 1
    d[A[i]] = True

print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [0]*(10**6+1)
for i in range(N):
    if d[A[i]] == 0:
        if c[A[i]] == 1:
            ans += 1
        j = A[i]
        while j <= (10**6):
            d[j] += 1
            j += A[i]
print(ans)
s = input()

n_q = 0
n_c = 0
for i in range(len(s)):
    if s[i] == '?':
        n_q += 1
    elif s[i] == 'C':
        n_c += 1

n_q_right = [0]
n_a_right = [0]
n_c_right = [0]
for i in range(len(s) - 1):
    if s[i] == '?':
        n_q_right.append(n_q_right[-1] + 1)
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'A':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1] + 1)
        n_c_right.append(n_c_right[-1])
    elif s[i] == 'C':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1] + 1)
    elif s[i] == 'B':
        n_q_right.append(n_q_right[-1])
        n_a_right.append(n_a_right[-1])
        n_c_right.append(n_c_right[-1])

total = 0
Jp3 = 1/3.0
Lp3 = 3 ** (n_q - 1)
for i in range(len(s)):
    if s[i] == '?':
        Lp3 /= 3
        total1 = int((n_a_right[i] * 3 + n_q_right[i]) * Jp3)  %  (10 ** 9 + 7)
        total2 = int(((n_c - n_c_right[i]) * 3 + n_q - n_q_right[i] - 1) * Lp3)  %  (10 ** 9 + 7)
        total += total1 * total2
        Jp3 *= 3

    elif s[i] == 'B':
        total1 = int((n_a_right[i] * 3 + n_q_right[i]) * Jp3)  %  (10 ** 9 + 7)
        total2 = int(((n_c - n_c_right[i]) * 3 + n_q - n_q_right[i]) * Lp3)  %  (10 ** 9 + 7)
        total += total1 * total2

print(total % (10 ** 9 + 7))


### FIXED CODE ###

s = input()
a, d = [0], [0]
for char in s[:-1]:
    if char == 'A':
        a.append(a[-1] + 1)
    else:
        a.append(a[-1])
    if char == '?':
        d.append(d[-1] + 1)
    else:
        d.append(d[-1])

c, e = [0], [0]
for char in s[::-1][:-1]:
    if char == 'C':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1])
    if char == '?':
        e.append(e[-1] + 1)
    else:
        e.append(e[-1])
c = c[::-1]
e = e[::-1]

ret = 0
mod = 10 ** 9 + 7
for char, aa, dd, cc, ee in zip(s, a, d, c, e):
    if char in 'B?':
        tmp1 = aa * pow(3, dd, mod)
        if dd != 0:
            tmp1 += dd * pow(3, dd - 1, mod)

        tmp2 = cc * pow(3, ee, mod)
        if ee != 0:
            tmp2 += ee * pow(3, ee - 1, mod)

        ret += tmp1 * tmp2
        ret %= mod

print(ret)
import math
gcd = math.gcd()
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans += gcd(i,gcd(j,l))
print(ans)


### FIXED CODE ###

import math
gcd = math.gcd
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans += gcd(i,gcd(j,l))
print(ans)
n = int(input())
a =list(map(int,input().split()))
s =sum(a)
x = [0]*100001
for i in a:
    x[i] += 1

q = int(input())
for i in range(q):
    b,c = map(int(input().split()))
    s -= b*x[b]
    s += c*x[c]
    x[c] += x[b]
    x[b] = 0
    print(s)

### FIXED CODE ###

n = int(input())
a =list(map(int,input().split()))
s =sum(a)
x = [0]*1000001
for i in a:
    x[i] += 1

q = int(input())
for i in range(q):
    b,c = map(int,input().split())
    s -= b*x[b]
    s += c*x[b]
    x[c] += x[b]
    x[b] = 0
    print(s)