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

N,M,S=map(int,input().split())
UVAB=[list(map(int,input().split())) for i in range(M)]
C,D=zip(*[list(map(int,input().split())) for i in range(N)])
c=[[] for i in range(N)]
A=[[] for i in range(N)]
B=[[] for i in range(N)]
for u,v,a,b in UVAB:
    c[u-1].append(v-1)
    c[v-1].append(u-1)
    A[u-1].append(a)
    A[v-1].append(a)
    B[u-1].append(b)
    B[v-1].append(b)
inf=10**20
from heapq import heappop,heappush
X=50*(N-1)
def dij(p,s):
    d=[[inf]*(X+1) for i in range(N)]
    d[p][s]=0
    q=[]
    heappush(q,(0,(p,s)))
    while q:
        t,(p,s)=heappop(q)
        for i in range(1,(X+1-s)//C[p]):
            if X<s+i*C[p] or d[p][s+i*C[p]]<=d[p][s]+i*D[p]:break
            d[p][s+i*C[p]]=d[p][s]+i*D[p]
            heappush(q,(d[p][s]+i*D[p],(p,s+i*C[p])))
        for j,n in enumerate(c[p]):
            if 0<=s-A[p][j] and d[n][s-A[p][j]]>d[p][s]+B[p][j]:
                d[n][s-A[p][j]]=d[p][s]+B[p][j]
                heappush(q,(d[n][s-A[p][j]],(n,s-A[p][j])))
    return d
d=dij(0,min(S,X))
print(*[min(x) for x in d[1:]],sep='\n')

### FIXED CODE ###

N,M,S=map(int,input().split())
UVAB=[list(map(int,input().split())) for i in range(M)]
C,D=zip(*[list(map(int,input().split())) for i in range(N)])
c=[[] for i in range(N)]
A=[[] for i in range(N)]
B=[[] for i in range(N)]
for u,v,a,b in UVAB:
    c[u-1].append(v-1)
    c[v-1].append(u-1)
    A[u-1].append(a)
    A[v-1].append(a)
    B[u-1].append(b)
    B[v-1].append(b)
inf=10**20
from heapq import heappop,heappush
X=50*(N-1)
def dij(p,s):
    d=[[inf]*(X+1) for i in range(N)]
    d[p][s]=0
    q=[]
    heappush(q,(0,(p,s)))
    while q:
        t,(p,s)=heappop(q)
        for i in range(1,(X+1-s)//C[p]):
            if X<s+i*C[p] or d[p][s+i*C[p]]<=d[p][s]+i*D[p]:break
            d[p][s+i*C[p]]=d[p][s]+i*D[p]
            heappush(q,(d[p][s]+i*D[p],(p,s+i*C[p])))
        for j,n in enumerate(c[p]):
            if 0<=s-A[p][j] and d[n][s-A[p][j]]>d[p][s]+B[p][j]:
                d[n][s-A[p][j]]=d[p][s]+B[p][j]
                heappush(q,(d[n][s-A[p][j]],(n,s-A[p][j])))
    return d
d=dij(0,min(S,X))
print(*[min(x) for x in d[1:]],sep='\n')
### BUGGY CODE ###

#!/usr/bin/env python

import sys

line = sys.stdin.readline().strip()
n = int(line)
parts = sys.stdin.readline().strip().split()
nvals = map(int,parts)

line = sys.stdin.readline().strip()
m = int(line)
parts = sys.stdin.readline().strip().split()
mvals = map(int,parts)

for item in mvals:
    if item in nvals:
        nvals.remove(item)
    else:
        print "NO"
        sys.exit()

print "YES"

    

### FIXED CODE ###

#!/usr/bin/env python

import sys

line = sys.stdin.readline().strip()
n = int(line)
parts = sys.stdin.readline().strip().split()
nvals = map(int,parts)
nhash = {}

for item in nvals:
    if nhash.has_key(item):
        nhash[item] += 1
    else:
        nhash[item] = 1

line = sys.stdin.readline().strip()
m = int(line)
parts = sys.stdin.readline().strip().split()
mvals = map(int,parts)
mhash = {}

for item in mvals:
    if mhash.has_key(item):
        mhash[item] += 1
    else:
        mhash[item] = 1

for item in mhash.keys():
    if nhash.has_key(item) and mhash[item] <= nhash[item]:
        pass
    else:
        print "NO"
        sys.exit()

print "YES"
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]

A.sort()
used = [0]*N

import bisect

ans = 0
for i in range(N-1, -1, -1):
    if used[i] == 1:
        continue
    for j in range(32):
        if A[i] < pow(2, j) <= 2*A[i]:
            num = pow(2, j) - A[i]
            break
    idx = bisect.bisect_left(A, num)
    while idx < i and used[idx] == 1:
        idx += 1
    if A[idx] == num and idx < i:
        ans += 1
        used[idx] = 1
        used[i] = 1

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

dic = {}
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1
        
A.sort(reverse=True)
ans = 0
for a in A:
    if dic[a] == 0:
        continue
    dic[a] -= 1
    num = pow(2, len(bin(a))-2) - a
    if num in dic and dic[num] > 0:
        ans += 1
        dic[num] -= 1

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

from itertools import product
N = int(input())

alphabets = list('abcdefghijklmn')[:10]
for i in product(
        alphabets[:1],
        alphabets[:2],
        alphabets[:3],
        alphabets[:4],
        alphabets[:5],
        alphabets[:6],
        alphabets[:7],
        alphabets[:8],
        alphabets[:9],
        alphabets[:10],
):
    print(''.join(i))


### FIXED CODE ###

N = int(input())

alphabets = list('Zabcdefghijklmn')
s = ['a']
ss = []
for i in range(2, N + 1):
    subset = alphabets[1:i + 1]
    for j in range(len(s)):
        for k in subset:
            ss.append(s[j] + k)
            if s[j].find(k) == -1:
                break
    # print('s, ss', s, ss)
    s = ss
    ss = []
print(*s, sep='\n')
# for i in s:
#     print(i)
### BUGGY CODE ###

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

### FIXED CODE ###

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

s = input()
t = input()
num = set()

for i in range(len(s)):
    a, b = s[i], t[i]
    if a != b:
        s = s.replace(a, '-').replace(b, a).replace('-', b)
        
if s == t:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys
s = list(input())
t = list(input())
a = [-1 for _ in range(26)]
b = [-1 for _ in range(26)]

for i in range(len(s)):
    num0, num1 = a[ord(s[i])-97], b[ord(t[i])-97]
    if num0 >= 0:
        if chr(num0+97) != t[i]:
            print('No')
            sys.exit()
    else:
        a[ord(s[i])-97] = ord(t[i])-97
        
    if num1 >= 0:
        if chr(num1+97) != s[i]:
            print('No')
            sys.exit()
    else:
        b[ord(t[i])-97] = ord(s[i])-97
            
print('Yes')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

S = list(input())
S.pop()
length=len(S)
dp = [[0 for _ in range(13)] for _ in range(length+1)]
dp[0][0]=1
for i in range(length):
    for j in range(13):
        if S[length-i-1] == "?":
            for k in range(10):
                j_sub = j-k*10**i%13
                if j_sub < 0: j_sub+= 13
                dp[i+1][j]+=dp[i][j_sub]%1000000007
        else: 
            j_sub = j-int(S[length-i-1])*10**i%13
            if j_sub < 0: j_sub+= 13
            dp[i+1][j]+=dp[i][j_sub]%1000000007
print(dp[length][5]%1000000007)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10%13
    print(dp[5]%1000000007)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = list(input())
Q = int(input())
R = 1
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      S[len(S):] = (c)
    else:
      S = [c]+S
S = S if R==1 else reversed(S)
S = ''.join(S)
print(S)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
R = 1
Top = deque()
Top.append(S)
for _ in range(Q):
  inp = input()
  if inp[0]=='1':
    R *= -1
  else:
    o, f, c = inp.split()
    if f=='1' and R==-1 or f=='2' and R==1:
      Top.append(c)
    else:
      Top.appendleft(c)
S = ''.join(Top)
S = S if R==1 else S[::-1]
print(S)
### BUGGY CODE ###

from collections import deque
s=list(input())
s=deque(s)
q=int(input())
a=0
for i in range(q):
  A=list(input().split())
  if A[0]=="1":
    a=(a+1)%2
  else:
    if A[1]=="1":
      if a==0:
        s.appendleft(A[2])
      else:
        s.append(A[2])
    else:
      if a==0:
        s.append(A[2])
      else:
        s.appendleft(A[2])
if a==1:
  S=[]
  c=len(s)
  for i in range(c):
    S.append(s[c-i-1])
else:
  S=s
for i in range(len(S)):
  print(S[i],end="")
print()

### FIXED CODE ###

from collections import deque
s=list(input())
s=deque(s)
q=int(input())
a=0
for i in range(q):
  A=list(input().split())
  if A[0]=="1":
    a=(a+1)%2
  else:
    if A[1]=="1":
      if a==0:
        s.appendleft(A[2])
      else:
        s.append(A[2])
    else:
      if a==0:
        s.append(A[2])
      else:
        s.appendleft(A[2])
if a==1:
  S=[]
  c=len(s)
  for i in range(c):
    S.append(s[-1])
    s.pop()
else:
  S=s
for i in range(len(S)):
  print(S[i],end="")
print()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in A:
    ans = ans * i
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for i in A:
        ans = ans * i
        if ans > 10**18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, W: "List[int]", V: "List[int]"):
    dp = [[0 for i in range(M+1)] for j in range(N+1)]

    for i in range(1,N+1):
        w = W[i-1]
        v = V[i-1]
        for j in range(1,M+1):
            if j >= w:
                dp[i][j] = max(dp[i-1][j-w]+v,dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]

    print(dp[-1][-1])



    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

    for i in range(1,N+1):
        for j in range(W+1):
            dp[i][j] = dp[i-1][j]
            if j >= w[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1])
    print(dp[N][W])


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

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

