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

x, y, z, k = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans_list = []
for h in range(min(x,k)):
    for i in range(min(y,k-h)):
        for j in range(min(z,k-h-i)):
            ans_list.append(a[h]+b[i]+c[j])
ans_list.sort(reverse=True)
for i in range(k):
    print(ans_list[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
p = []
for i in a:
    for j in b:
        p.append(i+j)
p.sort(reverse=True)
p = p[:min(3001, x*y*z+1)]
q = []
for j in c:
    for i in p:
        q.append(i+j)
q.sort(reverse=True)
for i in range(k):
    print(q[i])
### BUGGY CODE ###

n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])
    
m = len(set(x))

import itertools

cnt = 0
for i in range(1,m+1):
    p = list(itertools.combinations(s,i))

    for pp in p:
        if len(pp) == len(set(pp)):
            cnt = cnt + 1

print(cnt)


### FIXED CODE ###


n = int(input())

s = input()

x = []

for i in range(n):
    x.append(s[i])

import collections

clist = collections.Counter(x)

y = list(clist.values())

cnt = 1

for item in y:
    cnt = cnt * (item + 1)

cnt = cnt - 1
cnt = cnt % (10 ** 9 + 7)
print(cnt)
### BUGGY CODE ###

import bisect
import numpy as np

def main():
    N = int(input())
    P = list(map(int, input().split()))

    P = np.array(P)

    ans = 0
    i = N
    while i != 0:
        ans += 1
        i = np.argmin(P)
        P = P[0:i]
    print(ans)

    return 0


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
import numpy as np

def main():
    N = int(input())
    P = list(map(int, input().split()))


    ans = 1
    f = P[0]

    for i in range(1, N):
        f_o = P[i]
        if f >= f_o:
            ans+=1
            f = f_o
    print(ans)
    return 0


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

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = [0] * (x * y)
for i in range(x):
  for j in range(y):
    D[i * y + j] = A[i] + B[j]
D.sort(reverse=True)
E = [0] * (z * k)
size = min(x * y, k)
for i in range(z):
  for j in range(size):
    E[i * size + j] = C[i] + D[j]
E.sort(reverse=True)
print(*E[:k], sep='\n')

### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = [0] * (x * y)
for i in range(x):
  for j in range(y):
    D[i * y + j] = A[i] + B[j]
D.sort(reverse=True)
E = [0] * (z * k)
size = min(x * y, k)
for i in range(z):
  for j in range(size):
    E[i * size + j] = C[i] + D[j]
E.sort(reverse=True)
print(*E[:k], sep='\n')
### BUGGY CODE ###

n, m, Q = map(int, input().split())

ts = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    l, r = tuple(map(int, input().split()))
    ts[l][r] += 1

from itertools import accumulate
tsa = [list(accumulate(t)) for t in ts]

for _ in range(Q):
    p, q = tuple(map(int, input().split()))
    c = 0
    for i in range(p, q+1):
        c += tsa[i][q] - tsa[i][p-1]
    print(c)

### FIXED CODE ###

n, m, Q = map(int, input().split())

ts = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    l, r = tuple(map(int, input().split()))
    ts[l][r] += 1
# 二次元累積和
for i in range(1, n+1):
    for j in range(1, n+1):
        ts[i][j] += ts[i][j-1]

for i in range(1, n+1):
    for j in range(1, n+1):
        ts[i][j] += ts[i-1][j]

