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

from math import sqrt
from fractions import gcd
from collections import defaultdict
from copy import deepcopy

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

def f(n):
    d = defaultdict(int)
    if n % 2 == 0:
        r = 0
        while n % 2 == 0:
            n //= 2
            r += 1
        d[2] = r
    for i in range(3,int(sqrt(n))+1):
        if n % i == 0:
            s = 0
            while n % i == 0:
                n //= i
                s += 1
            d[i] = s
    if n != 1:
        d[n] = 1
    return d

B = []
for i in range(N):
    B.append(f(A[i]))

lp = deepcopy(B[0])

for i in range(N-1):
    for j in list(set(B[i+1].keys()) | set(lp.keys())):
        lp[j] = max(B[i+1][j],lp[j])

ans = 0

for i in range(N):
    r = 1
    for j in list(lp.keys()):
        r = (r*pow(j,lp[j]-B[i][j],mod)) % mod
    ans = (ans + r) % mod

print(ans)

### FIXED CODE ###

def main():
    from math import sqrt
    from fractions import gcd
    from collections import defaultdict
    from copy import deepcopy

    N = int(input())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    p = [1] * (1001)
    P = []  # 1000までの素数表
    p[0] = p[1] = 0
    for x in range(2, int(sqrt(1000000)) + 1):
        if p[x]:
            P.append(x)
            for y in range(x * x, 1001, x):
                p[y] = 0

    B = [defaultdict(int) for i in range(N)]  # N個の数を素因数分解したもの
    lcm = defaultdict(int)  # N個の数のlcmを素因数分解したもの

    for i in range(N):
        for j in P:
            if A[i] % j == 0:
                while A[i] % j == 0:
                    A[i] //= j
                    B[i][j] += 1
            lcm[j] = max(lcm[j], B[i][j])
        if A[i] != 1:
            B[i][A[i]] = 1
            lcm[A[i]] = 1

    l = 1  # N個の数のlcm
    for i in lcm.keys():
        l = (l * pow(i, lcm[i], mod)) % mod

    ans = 0
    # l/A[i]の和を求めていく
    for i in range(N):
        r = l
        for j in list(B[i].keys()):
            r = (r * pow(j, mod - B[i][j] - 1, mod)) % mod
        ans = (ans + r) % mod

    print(ans)

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

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        #if b1<b0:
        #    b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        #if b2<b1:
        #    b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)

    ANS+=str(count%2)

print(int(ANS[::-1],2))


### FIXED CODE ###

import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)

    ANS+=str(count%2)

print(int(ANS[::-1],2))
### BUGGY CODE ###

n = int(input())
a_lst = list(map(int, input().split()))
ans = []
for i in range(1,n+1):
    ans.append(str(a_lst.index(i)+1))
print(' '.join(ans))

### FIXED CODE ###

n = int(input())
a_lst = list(map(int, input().split()))
lst = []
for i,a in enumerate(a_lst):
    lst.append([i+1,a])
ans = []
for l in sorted(lst, key=lambda x:x[1]):
    ans.append(l[0])
print(' '.join(map(str,ans)))
### BUGGY CODE ###

import heapq
import sys
input=sys.stdin.readline
from copy import deepcopy
from collections import defaultdict
h, w, d = map(int, input().split())
p = dict()
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (x, i, j)
        heapq.heappush(D[x%d], (x, i, j))

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    v = deepcopy(D[a%d])
    ans = 0
    while v:
        x, i, j = heapq.heappop(v)
        if x == a:
            s, t = i, j
        if a <= x <= b:
            ans += abs(s-i)+abs(t-j)
            s, t = i, j
            if x == b:
                break
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [0]*(h*w+1)
for i in range(h*w+1):
    if d < i:
        dp[i] = dp[i-d] + abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[b]-dp[a]
    print(ans)
### BUGGY CODE ###

N = input()
counter = 0

for i in range(1, int(N)+1):
  if 357<= i and i <= 777777753:
    a = str(i)
    if '7' in a and a != '':
      a = a.replace('7', '')
      if '3' in a and a != '':
        a = a.replace('3', '')
        if a != '':
          a = a.replace('5', '')
          if a == '':
            counter += 1
print(counter)

### FIXED CODE ###

N = int(input())
 
def dfs(s):
  if int(s) > N: 
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
 
