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

import sys
from collections import deque

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = deque([1])
n = gcd+1
for i in range(2, n):
    while True:
        if gcd%i ==0:
            L.append(i)
            gcd = gcd//i
        else:
            break
    if gcd < i:
        break
L = set(L)
print(len(L))

### FIXED CODE ###

import sys
import math

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = [1]
n = int(math.sqrt(gcd))
for i in range(2, n+1):
    while True:
        if gcd%i ==0:
            L.append(i)
            gcd = gcd//i
        else:
            break
if gcd>1:
    L.append(gcd)
L = set(L)
print(len(L))
### BUGGY CODE ###

import numpy as np

n = int(input())
aaa = list(map(int,input().split()))
aa=sorted(aaa)
a=np.array([[i,1] for i in aa])

for i in range(n-1):
    if a[i][1]==1:
        for j in range(i+1,n):
            wk1,wk0=divmod(a[j][0],a[i][0])
            if wk0==0:
                if wk1==1:
                    a[i][1]=0
                a[j][1]=0

print((np.sum(a,axis=0))[1])

### FIXED CODE ###

import numpy as np

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

amax=max(a)+1
ah=[0]*amax

for i in a:
    for j in range(i,amax,i):
        ah[j]+=1

an=0
for i in a:
    if ah[i]==1:
        an+=1
print(an)
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = list(map(int,input().split()))

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

a_c = Counter(A)
for i in range(n):
    tmp = 0
    for k,v in a_c.items():
        if k==A[i]:
            v-=1
        if v>=2:
            tmp+=cmb(v,2)
    print(tmp)

### FIXED CODE ###

from collections import Counter
n = int(input())
a_input = list(map(int,input().split()))

a_count = Counter(a_input)

score_dic={}
exclude_dic={}

for k,v in a_count.items():
    score_dic[k]=v*(v-1)//2
    exclude_dic[k]=(v-1)*(v-2)//2

score_sum = sum(score_dic.values())

for i in range(n):
    print(score_sum-score_dic[a_input[i]]+exclude_dic[a_input[i]])
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
INF=float('inf')
dp=[INF]*N
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1,1):
        if i+j>N-1:
            break
        dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[N-1])


### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
INF=float('inf')
dp=[INF]*N
dp[0]=0
for i in range(N-1):
    for j in range(1,K+1,1):
        if i+j>N-1:
            break
        dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[N-1])
### BUGGY CODE ###

N=int(input())
D=list(map(int,input().split()))
ans=1
if D[0]!=0:
    print(0)
else:
    for i in range(max(D)-1):
        ans*=D.count(i+1)**D.count(i+2)
        ans%=998244353
    print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
 
from collections import Counter
q=Counter(d)

# 例外対応
if q[0]!=1 or d[0]!=0:
  print(0)
  exit()

ans = 1
for i in range(1,max(d)+1):
  ans *= q[i-1]**q[i]
  if ans == 0:
    break
print(ans%998244353)
### BUGGY CODE ###

import sys

N, X = map(int, input().split())
x = list(input().split())
city = [int(x[i]) for i in range(N)]
MAX = min([abs(city[i] - X) for i in range(N)])

for j in reversed(range(MAX)):
    tmp = [abs(X - city[i]) % (j+1) for i in range(N)]
    if max(tmp) == 0:
        print(j+1)
        sys.exit()

### FIXED CODE ###

import sys
import math