for _ in range(Q):
    p, q = tuple(map(int, input().split()))
    print(ts[q][q] - ts[p-1][q] - ts[q][p-1] + ts[p-1][p-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def fennec(n, k):
    if n <= k:
        print("0")
    else:
        hp_list = list(map(int, input().split()))
        i = 1
        while i <= int(k): 
            del hp_list[hp_list.index(max(hp_list))]
            i += 1
        attack = sum(hp_list)
        print(attack)
        
        
n, k = map(int, input().split())
fennec(n, k)


### FIXED CODE ###

def fennec(n, k):
    if n <= k:
        print("0")
    else:
        hp_list = list(map(int, input().split()))
        hp_list.sort()
        attack = 0
        for i in range(int(n) - int(k)):
            attack += hp_list[i]
        print(attack)
        
        
n, k = map(int, input().split())
fennec(n, k)
### BUGGY CODE ###

n = int(input())
output = []
for i in range(n):
    li = input().split(' ')
    if(li[0] == 'insert'):
        output[0:0] = [int(li[1])]
        #output.insert(0, int(li[1]))
    elif(li[0] == 'delete'):
        if(int(li[1]) in output):
            output.remove(int(li[1]))
    elif(li[0] == 'deleteFirst'):
        del output[0]
    elif(li[0] == 'deleteLast'):
        del output[-1]
str_l = [str(o) for o in output]
print(' '.join(str_l))



### FIXED CODE ###

from collections import deque
n = int(input())
output = deque()
for i in range(n):
    li = input().split(' ')
    if(li[0] == 'insert'):
        output.appendleft(li[1])
    elif(li[0] == 'deleteFirst'):
        output.popleft()
    elif(li[0] == 'deleteLast'):
        output.pop()
    elif(li[0] == 'delete'):
        try:
            output.remove(li[1])
        except:
            pass
print(' '.join(output))
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
    if i<=a+k-1 or i>=b-k+1:
        print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
if k*2>(b-a+1):
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
### BUGGY CODE ###

n = int(input())
a = list(map(int ,input().split()))
ans = 1
for i in a:
  ans *= i
if ans > 10**18:
  print(-1)
  exit()
  
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int ,input().split()))
ans = 1
if 0 in a:
  print(0)
  exit()
for i in range(n):
  ans *= a[i]
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

S = input()
N = int(input())
Q = [[] for _ in range(N)]
for i in range(N):
    line = input().split()
    Q[i] = line
reverse = 0
for i in range(N):
    if Q[i][0] == '1' :
        reverse = (reverse + 1) % 2
    else :
        if reverse == 0 :
            if Q[i][1] == '1' :
                S = Q[i][2] + S
            else :
                S = S +Q[i][2]
        else:
            if Q[i][1] == '1':
                S = S + Q[i][2]
            else:
                S = Q[i][2] + S
if reverse == 0 :
    print(S)
else:
    S = S[::-1]
    print(S)

### FIXED CODE ###

S = input()
N = int(input())
Q = [[] for _ in range(N)]
for i in range(N):
    line = input().split()
    Q[i] = line
reverse = 0
r_b = ""
r_f = ""
for i in range(N):
    if Q[i][0] == '1' :
        reverse = (reverse + 1) % 2
    else :
        if reverse == 0 :
            if Q[i][1] == '1' :
                r_f = Q[i][2] + r_f
            else :
                r_b = r_b +Q[i][2]
        else:
            if Q[i][1] == '1':
                r_b = r_b +Q[i][2]
            else:
                r_f = Q[i][2] + r_f
if reverse == 0 :
    print(r_f + S + r_b)
else:
    r_f = r_f[::-1]
    r_b = r_b[::-1]
    S = S[::-1]
    print(r_b + S + r_f)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = wv[i]
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))

### FIXED CODE ###

N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))
### BUGGY CODE ###

#Reference : http://qiita.com/lethe2211/items/6cbade2bc547649bc040
n = input()

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

start_point = 0
peak = 0
max_diff = -pow(10, 9)

while (start_point < n - 1):
    diff = -pow(10, 9)
    for i in range(start_point + 1, n):
         diff_temp = R[i] - R[start_point]
         if (diff_temp >= diff):
             diff = diff_temp
             peak = i
    for i in range(start_point, peak):
        diff_temp = R[peak] - R[i]
        if (diff_temp > max_diff):
            max_diff = diff_temp
    start_point = peak

print max_diff

### FIXED CODE ###

#Reference : http://qiita.com/lethe2211/items/6cbade2bc547649bc040
#Reference : http://judge.u-aizu.ac.jp/onlinejudge/commentary.jsp?id=ALDS1_1_D
n = input()

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

min_v = R[0]
max_v = -pow(10, 9)
for i in range(1, n):
    temp = R[i] - min_v
    if (temp >= max_v):
        max_v = temp
    temp = R[i]
    if (min_v >= temp):
        min_v = temp
print max_v
### BUGGY CODE ###

n, k = map(int, raw_input().split(" "))