print(dfs('0'))
### BUGGY CODE ###

import copy 
n = int(input())
        
a = [int(input()) for _ in range(n)]
        
for i in range(n):
  temp = copy.deepcopy(a)
  temp[i] = 0
  print(max(temp))

### FIXED CODE ###

n = int(input())
        
a = [(int(input()), i) for i in range(n)]
a.sort()
max_, max_index = a[-1]

for i in range(n):
  if i != max_index:
  	print(max_)
  else:
  	print(a[-2][0])
### BUGGY CODE ###

import bisect

n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))

index = [-1, -1, pi[n - 1][1], n, n]
ret = 0
for pos in range(n - 2, -1, -1):
    p, i = pi[pos]
    ii = bisect.bisect_left(index, i)
    ret += p * (index[ii - 1] - index[ii - 2]) * (index[ii] - i)
    ret += p * (i - index[ii - 1]) * (index[ii + 1] - index[ii])
    bisect.insort_left(index, i)
print(ret)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
pi = sorted(zip(p, range(n)))
left  = {i: i - 1 for i in range(n)}
right = {i: i + 1 for i in range(n)}
left[-1] = -1
right[n] = n

ret = 0
for p, i in pi:
    ret += p * (left[i] - left[left[i]]) * (right[i] - i)
    ret += p * (i - left[i]) * (right[right[i]] - right[i])
    l, r = left[i], right[i]
    right[l] = r
    left[r] = l
print(ret)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
from collections import Counter
MOD = 2019

def main():
    S = readline().rstrip()
    N = len(S)
    T = [0] * (N+1)
    for i in range(N-1, -1, -1):
        T[i] = T[i+1] + int(S[i]) * 10 ** (N-1-i)
    
    T = [t % MOD for t in T]
    c = Counter(T)
    ans = 0
    for k, v in c.items():
        ans += (v * (v-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
from collections import Counter
MOD = 2019

def main():
    S = list(map(int, list(readline().rstrip())))
    N = len(S)
    T = [0] * (N+1)
    e = 1
    for i in range(N-1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * e) % MOD
        e = e * 10 % MOD
    
    T = [t % MOD for t in T]
    c = Counter(T)
    ans = 0
    for k, v in c.items():
        ans += (v * (v-1)) // 2
    print(ans)


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

from itertools import permutations
N, M, X = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(N)]
P = permutations(books, len(books))
ans = 10 ** 9 + 1
for items in P:
    price = 0
    chk = [0] * M
    for p in items:
        price += p[0]
        for i, item in enumerate(p[1:]):
            chk[i] += item
        if all(c >= X for c in chk):
            ans = min(ans, price)
            break

if ans == 10 ** 9 + 1:
    ans = -1
print(ans)

### FIXED CODE ###

from itertools import combinations
N, M, X = map(int, input().split())
books = []
for _ in range(N):
    books.append(list(map(int, input().split())))
P = []
for i in range(1, N+1):
    for item in list(combinations(books, i)):
        P.append(item)
ans = 10 ** 9 + 1
for items in P:
    price = 0
    chk = [0] * M
    for p in items:
        price += p[0]
        for i, item in enumerate(p[1:]):
            chk[i] += item
        if all(c >= X for c in chk):
            ans = min(ans, price)
            break
if ans == 10 ** 9 + 1:
    ans = -1
print(ans)
### BUGGY CODE ###

def main():
    a = int(input())
    b = list(map(int, input().split()))
    for i in range(1,a+1):
        n = 0
        for j in b:
            if i == j:
                n = n + 1
        print(n)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    a = int(input())
    b = list(map(int, input().split()))
    c = [0]*a
    for i in b:
        c[i-1] += 1
    for j in c:
        print(j)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())

a=[]
for i in range(n):
    a.append(int(input()))

for i in range(n):
    print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n=int(input())

a=[]
for i in range(n):
    a.append(int(input()))

a_max=max(a)
a_max_cnt=a.count(a_max)

for i in range(n):
    if (a[i]!=a_max or a_max_cnt>1):
        print(a_max)
    else:
        print(max(a[:i]+a[i+1:]))
### BUGGY CODE ###

# 非負の整数a, b(a ≤ b)と 、 正の整数xが与えられます 。
# a以上b以下の整数のうち 、 xで割り切れるものの個数を求めてください 。
a, b, x = [int(i) for i in input().split()]