# coding: utf-8

a = input()
q = int(input())

for i in range(q):
    q_list = [b for b in input().split()]
    if q_list[0] == '1':
        a = a[::-1]
    else:
        if q_list[1] == '1':
            a = q_list[2] + a
        else:
            a += q_list[2]
print(a)


### FIXED CODE ###

# coding: utf-8

a = input()
q = int(input())
mode = 1
L = ''
R = ''

for _ in range(q):
    q_list = input().split()

    if q_list[0] == '1':
        mode *= -1
    else:
        if q_list[1] == '1':
            if mode == 1:
                L += q_list[2]
            else:
                R += q_list[2]
        else:
            if mode == -1:
                L += q_list[2]
            else:
                R += q_list[2]
result = L[::-1] + a + R
if mode == -1:
    result = result[::-1]
print(result)
### BUGGY CODE ###

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

for i in range(N-1):
  for j in range(i+1,N):
    if A[i]+A[j] == abs(i-j):
      ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
from collections import defaultdict
I = defaultdict(int)
J = defaultdict(int)
ans = 0

for i in range(N):
  I[A[i]+i] += 1
  J[i-A[i]] += 1
for i,j in I.items():
  ans += J[i]*j
    
print(ans)
### BUGGY CODE ###

from itertools import accumulate