N, X = map(int, input().split())
x = list(input().split())
city = [abs(int(x[i]) - X) for i in range(N)]
MAX = min(city)
candidate = []
for i in range(int(math.sqrt(MAX)+1)):
    if MAX % (i+1) == 0:
        candidate.append(i+1)
        candidate.append(MAX // (i+1))

candidate = list(sorted(candidate, reverse=True))

for j in range(len(candidate)):
    ans = candidate[j]
    tmp = [city[i] % ans for i in range(N)]
    if max(tmp) == 0:
        print(ans)
        sys.exit()
### BUGGY CODE ###

N = int(input())
if N%2==0:
    a=N//2
    b=N
    c=N
    print(a,b,c)
else:
    for ai in range(N//4,3500):
        for bi in range(N//4,3500):
            try:
                ci = N*ai*bi/(4*ai*bi-N*ai-N*bi)
                if ci == int(ci) and ci > 0:
                    print(ai,bi,int(ci))
                    exit()
            except:
                continue


### FIXED CODE ###

N = int(input())
for ai in range(1,3500):
    for bi in range(1,3500):
        try:
            ci = N*ai*bi/(4*ai*bi-N*ai-N*bi)
        except:
            continue
        if ci == int(ci) and ci > 0:
            print(ai,bi,int(ci))
            exit()
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ BIT汎用版 """

    def __init__(self, n, func, init):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.func = func
        self.init = init
        self.tree = [init] * nv
    
    def query(self, i):
        """ [0, i]の値を取得 """
        s = self.init
        i += 1
        while i > 0:
            s = self.func(s, self.tree[i-1])
            i -= i & -i
        return s
    
    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] = self.func(self.tree[i-1], x)
            i += i & -i

N = INT()
H = LIST()
A = LIST()

bit = BIT(N+1, max, 0)
for h, a in zip(H, A):
    # ここより手前で出現した自分より低い花から、一番いいところを取る
    mx = bit.query(h)
    # 自身の最善の値を更新
    bit.update(h, mx + a)
ans = bit.query(N)
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BIT:
    """ BIT汎用版 """

    def __init__(self, n, func, init):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.func = func
        self.init = init
        self.tree = [init] * nv
    
    def query(self, i):
        """ [0, i]の値を取得 """
        s = self.init
        i += 1
        while i > 0:
            s = self.func(s, self.tree[i-1])
            i -= i & -i
        return s
    
    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] = self.func(self.tree[i-1], x)
            i += i & -i

N = INT()
H = LIST()
A = LIST()

bit = BIT(N+1, max, 0)
for h, a in zip(H, A):
    # ここより手前で出現した自分より低い花から、一番いいところを取る
    mx = bit.query(h)
    # 自身の最善の値を更新
    bit.update(h, mx + a)
ans = bit.query(N)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

    for i in range(H):
        st = list(input())
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j,0))

    answer = 0
    while queue:
        i,j,count = queue.popleft()

        if isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
                if 0<=i+ix<H and 0<=j+iy<W:
                    queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            if not isVisited[i][j]:
                isVisited[i][j] = True
                for ix,iy in a:
                    if 0<=i+ix<H and 0<=j+iy<W:
                        nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(max(answer-1,0))
    return

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

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


nr = 0
ng = 0
nb = 0

for i in range(0, n):
    if s[i] == 'R':
        nr += 1
    elif s[i] == 'G':
        ng += 1
    else:
        nb += 1

c = 0
for i in range(0, n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if j < k and k < n and s[i] != s[k] and s[j] != s[k]:
                c += 1

print(nr*ng*nb - c)


### FIXED CODE ###

from collections import defaultdict

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

rgb = {'R': 0, 'G': 0, 'B': 0}
for i in s:
    rgb[i] += 1

c = 0
for i in range(0, n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if j < k and k < n and s[i] != s[k] and s[j] != s[k]:
                c += 1

print(rgb['R']*rgb['G']*rgb['B'] - c)
### BUGGY CODE ###

n = int(input())
h_l = list(map(int,input().split()))
cnt = 0
for i in range(n):
    for j in range(i,n):
        if((j-i)==(h_l[j]+h_l[i])):
            cnt += 1

print(cnt)

### FIXED CODE ###

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

#Ai + i 
#j-Aj
ans = 0
cnt = [0]*(n+1)
for i in range(n-1):
    j=i+1
    a = mp[i]+i
    if(a<=n):
        cnt[a] += 1 
    b = j-mp[j]
    if(b<0):
        continue
    ans += cnt[b]
    

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

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
#初めから、どこに挿入されるのかを考えておく
A = {}
B = {}
C = {}
for i in range(n):
    B[c[i]] = min(bisect.bisect_left(b, c[i]), n)
    A[b[i]] = min(bisect.bisect_left(a, b[i]), n)
for i in range(n):
    Bindex = B[c[i]]
    for j in range(Bindex):
        Aindex = A[b[j]]
        ans +=  (Aindex)
print(ans)


### FIXED CODE ###

import bisect
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
#初めから、どこに挿入されるのかを考えておく
Bcount = [0 for i in range(n+1)]
for i in range(1,n+1):
    Bcount[i] = bisect.bisect_left(a, b[i-1]) + Bcount[i - 1]

for i in range(n):
    index = bisect.bisect_left(b,c[i])

    ans += Bcount[index]
print(ans)
### BUGGY CODE ###

""" nC3 のすべての組み合わせに対して、三角形が成立するかを調べると、O(n^3)で計算量がだめ
ソートしてから、maxの辺を固定する
他の２つのへんをfor loop *２で回すが、a >= b + c になった段階でbreakする
この時の計算量はo(n^3)だけど半分くらいに減るはず。
これでTLEするか試す
"""
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 0
for i in range(n-1,1,-1):
  for j in range(i-1,0,-1):
    for k in range(j-1,-1,-1):
      ans += 1
      if l[i] >= l[j] + l[k]:
        ans -= 1
        break
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input()[:-1])
li = list(map(int,input().split()))
li.sort()
ans = 0
for i in range(n-1,1,-1):
  for j in range(i-1,0,-1):
    l = 0
    r = j
    while r-l > 0:
      p = (r+l)//2
      if li[p] + li[j] > li[i]:
        r = p
      else:
        l = p + 1
    ans += j - r
print(ans)
### BUGGY CODE ###

h, w = map(int, raw_input().split())
S = [[0 if c == "." else 1 for c in raw_input()] for i in range(h)]
L = [[0]*w for i in range(h)]
R = [[0]*w for i in range(h)]
U = [[0]*w for i in range(h)]
D = [[0]*w for i in range(h)]

for i in xrange(h):
    ps = 0
    for j in xrange(w):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            L[i][j] = ps

for j in xrange(w):
    ps = 0
    for i in xrange(h):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            U[i][j] = ps

for i in xrange(h-1, -1, -1):
    ps = 0
    for j in xrange(w-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            R[i][j] = ps
for j in xrange(w-1, -1, -1):
    ps = 0
    for i in xrange(h-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            D[i][j] = ps
maxLight = 0
for i in xrange(h):
    for j in xrange(w):
        maxLight = max(maxLight, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print maxLight


### FIXED CODE ###

h, w = map(int, raw_input().split())
S = [[0 if c == "." else 1 for c in raw_input()] for i in range(h)]
L = [[0]*w for i in range(h)]
R = [[0]*w for i in range(h)]
U = [[0]*w for i in range(h)]
D = [[0]*w for i in range(h)]

for i in xrange(h):
    ps = 0
    for j in xrange(w):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            L[i][j] = ps

for j in xrange(w):
    ps = 0
    for i in xrange(h):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            U[i][j] = ps

for i in xrange(h-1, -1, -1):
    ps = 0
    for j in xrange(w-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            R[i][j] = ps
for j in xrange(w-1, -1, -1):
    ps = 0
    for i in xrange(h-1, -1, -1):
        if S[i][j] == 1:
            ps = 0
        else:
            ps += 1
            D[i][j] = ps
maxLight = 0
for i in xrange(h):
    for j in xrange(w):
        maxLight = max(maxLight, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print maxLight
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


C = np.bincount(A)
C.sort()


def solve(k):
    cnt = N // k
    if C[-1] <= cnt:
        # 全部取れるとしていい
        # 最後に2つ以上余ると max_c <= cnt に矛盾する
        return cnt

    S = N
    i = 1
    while i < k:
        # 最大値は毎回取ることにしてもう見ない
        S -= C[-i]
        cnt = S // (k - i)
        max_c = C[-i - 1]
        if max_c <= cnt:
            return cnt
        i += 1
    return 0


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = solve(k)
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    s = 0
    ret = []
    for a in it:
        s += a
        ret.append(s)
    return ret


C = [0] * (N + 1)
for a in A:
    C[a] += 1
C.sort()
cs = list(reversed(cumsum(reversed(C))))


def solve(k):
    cnt = N // k
    if C[-1] <= cnt:
        # 全部取れるとしていい
        # 最後に2つ以上余ると max_c <= cnt に矛盾する
        return cnt

    # S = N
    # i = 1
    # while i < k:
    #     # 最大値は毎回取ることにしてもう見ない
    #     S -= C[-i]
    #     cnt = S // (k - i)
    #     max_c = C[-i - 1]
    #     if max_c <= cnt:
    #         return cnt
    #     i += 1

    ng = 0
    ok = k
    while abs(ng - ok) > 1:
        i = (ng + ok) // 2
        s = N - cs[-i]
        cnt = s // (k - i)
        max_c = C[-i - 1]
        if max_c <= cnt:
            ok = i
        else:
            ng = i
    if ok < k:
        i = ok
        s = N - cs[-i]
        return s // (k - i)
    else:
        return 0


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = solve(k)
print(*ans, sep='\n')
### BUGGY CODE ###

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

for i in range(2**N):
  temp = list(format(i,"0"+str(N)+'b'))
  temp1 = list(map(int, temp))
  for k in range(1,N+1):
    if sum(temp1[k-1::k])%2 == A[k-1]:
        pass
    else:
        break
  else:
    print(sum(temp1))
    anslist = []
    for i in range(N):
        if temp1[i] == 1:
          anslist.append(i+1)
    if anslist == []:
      exit()
    else:
      print(*anslist)
      exit()

### FIXED CODE ###

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

temp = [0]*N
for i in range(N-1,-1,-1):
  for j in [0,1]:
    temp[i] = j
    if sum(temp[i::i+1])%2 == A[i]:
      break
  else:
    print(-1)
    exit()
print(sum(temp)) 
anslist = []
for i in range(N):
  if temp[i] == 1:
    anslist.append(i+1)
if anslist == []:
  exit()
else:
  print(*anslist)
  exit()
### BUGGY CODE ###

import copy
S=list(str(input()))
kae=copy.copy(S)
ans=0
while True:
  con=0
  S=[i for i in S if i!=-100]
  for i in range(len(S)-1):
    if int(S[i])+int(S[i+1])==1:
      S[i]=-100
      S[i+1]=-100
      ans+=2
      con+=1
  if con==0:
    break
print(ans)

### FIXED CODE ###

S=list(str(input()))
zero=S.count("0")
one=S.count("1")
if zero==0 or one==0:
  print(0)
else:
  print(min(zero,one)*2)
### BUGGY CODE ###

N = int(input())
line = list(map(int,input().split()))
a = 0
p = []
for i in line:
    p.append(i)
    m = min(p)
    if m >= i:
       a += 1

print(a)

### FIXED CODE ###

N = int(input())
line = list(map(int,input().split()))
a = 1
m = line[0]
for i in range(N-1):
    if m >= line[i]:
        m = line[i]

    if m >= line[i+1]:
       a += 1

print(a)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	s=input().rstrip().decode('utf-8')
	n=len(s)
	
	dp=[[0]*13 for _ in range(n+1)]
	dp[0][0]=1
	
	for i in range(1,n+1):
		now=s[i-1]
		if now=="?":
			for j in range(13):
				for k in range(10):
					dp[i][(10*j+k)%13]+=dp[i-1][j]
		else:
			k=int(now)
			for j in range(13):
				dp[i][(10*j+k)%13]+=dp[i-1][j]
		
		for j in range(13):
			dp[i][j]%=MOD
	
	print(dp[n][5])
	
	
	
	
if __name__ == '__main__':
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	s=input().rstrip().decode('utf-8')
	n=len(s)
	
	dp=[[0]*13 for _ in range(n+1)]
	dp[0][0]=1
	
	for i in range(1,n+1):
		now=s[i-1]
		if now=="?":
			for j in range(13):
				for k in range(10):
					dp[i][(10*j+k)%13]+=dp[i-1][j]
		else:
			k=int(now)
			for j in range(13):
				dp[i][(10*j+k)%13]+=dp[i-1][j]
		
		for j in range(13):
			dp[i][j]%=MOD
	
	print(dp[n][5])
	
	
	
	
if __name__ == '__main__':
	main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    b = a[0:i]+a[i+1:n]
    c = sorted(b)
    d = int(n/2 - 1)
    e = int(c[d])
    print(e)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
for i in range(n):
    if b[int(n/2)] <= a[i]:
        print(b[int(n/2)-1])
    else:
        print(b[int(n/2)])