cou = 0
for i in range(a, b + 1):
    if i % x == 0:
        cou += 1

print(cou)


### FIXED CODE ###

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

def ret(n):
    if n>=0:
        return n//x+1
    else:
        return 0
print(ret(b)-ret(a-1))
### BUGGY CODE ###

# C
import numpy as np
n, q = map(int, input().split())
s = str(input())
s_flag = [0] * n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        s_flag[i] = 1
s_flag = np.array(s_flag)
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = np.sum(s_flag[l:r+1])
    if s_flag[r:r+1] == 1:
        ans -=1
    print(ans)

### FIXED CODE ###

# C
n, q = map(int, input().split())
s = str(input())
s_flag = [0] * n
v = 0
for i in range(n-1):
    if s[i:i+2] == 'AC':
        v += 1
    s_flag[i+1] = v

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = s_flag[r] - s_flag[l]
    print(ans)
### BUGGY CODE ###

# Q2
H, W = map(int, input().split())
a = [[c for c in input()] for _h in range(H)]

compressed = True
while compressed:
    compressed = False
    for h in range(H):
        if '#' not in a[h]:
            for w in range(W):
                a[h][w] = ''
                compressed = True
    for w in range(W):
        if '#' not in [p[w] for p in a]:
            for h in range(H):
                a[h][w] = ''
                compressed = True

for h in range(H):
    line = ''.join(a[h])
    if line:
        print(''.join(a[h]))

### FIXED CODE ###

# Q2
H, W = map(int, input().split())
a = [[c for c in input()] for _h in range(H)]


for h in range(H):
    if '#' not in a[h]:
        for w in range(W):
            a[h][w] = ''
for w in range(W):
    if '#' not in [p[w] for p in a]:
        for h in range(H):
            a[h][w] = ''

for h in range(H):
    line = ''.join(a[h])
    if line:
        print(''.join(a[h]))
### BUGGY CODE ###

n, m, q = map(int, input().split())
edges = [[0]*n for _ in range(n)]

for _ in range(m):
    L, R = map(lambda x: int(x)-1, input().split())
    edges[L][R] += 1


for _ in range(q):
    p, q = map(int, input().split())
    lines = edges[p-1:q]
    print(sum(sum(row[p-1:q]) for row in lines))

### FIXED CODE ###

n, m, q = map(int, input().split())
edges = [[0]*n for _ in range(n)]

for _ in range(m):
    L, R = map(lambda x: int(x)-1, input().split())
    edges[L][R] += 1