l = []
d = {}
for i in range(n):
    a1, b1 = map(int, raw_input().split(" "))
    if a1 in l:
        d[a1] += b1
    else:
        l.append(a1)
        d[a1] = b1

l.sort()
count = 0
for item in l:
    count += d[item]
    if k <= count:
        print item
        break


### FIXED CODE ###

line_one = raw_input().split()
n = int(line_one[0])
k = int(line_one[1])

l = []
#d = {}
for i in range(n):
    line_one2 = raw_input().split()
    a1 = int(line_one2[0])
    b1 = int(line_one2[1])
    l.append( ( a1, b1 ))
    #if a1 in l:
    #    #d[a1] += b1
    #    l[a1][1] += b1
    #else:
    #    l.append( ( a1, b1 ))
    #    #//d[a1] = b1

#l.sort()
l = sorted(l, key=lambda x: x[0])
count = 0
for item in l:
    count += item[1]
    if k <= count:
        print item[0]
        break
### BUGGY CODE ###

import numpy as np


def Z_algorithm(s):
    n = len(s)
    Z = [0] * n  # z[i] = sum(s[0::n - i], s[i::n])
    Z[0] = n
    i, j = 1, 0
    while i < n:
        # 共通部分を見つけるパート
        while i + j < n and s[j] == s[i + j]:
            j += 1
        Z[i] = j

        if j == 0:
            i += 1
            continue
        # 計算の再利用パート
        # k + Z[k] < j なら再利用できる
        k = 1
        while k < j and k + Z[k] < j:
            Z[i + k] = Z[k]
            k += 1
        # k個先まで見たのでk個先にバトンを渡す
        i += k
        j -= k
    return Z


n, s = int(input()), input()
print(max((np.minimum(Z_algorithm(s[i:]), range(n - i))).max() for i in range(n)))


### FIXED CODE ###

n, s = int(input()), input()
dp = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            dp[i + 1][j + 1] = min(dp[i][j] + 1, j - i)
from itertools import chain
print(max(i for i in chain.from_iterable(dp)))
### BUGGY CODE ###

words = lambda t : list(map(t, input().split()))

def getNext(xs, i):
    if i == len(xs)-1:
        return 0
    else:
        return i+1

def getPrev(xs, i):
    if i == 0:
        return len(xs)-1
    else:
        return i-1

n = int(input())
a = words(int)
b = words(int)

import queue
q = queue.Queue()

def verify(i):
    if b[i] != a[i] and b[i] - (b[getNext(b,i)] + b[getPrev(b,i)]) >= a[i]:
        return True
    else:
        return False

for i in range(len(b)):
    if b[i] >= a[i] and verify(i):
        q.put(i)

ans = 0
succeed = True
while not q.empty():
    i = q.get()
    #print(i, b)
    d = b[getNext(b,i)] + b[getPrev(b,i)]
    if b[i] % d == a[i] % d:
        ans += b[i] // d - (a[i] // d)
        b[i] = a[i]
    else:
        ans += b[i] // d
        b[i] = b[i] % d
    if b[i] < a[i]:
        succeed = False
        break
    if verify(getNext(b,i)):
        q.put(getNext(b,i))
    if verify(getPrev(b,i)):
        q.put(getPrev(b,i))

for i in range(len(b)):
    if a[i] != b[i]:
        succeed = False
        break

if succeed:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

words = lambda t : list(map(t, input().split()))



n = int(input())
a = words(int)
b = words(int)

def getNext(i):
    if i == n-1:
        return 0
    else:
        return i+1

def getPrev(i):
    if i == 0:
        return n-1
    else:
        return i-1

from collections import deque
q = deque()

def verify(i):
    if b[i] != a[i] and b[i] - (b[getNext(i)] + b[getPrev(i)]) >= a[i]:
        return True
    else:
        return False

for i in range(len(b)):
    if b[i] >= a[i] and verify(i):
        q.append(i)

ans = 0
succeed = True
while not len(q) == 0:
    i = q.popleft()
    ni = getNext(i)
    pi = getPrev(i)
    #print(i, b)
    d = b[ni] + b[pi]
    if b[i] % d == a[i] % d:
        ans += b[i] // d - (a[i] // d)
        b[i] = a[i]
    else:
        ans += b[i] // d
        b[i] %= d
    if b[i] < a[i]:
        succeed = False
        break
    if verify(ni):
        q.append(ni)
    if verify(pi):
        q.append(pi)