def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    ini = [0] * n
    fin = [n] * n
    for _ in range(k):
        b = ini.copy()
        for i, ai in enumerate(a):
            b[max(i - ai, 0)] += 1
            if i + ai + 1 < n:
                b[i + ai + 1] -= 1
        a = list(accumulate(b))
        if a == fin:
            print(*a)
            return
    print(*a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from itertools import accumulate


def main():
    n, k = map(int, input().split())
    a = [int(i) for i in input().split()]
    ini = [0] * n
    fin = [n] * n
    for c in range(min(k, 45)):
        b = ini.copy()
        for i, ai in enumerate(a):
            b[max(i - ai, 0)] += 1
            if i + ai + 1 < n:
                b[i + ai + 1] -= 1
        a = list(accumulate(b))
    print(*a)


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

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
check = [[] for i in range(N)]

for i in range(M):
    P[i], Y[i] = map(int, input().split())
    check[P[i]-1].append(Y[i])

for i in range(N):
    check[i].sort()

for i in range(M):
    print(('000000' + str(P[i]))[-6:] + ('000000' + str(check[P[i]-1].index(Y[i])+1))[-6:])




### FIXED CODE ###

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
X = [0] * M
check = [[] for i in range(N)]

for i in range(M):
    P[i], Y[i] = map(int, input().split())
    X[i] = [Y[i], P[i], i]

X.sort()
#print(X)

count = [0] * (N+1)
ans_list = [[] for _ in range(M)]

for i in range(len(X)):
    count[X[i][1]] += 1
    tmp = ('000000'+ str(X[i][1]))[-6:] + ('000000'+ str(count[X[i][1]]))[-6:]
    ans_list[X[i][2]] = tmp

for i in range(len(ans_list)):
    print(ans_list[i])
### BUGGY CODE ###

N=int(input())
r=[list(map(int, input().split())) + [set()] for _ in range(N)]
for _ in range(N):
	bx,by=map(int, input().split())
	for rx,ry,s in r:
		if bx>rx and by>ry:
			s.add(bx)
r=sorted(r, key=lambda x: len(x[2]))
def find(i, c, sel):
	if i == N:
		return c
	return max([find(i+1, c, sel)] + [find(i+1, c+1, sel | set([s])) for s in r[i][2] if s not in sel])
print(find(0, 0, set()))


### FIXED CODE ###

N=int(input())
r=sorted([list(map(int, input().split())) for _ in range(N)], key=lambda q: q[0], reverse=True)
b=sorted([list(map(int, input().split())) for _ in range(N)], key=lambda q: q[1])
ans=0
for rx,ry in r:
	for i in range(len(b)):
		bx,by=b[i]
		if bx>rx and by>ry:
			ans+=1
			b.pop(i)
			break
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

r, g, b = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
x, y, z = 0, 0, 0
for i in range(n):
    if s[i] == "R":
        x += 1
    elif s[i] == "G":
        y += 1
    else:
        z += 1
    r[i + 1] = x
    g[i + 1] = y
    b[i + 1] = z

cnt = 0
for i in range(n - 1):
    t = set(["R", "G", "B"])
    t -= set(s[i])
    for j in range(i + 1, n):
        a = 0
        tmp = t - set(s[j])
        if tmp == set("R"):
            a = r[n] - r[j + 1]
            if 2 * j - i < n:
                if s[2 * j - i] == "R":
                    a -= 1
        elif tmp == set("G"):
            a = g[n] - g[j + 1]
            if 2 * j - i < n:
                if s[2 * j - i] == "G":
                    a -= 1
        elif tmp == set("B"):
            a = b[n] - b[j + 1]
            if 2 * j - i < n:
                if s[2 * j - i] == "B":
                    a -= 1
        cnt += a
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

cnt = s.count("R") * s.count("G") * s.count("B")

for i in range(n - 1):
    tmp = s[i]
    for j in range(i + 1, (n + i + 1) // 2):
        if s[2 * j - i] != s[j] and s[j] != tmp and s[2 * j - i] != tmp:
            cnt -= 1
print(cnt)
### BUGGY CODE ###

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

dp = [[[0]*(50*(N+1)+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    for k in range(N):
        for s in range(50*N+1):
            dp[i+1][k][s] += dp[i][k][s]
            dp[i+1][k+1][s+X[i]] += dp[i][k][s]

ans = 0
for k in range(1, N+1):
    ans += dp[N][k][A*k]

print(ans)

### FIXED CODE ###

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

dp = [[[0]*(50*(N+1)+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(N):
    for k in range(N):
        for s in range(50*N+1):
            dp[i+1][k][s] += dp[i][k][s]
            dp[i+1][k+1][s+X[i]] += dp[i][k][s]

ans = 0
for k in range(1, N+1):
    ans += dp[N][k][A*k]

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

import sys
sys.setrecursionlimit(10**9)
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(N):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
count = 0
ans = []
bfs(0,G,queue,dist)
for v in range(1,N): 
    for el in G[v]: 
        if dist[v] == dist[el] + 1:
            ans.append(el+1)
            count += 1
            break
if count == N-1:
  print("Yes")
  for el in ans:
    print(el)
else:
  print("No")
    

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,m = map(int,input().split())
ee = [list(map(int,input().split())) for _ in range(m)]

cnt = 0
for p in range(m):
    e = ee[:p] + ee[p+1:]
    dist = [[float("inf")]*n for _ in range(n)]
    
    for i in range(m-1):
        s,t = e[i]
        dist[s-1][t-1]=1
        dist[t-1][s-1]=1

    for i in range(n):
        dist[i][i]=0
    #[print(*dist[l]) for l in range(n)]
    #print("-------------------------")

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float("inf") and dist[k][j] != float("inf"):
                   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    #[print(*dist[l]) for l in range(n)]
    #print("-------------------------")

    flag = True
    for i in range(n):
        if flag == False:
            break
        for j in range(n):
            if dist[i][j]==float("inf"):
                cnt += 1
                flag = False
                break
print(cnt)
 

### FIXED CODE ###

n,m = map(int,input().split())
ee = [list(map(int,input().split())) for _ in range(m)]

cnt = 0
for p in range(m):
    e = ee[:p] + ee[p+1:]
    dist = [[float("inf")]*n for _ in range(n)]
    
    for i in range(m-1):
        s,t = e[i]
        dist[s-1][t-1]=1
        dist[t-1][s-1]=1

    for i in range(n):
        dist[i][i]=0
    #[print(*dist[l]) for l in range(n)]
    #print("-------------------------")

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float("inf") and dist[k][j] != float("inf"):
                   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    #[print(*dist[l]) for l in range(n)]
    #print("-------------------------")

    flag = True
    for i in range(n):
        if flag == False:
            break
        for j in range(n):
            if dist[i][j]==float("inf"):
                cnt += 1
                flag = False
                break
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int

def combination(n: int, r:int, mod=MOD):
    n1 = n+1
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


def solve(N: int, M: int, K: int):
    ans = 0
    for k in range(K+1): 
        ans += combination(N-1,N-k-1) * M * pow(M-1, N-k-1, MOD) % MOD
        ans %= MOD
    
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 998244353  # type: int


MAX = 600000
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD
 
def combination(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD

def solve(N: int, M: int, K: int):
    ans = 0
    for k in range(K+1): 
        ans += combination(N-1,N-k-1) * M * pow(M-1, N-k-1, MOD) % MOD
        ans %= MOD
    
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

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

from collections import Counter

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

is_p=[1]*(10**6+1)
for i in a:
  if is_p[i]:
    for j in range(i+i,10**6+1,i):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i] and c[i]==1:
    cnt+=1

print(cnt)

### FIXED CODE ###

from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in set(a):
  v=i
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)