S = [[0]*(n+1)for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        S[i][j+1] = S[i][j] + edges[i][j]

for _ in range(q):
    p, q = map(int, input().split())
    lines = S[p-1:q]
    ans = 0
    for row in lines:
        ans += row[q]-row[p-1]
    print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(50000)
N,K= [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]

visited = [True for _ in range(N)]
cycle = []


ans = -float('inf')
for sn in range (N):
    cost = []
    nn = sn
    while True:
        cost.append(C[nn])
        nn = P[nn]
        if sn == nn:
            break
    total = sum(cost)
    l = len(cost)

    t = 0
    for i in range(l):
        t += cost[i]
        if i+1 > K: break
        now = t
        if total > 0:
            e = (K-i-1)//l
            now += total * e
        ans = max(ans,now)


print(int(ans))


### FIXED CODE ###

import sys

sys.setrecursionlimit(50000)
N,K= [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]

visited = [True for _ in range(N)]
cycle = []


ans = -float('inf')
for sn in range (N):
    cost = []
    nn = sn
    while True:
        cost.append(C[nn])
        nn = P[nn]
        if sn == nn:
            break
    total = sum(cost)
    l = len(cost)

    t = 0
    for i in range(l):
        t += cost[i]
        if i+1 > K: break
        now = t
        if total > 0:
            e = (K-i-1)//l
            now += total * e
        ans = max(ans,now)


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

n=int(input())
a=[0]*n
def int1(x):
  return int(x)-1
a[:]=map(int1,input().split())
#print(a)
import numpy as np
l=np.argsort(a)
#print(l)
del a[0:l[0]]
r=0
for ii in range(n):
  if ii in a:
    del a[0:a.index(ii)]
    r+=1
    #print(a,r)
  else:
    #print(a)
    if r==0:
      print(-1)
    else:
      print(n-r)
    exit()
print(n-r)

### FIXED CODE ###

n=int(input())
a=[0]*n
def int1(x):
  return int(x)-1
a[:]=map(int1,input().split())

r=0
#j0=0
#import numpy as np
ii=0
for jj in range(n):
  if a[jj]==ii:
    r+=1
    ii+=1
if r==0:
  print(-1)
  exit()

print(n-r)
### BUGGY CODE ###

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

ans = 1#np.prod(A)
for i in A:
  ans = ans * i
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

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

if A.count(0) > 0:
  print(0)
else:
  ans = 1
  for i in A:
    ans = ans * i
    if ans > 10 ** 18:
      ans = -1
      break
  
  print(ans)
### BUGGY CODE ###

k = int(input())
from fractions import gcd

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        x=gcd(i+1,j+1)
        ans+=6*gcd(i+1,j+1)
        for l in range(j+1, k):
            ans+=6*gcd(x,l+1)
print(ans)


### FIXED CODE ###

k = int(input())
from fractions import gcd

ans=0
for i in range(k):
    ans+=i+1
    for j in range(i+1, k):
        x=gcd(i+1,j+1)
        ans+=6*gcd(i+1,j+1)
        for l in range(j+1, k):
            ans+=6*gcd(x,l+1)
print(ans)
### BUGGY CODE ###

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

for i in range(n):
    ans *= a[i]
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a.sort()
if a[0] == 0:
    ans = 0
    print(ans)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()

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

def main():
    A, B, K = map(int, input().split())
    count = 0
    for i in range(A, B+1):
        if count < K or  (B-A)-K < count:        
            print(i)
        count += 1
main()

### FIXED CODE ###

def main():
    A, B, K = map(int, input().split())
    if 2*K > B - A:
        for j in range(A, B + 1):
            print(j)
    else:
        for i in range(A, A + K):
            print(i)
        for j in range(B-(K-1), B + 1):
            print(j)
main()
### BUGGY CODE ###

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

hyoten = 1

for idx, a in enumerate(A):
    if idx < K:
        hyoten *= a
    else:
        next_hyoten = hyoten * a / A[idx - K]
        if next_hyoten <= hyoten:
            print('No')
        else:
            print('Yes')
        hyoten = next_hyoten

### FIXED CODE ###

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

for idx, a in enumerate(A):
    if idx < K:
        continue
    else:
        if a <= A[idx - K]:
            print('No')
        else:
            print('Yes')
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
s = list(input())
q = int(input())
ql = [input().split() for _ in range(q)]

w = 800
sl = []
dl = []
for i in range((n+w-1)//w):
    ss = s[i*w:min((i+1)*w,n)]
    dl.append(set(ss))
    sl.append(ss)

for i in range(q):
    if ql[i][0]=="1":
        idx = int(ql[i][1])-1
        c = ql[i][2]

        ss = sl[idx//w]
        ss[idx%w] = c
        s[idx] = c
        sl[idx//w] = ss
        dl[idx//w] = set(ss)
    else:
        l = int(ql[i][1])-1
        r = int(ql[i][2])-1

        li = l//w
        ri = r//w
        if abs(li-ri)<2:
            print(len(set(s[l:r+1])))
        else:
            u = set()
            u = u | set(sl[li][l%w:])
            for j in range(li+1,ri):
                u = u | dl[j]
            u = u | set(sl[ri][:r%w+1])
            print(len(u))


### FIXED CODE ###


class SegTree(object):
    """docstring for SegTree."""
    def __init__(self, l, _n):
        n = 1
        while n<_n:
            n *= 2
        self.n = n
        self.dat = [0 for _ in range(2*n)]
        for i in range(_n):
            self.dat[i+n-1] |= 1<<l[i]
        self.init(0)

    def init(self, i):
        if i>=self.n-1:
            return self.dat[i]
        self.dat[i] = self.init(self.left(i)) | self.init(self.right(i))
        return self.dat[i]

    def par(self, i):
        return (i-1)//2

    def left(self, i):
        return 2*i+1

    def right(self, i):
        return 2*i+2

    def update(self, i, x):
        i += self.n-1
        self.dat[i] = 1<<x
        while i>0:
            i = self.par(i)
            self.dat[i] = self.dat[self.left(i)] | self.dat[self.right(i)]

    def q(self,a,b,k,l,r):
        if r<=a or b<=l:
            return 0
        if a<=l and r<=b:
            return self.dat[k]
        return self.q(a,b,self.left(k),l,(l+r)//2) | self.q(a,b,self.right(k),(l+r)//2,r)

    def query(self,a,b):
        return self.q(a,b,0,0,self.n)

n = int(input())
s = [ord(c)-ord("a") for c in input()]
q = int(input())
ql = [input().split() for _ in range(q)]

seg = SegTree(s,n)

for i in range(q):
    if ql[i][0]=="1":
        seg.update(int(ql[i][1])-1, ord(ql[i][2])-ord("a"))
    else:
        r = seg.query(int(ql[i][1])-1, int(ql[i][2]))
        print(bin(r).count("1"))
### BUGGY CODE ###

import sys
from itertools import permutations

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(')
    r = x.count(')')
    if l != r: return 0

    return 1

def main():
    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

if __name__ == '__main__':
    readline = sys.stdin.readline

    n = int(readline())
    s = [readline().strip() for i in range(n)]

    comb_s = list(permutations(s))

    main()


### FIXED CODE ###

from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    plus, minus = [], []
    for c in s:
        if 2 * c.count('(') - len(c) > 0:
            plus.append(c)
        else:
            minus.append(c)

    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)
    sum = 0
    for v in plus:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

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

N = int(input())
S = list(input())

if '#' not in S:
    ans = 0
else:
    ans = 2*10**5
    for i in range(N):
        if S[i] == '#':
            ans = min(S[:i].count('#') + S[i:].count('.'), ans)

print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())

white = S.count('.')
black = 0
ans = white + black

for x in S:
    if x == '.':
        white -= 1
    else:
        black += 1
    ans = min(ans, white+black)

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

import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    path = []
    for _ in range(M):
        (A,B) = map(int, input().split())
        path += (A,B),

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びるパス
        pn = list(filter(lambda p: n in p, path))
        # nから伸びる行き先
        dests = list(map(lambda p: p[0] if p[0] != n else p[1], pn))
        # すでに道しるべがあるものは除く
        dests = list(filter(lambda d: not d in guide.keys(), dests))
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            # 探索候補の末尾に追加
            target += d,

    if set(range(1,N+1)) <= set(guide.keys()):
        print('Yes')
        for i in range(2,N+1):
            print(guide[i])
    else:
        print('No')

main()


### FIXED CODE ###

#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

    guide = [0 for _ in range(N+1)]

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor[n]
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: guide[d] == 0, dests)
        # 道しるべを置く
        for d in dests:
            guide[d] = n
            checked += d,
            # 探索候補の末尾に追加
            target += d,

    print('Yes')
    for i in range(2,N+1):
        print(guide[i])

main()
### BUGGY CODE ###

import numpy as np

s = input()

dp = np.zeros(shape=(len(s), 13), dtype=int)

# 初期値
digit = s[0]
ii = len(s) - 1
if digit == '?':
    for j in range(10):
        num = j * (10**ii)
        amari = num % 13
        dp[0][amari] += 1
else:
    num = int(digit) * (10**ii)
    amari = num % 13
    dp[0][amari] += 1

for i in range(1, len(s)):
    ii = len(s) - 1 - i
    digit = s[i]
    if digit == '?':
        for j in range(10):
            num = j * (10**ii)
            amari = num % 13
            for k in range(13):
                dp[i][k] += dp[i-1][k-amari]
                dp[i][k] = dp[i][k] % (10**9+7)
    else:
        num = int(digit) * (10**ii)
        amari = num % 13
        for k in range(13):
            dp[i][k] += dp[i-1][k-amari]
            dp[i][k] = dp[i][k] % (10**9+7)

print(dp[len(s)-1][5] % (10**9+7))

### FIXED CODE ###

s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = [[0 for j in range(13)] for i in range(n)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    num = int(s[0])
    dp[0][num] = 1

mul = 1
for i in range(1, n):
    mul = (mul*10) % 13
    if s[i] == '?':
        for m in range(10):
            num = (m * mul) % 13
            for j in range(13):
                dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod
    else:
        num = (int(s[i]) * mul) % 13
        for j in range(13):
            dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod

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