for i in range(len(b)):
    if a[i] != b[i]:
        succeed = False
        break

if succeed:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

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

def P(n):
  return (n + 1) / 2
  
ans = []
for i in range(N - (K - 1)):
  a = []
  for j in range(K):
    a.append(p[i+j])
  if sum(a) > sum(ans):
    ans = a

A = 0
for x in range(K):
  A += P(ans[x])

print(A)

### FIXED CODE ###

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

a = 0
for i in range(N - K + 1):
  if i == 0:
    b = sum(p[0:K])
  else:
    b = b - p[i-1] + p[i + K - 1]
  
  if b > a:
    a = b
    f = i

ans = 0
for j in range(K):
  ans += (p[f + j] + 1) / 2

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

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))

for i in range(Q):
    for j in range(N):
        if BC[i][0]==A[j]:A[j]=BC[i][1]
    print(sum(A))

### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
#BC=[]
#for i in range(Q):
#    BC.append(list(map(int,input().split())))
A_sum=sum(A)
A_count=Counter(A)

for i in range(Q):
    B,C=(map(int,input().split()))
    A_sum+=(C-B)*A_count[B]
    A_count[C]+=A_count[B]
    A_count[B]=0
    print(A_sum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
n = len(edges)
colors = [-1]*(n+1)

def paint(v,c):
    if colors[v] == -1:
        colors[v] = c
        nxC = (c+1)%2
        for nxV in edges[v]:
            result = paint(nxV,nxC)
            if result == False:
                return result
    else:
        if colors[v] != c:
            return False
    return True
    
if paint(1,0):
    ans = colors.count(1)*colors.count(0)-M
else:
    def choose(n,k):
        import math
        return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    ans = choose(N,2)-M
print(ans)

### FIXED CODE ###

"""
グラフが二部グラフかどうかを判定する。
二部グラフであれば、AグループのノードとBグループのノード同士をそれぞれ結ぶことができる。
二部グラフでない場合、すべてのノード同士を結ぶことができる。
"""
import math
from collections import Counter
import sys
sys.setrecursionlimit(200000)
def choose(n):
    return math.factorial(n)//(math.factorial(n-2)*math.factorial(2))
N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    edges[A].append(B)
    edges[B].append(A)

colors = [-1]*(N+1)
def f(n,p):
    c = colors[n]
    for v in edges[n]:
        if v != p:
            if colors[v] == -1:
                colors[v] = 1 if c==0 else 0
                f(v,n)
            elif colors[v] == c:
                print(choose(N)-M)
                exit()
colors[1]=0
f(1,0)
count1 = colors.count(0)
count2 = colors.count(1)
print(count1*count2-M)
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()
    W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for sum_w in range(K + 1):
        for i in range(N):
            if sum_w - W[i] > -1:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - W[i]] + V[i]
                )
            else:
                dp[i + 1][sum_w] = dp[i][sum_w]

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


main()


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

import numpy as np
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
c = np.zeros(10 ** 3 + 1, dtype=int)
for l in L:
    c[l] += 1
ans = 0
for i, a in enumerate(L):
    for b in L[i+1:]:
        ans += c[a - b + 1:b].sum()
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
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):
        x = L[i] - L[j]
        bottom = bisect_right(L, x)
        if j > bottom:
            ans += j - bottom
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
"""
3000以下なので全探索を考える。
まず，全探索できるものは全探索から考える必要がある。
"""

count = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        n_b = (N - r*R - g*G)
        if n_b % B == 0 and n_b >= 0:
            count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
"""
3000以下なので全探索を考える。
まず，全探索できるものは全探索から考える必要がある。
オーダーを計算し，いけそうならそれで行くべき。今回は固定を順にしていくので間に合う
そこから探索する範囲を絞り込んで
"""

count = 0
for r in range(N//R+1):
    rest = N - r*R
    for g in range(rest//G+1):
        n_b = (rest - g*G)
        if n_b % B == 0 and n_b >= 0:
            count += 1
print(count)
### BUGGY CODE ###

L = [input(), input()]
A = L[1].split()
print(' '.join([str(A.index(str(i))+1) for i in range(1, int(L[0])+1)]))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
lists = [0] * n

for i in range(n):
    lists[a[i] - 1] = i + 1
    
for i in lists:
  print(i , end =' ')
### BUGGY CODE ###

import sys
from collections import deque

S = input()
Q = int(input())
QUERY = sys.stdin.readlines()

state = 0
q1 = deque()
q2 = deque()
for i in range(Q):
    query = QUERY[i]
    if query[0] == '1':
        state ^= 1
    else:
        _, F, C = query.split()
        F = int(F)
        if (state + F) % 2 == 1:
            q1.appendleft(C)
        else:
            q2.append(C)

ans = ''
if state == 0:
    while q1:
        ans += q1.popleft()
    ans += S
    while q2:
        ans += q2.popleft()
else:
    while q2:
        ans += q2.pop()
    ans += ''.join(list(reversed(S)))
    while q1:
        ans += q1.pop()
print(ans)


### FIXED CODE ###

import sys

S = input()
Q = int(input())
QUERY = sys.stdin.readlines()

state = 0
q1 = ''
q2 = ''
for i in range(Q):
    query = QUERY[i]
    if query[0] == '1':
        state ^= 1
    else:
        _, F, C = query.split()
        if (state + int(F)) % 2:
            q1 += C
        else:
            q2 += C

ans = ''
if state == 0:
    print(q1[::-1], end='')
    print(S, end='')
    print(q2)
else:
    print(q2[::-1], end='')
    print(S[::-1], end='')
    print(q1)
### BUGGY CODE ###

S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
            
    for j in range(10):
        dp[i + 1][j] %= MOD
        
print(dp[-1][5])


### FIXED CODE ###

S = input()

MOD = 10 ** 9 + 7
MAX_LEN = len(S)
dp = [[0] * 13 for _ in range(MAX_LEN + 1)]
dp[0][0] = 1

for i in range(MAX_LEN):
    c = int(S[i]) if S[i] != '?' else -1
    for j in range(10):
        if c != -1 and c != j:
            continue
        
        for k in range(13):
            idx = (k * 10 + j) % 13
            dp[i + 1][idx] += dp[i][k]
            dp[i + 1][idx] %= MOD
        
print(dp[-1][5])
### BUGGY CODE ###

from collections import deque

H, W = [int(i) for i in input().split()]
S = [list(input()) for _ in range(H)]

white = sum(s.count(".") for s in S)

Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if not (0 <= nh < H and 0 <= nw < W):
            continue
        if S[nh][nw] == ".":
            S[h][w] = "" # visited
            Q.append((nh, nw, count + 1))
print(-1)

### FIXED CODE ###

from collections import deque

H, W = [int(i) for i in input().split()]
S = [list(input()) for _ in range(H)]

white = sum(s.count(".") for s in S)

S[0][0] = "_"
Q = deque([(0, 0, 1)])
while Q:
    h, w, count = Q.popleft()
    if (h, w) == (H - 1, W - 1):
        print(white - count)
        quit()

    for nh, nw in [(h, w + 1), (h, w - 1), (h + 1, w), (h - 1, w)]:
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            S[nh][nw] = "_"
            Q.append((nh, nw, count + 1))
print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
import sys

if n > int(m / 2):
    print(int(m / 2))
    sys.exit(0)

while True:
    if n > (m - 2) / 2:
        break
    else:
        n += 1
        m -= 2
print(int(m / 2))

### FIXED CODE ###

n, m = map(int, input().split())
import sys

if n > int(m / 2):
    print(int(m / 2))
    sys.exit(0)

print(n + int((m - n * 2) / 4))
### BUGGY CODE ###

n=int(input())
Alist=[0]+[int(input()) for i in range(n)]

now=1
Hist=[1]

for i in range(n):
    now=Alist[now]
    if now==2:
        print(i+1)
        break
    if now in Hist:
        print(-1)
        break
    Hist.append(now)

### FIXED CODE ###

n=int(input())
Alist=[0]+[int(input()) for i in range(n)]

now=1
count=0

for _ in range(n):
    now=Alist[now]
    count+=1
    if now==2:
        print(count)
        exit()
print(-1)