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

import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())
 
tree = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
 
adds = defaultdict(int)
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x
 
def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    for v in tree[i]: dig(v,tmp)
 
ans = defaultdict(int)
tmp = 0
dig(1,tmp)
 
for i in range(1,N+1):
    print(ans[i], end=' ')
print()

### FIXED CODE ###

from queue import deque
N,Q = map(int,input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

ans = {i+1:0 for i in range(N)}
for i in range(Q):
    p,x = map(int,input().split())
    ans[p] += x

checked = [False for i in range(N+1)]
myq = deque()
myq.append(1)

while myq:
    v = myq.pop()
    checked[v] = True
    for n in tree[v]:
        if not checked[n]:
            ans[n] += ans[v]
            myq.append(n)
print(' '.join(str(ans[i]) for i in range(1,N+1)))
### BUGGY CODE ###

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

for i in range(N):
    A0=A.copy()
    A0.pop(i)
    A0=sorted(A0)
    
    ii=0
    C=0
    L=0
    while ii<N-1:
        C=A0.count(A0[ii])
        ii+=C
        L=int(C*(C-1)/2)+L
    print(L)

### FIXED CODE ###

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

L=0
C=[0]*N

for i in range(N):
    C[A[i]-1]+=1

for i in range(N):
    L+=int(C[i]*(C[i]-1)/2)
    
for i in A:
    print(L-C[i-1]+1)
### BUGGY CODE ###

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

minimumCostToReach = [0 for i in range(N)]

minimumCostToReach[0] = 0
for currentIndex in range(1, N):
  minimumCostToReach[currentIndex] = 1000000000

  previousIndex = currentIndex - 1
  while previousIndex >= 0 and previousIndex + K >= currentIndex:
    cost = minimumCostToReach[previousIndex] + abs(h[currentIndex] - h[previousIndex])
    minimumCostToReach[currentIndex] = min(minimumCostToReach[currentIndex], cost)
    previousIndex -= 1

print(minimumCostToReach[N - 1])


### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N

  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))

  return dp[N - 1]

print(solve())
### BUGGY CODE ###

import sys
from io import StringIO
import unittest
import math


def check(A, F, x, N, K):
    for i in range(N):
        if A[i] * F[i] > x:
            k = math.ceil(A[i] - x / F[i])
            K -= k
    if K < 0:
        return False
    else:
        return True


def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse=True)
    F.sort()

    # binary search
    l = 0
    r = max(A) * max(F)
    result = None
    while l <= r:
        # print('l {}, r {}'.format(l, r))
        if l == r:
            result = l
            break
        mid = (l + r) // 2
        if check(A, F, mid, N, K):
            r = mid
        else:
            l = mid + 1

    print(result)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 5
4 2 1
2 3 1"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 8
4 2 1
2 3 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2"""
        output = """12"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

import math


def check(A, F, x, N, K):
    for i in range(N):
        if A[i] * F[i] > x:
            k = math.ceil(A[i] - x / F[i])
            K -= k
    if K < 0:
        return False
    else:
        return True


def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse=True)
    F.sort()

    # binary search
    l = 0
    r = max(A) * max(F)
    result = None
    while l <= r:
        # print('l {}, r {}'.format(l, r))
        if l == r:
            result = l
            break
        mid = (l + r) // 2
        if check(A, F, mid, N, K):
            r = mid
        else:
            l = mid + 1

    print(result)


if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

S=input()
counter=0
while True:
    tmp=S.count('BW')
    if tmp == 0:
        print(counter)
        break
    else:
        counter+=tmp
        S=S.replace('BW','WB')

### FIXED CODE ###

S = input()
counter = 0
# while True:
#     tmp=S.count('BW')
#     if tmp == 0:
#         print(counter)
#         break
#     else:
#         counter+=tmp
#         S=S.replace('BW','WB')

# i=0
# while True:
#     tmp = S[i:].find('W')
#     print(S[i:])
#     if tmp == -1:
#         print(counter)
#         break
#     else:
#         counter += tmp
#         i+=1

sum=0
for i in range(len(S)):
    if S[i]=='W':
        sum+=i
        counter+=1

n=counter-1
minus=n*(n+1)/2
print(int(sum-minus))
### BUGGY CODE ###

N = int(input())
A = input().split()
answer = 1
flag = 0
x = 10**18
for i in range(N):
  A[i] = int(A[i])
  answer *= A[i]
  if answer == 0:
    break

check = answer/x
if ((check) >= 1) and (answer != x):
  print(-1)
else:
  print(answer)

### FIXED CODE ###

N = int(input())
A = input().split()
answer = 1
flag = 0
x = 10**18

if '0' in A:
  print(0)
  flag = 1
  


if flag == 0:
  for i in range(N):
    answer *= int(A[i])
    if answer > x:
      print(-1)
      flag = 1
      break

if flag == 0:    
  print(answer)
### BUGGY CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
ans = [k for _ in range(n)]
for i in range(q):
    ans[a[i]-1] += 1
    for j in range(n):
        ans[j] -= 1
for i in range(n):
    if ans[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
ans = [0 for _ in range(n)]
for i in range(q):
    ans[a[i]-1] += 1
for i in range(n):
    if q-ans[i] < k:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, W = map(int, input().split())
wv = []
dp = [[0] * (W + 1)]
for i in range(n):
    w, v = map(int, input().split())
    wv.append([w, v])
    dp.append([0] * (W + 1))

for i in range(n):
    for j in range(W + 1):
        if j - wv[i][0] >= 0:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i + 1][j])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, W = map(int, input().split())
dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
wv = [[int(x) for x in input().split()] for _ in range(n)]

for i in range(n):
    for j in range(W + 1):
        if j - wv[i][0] >= 0:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i + 1][j])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print(max(dp[-1]))
### BUGGY CODE ###

def main():
  from collections import deque
  from array import array
  s,*c=open(0)
  h,w=map(int,s.split())
  f=array('h',[-1]*h*w)
  q=deque()
  for i,c in enumerate(''.join(t[:w]for t in c)):
    if c=='#':
      q.append(i)
      f[i]=0
  while q:
    i=q.popleft()
    v=f[i]+1
    j,k,l,m=i+w,i-w,i+1,i-1
    if h*w>j and f[j]<0:
      q.append(j)
      f[j]=v
    if k>=0 and f[k]<0:
      q.append(k)
      f[k]=v
    if w>i%w+1and f[l]<0:
      q.append(l)
      f[l]=v
    if i%w and f[m]<0:
      q.append(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

### FIXED CODE ###

from collections import*
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=deque()
for i in range(h):
    for j in range(w):
        if c[i][j]=='#':
            q.append((i,j,0))
ans=0
while q:
    y,x,v=q.popleft()
    ans=max(ans,v)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
        if h>i>=0 and w>j>=0 and c[i][j]=='.':
            c[i][j]='#'
            q.append((i,j,v+1))
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())
k = []
for i in range(1, min(a, b)+1):
    if a % i == 0 and b % i == 0:
        k.append(i)
cnt = 0
for n in k:
    if n == 1:
        cnt += 1
    elif n == 2:
        cnt += 1
    else:
        flg = ""
        for p in range(2, n):
            if n % p == 0:
                flg = "composite"
                break
            else:
                flg = "prime"
        if flg == "prime":
            cnt += 1
print(cnt)


### FIXED CODE ###

import math

def gcd(n, m):
    while m != 0:
        n, m = m, n % m
    return n

a, b = map(int, input().split())
g = gcd(a, b)
g_2 = int(math.sqrt(g))
cnt = 1

for i in range(2, g_2+1):
    if g % i == 0:
        while g % i == 0:
            g //= i
        cnt += 1
if g > 1:
    cnt += 1

print(cnt)
### BUGGY CODE ###

from heapq import heappop,heappush

n = int(input())
p = []
for i in range(n):
    x,y = map(int,input().split())
    p.append((i,x,y))

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    #edge[source] = [[cost_1,target_1],[cost_2,target_2],...]
    used = [False] * n
    q = []
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))

### FIXED CODE ###

import sys
input = sys.stdin.readline

from heapq import heappop,heappush

n = int(input())
p = []
for i in range(n):
    x,y = map(int,input().split())
    p.append((i,x,y))

e = [[] for _ in range(n)]

p = sorted(p,key=lambda x:x[1])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

p = sorted(p,key=lambda x:x[2])
n0,x0,y0 = p[0]
for i in range(n-1):
    n1,x1,y1 = p[i+1]
    e[n0].append([min(abs(x1-x0),abs(y1-y0)),n1])
    e[n1].append([min(abs(x1-x0),abs(y1-y0)),n0])
    n0,x0,y0 = n1,x1,y1

def Prim(n,edge):
    #edge[source] = [[cost_1,target_1],[cost_2,target_2],...]
    used = [False] * n
    q = []
    #e = [cost,target]
    for e in edge[0]:
        heappush(q,e)
    used[0] = True
    res = 0
    while q:
        c,v = heappop(q)
        if used[v]:
            continue
        used[v] = True
        for e in edge[v]:
            if not used[e[1]]:
                heappush(q,e)
        res += c
    return res

print(Prim(n,e))
### BUGGY CODE ###

import math

S = int(input())

ans = [0, 0]
limit = 10 ** 9
for i in range(1, 10**9):
    seki = S + i ** 2
    for j in range(1, 10**9):
        div = seki % j
        if div == 0:
            if j > limit or seki // j > limit:
                continue
            ans += [j, i, i, seki // j]
            print(*ans)
            exit()


### FIXED CODE ###

import math

S = int(input())

ans = [0, 0]
if S <= 10 ** 9:
    ans += [S, 0, 0, 1]
else:
    root = math.ceil(math.sqrt(S))
    ans += [root ** 2 - S, root, root, 1]

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



def remove_data(data, ind_pre, ind_after):
    if ind_pre == 0:
        data_pre = ''
    else:
        data_pre = data[:ind_pre]
    if ind_after == len(data) - 1:
        data_after = ''
    else:
        data_after = data[ind_after + 1:]
    data_remove = data_pre + data_after
    return data_remove


def calc_data(data):
    flg = 1
    while flg:
        flg = 0
        for i in range(len(data) - 1):
            if data[i] != data[i + 1]:
                data = remove_data(data, i, i+1)
                flg = 1
                break
    return len(data)

def main():
    data = input()
    length = len(data)
    final_length = calc_data(data)
    print(length - final_length)


if __name__ == '__main__':
    main()

### FIXED CODE ###


def calc_data(data):
    count = 0
    c_0, c_1 = 0, 0
    for i in range(len(data)):
        if data[i] == '0':
            if c_1 > 0:
                count += 2
                c_1 -= 1
            else:
                c_0 += 1
        if data[i] == '1':
            if c_0 > 0:
                count += 2
                c_0 -= 1
            else:
                c_1 += 1
    print(count)

def main():
    data = input()
    calc_data(data)


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

n = int(input())
a = list(map(int, input().split()))
b = "APPROVED"
while b == "APPROVED":
  for i in a:
    if i % 2 == 0:
      if (i % 3 == 0 or i % 5 == 0):
        b = "APPROVED"
      else:
        b = "DENIED"
        break
print(b)

### FIXED CODE ###

from sys import exit
n = int(input())
a = list(map(int, input().split()))
b = "APPROVED"
while b == "APPROVED":
  for i in a:
    if i % 2 == 0:
      if (i % 3 == 0 or i % 5 == 0):
        b = "APPROVED"
      else:
        print("DENIED")
        exit()
  break
print(b)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i):
        for k in range(j,N+1):
            score(j,k,0,(-1)**(j+k+hand))

print(SCORE[0][N])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[0][N])
### BUGGY CODE ###

import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    count2 = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        tmp = count
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count == tmp : count2 += 1
        if count2 > 200 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

L,R = map(int,(input().split()))

A = []

ans = 2019

for i in range(L,R+1):
    A.append(i % 2019)

a = min(A)
b = max(A)

for j in range(a+1,b+1):
        for k in range(a,j):
            ans = min(ans,(j*k)%2019)
print(ans)

### FIXED CODE ###

L,R = map(int,(input().split()))

A = []

ans = 2019

if (R-L) >= 2018:
    print(0)
else:
    for i in range(L,R+1):
        A.append(i % 2019)
    a = min(A)
    b = max(A)
    for j in range(a+1,b+1):
            for k in range(a,j):
                ans = min(ans,(j*k)%2019)
    print(ans)
### BUGGY CODE ###

N = int(raw_input())
nums = []

for i in range(N):
    nums.append(int(raw_input()))

m = -1000000000000000000000000
for i in range(1, len(nums)):
    value = nums[i] - min(nums[:i])
    if m <= value:
        m = value

print(m)

### FIXED CODE ###

N = int(raw_input())
nums = []

for i in range(N):
    nums.append(int(raw_input()))

m = -1000000000000000000000000
minvalue = nums[0]

for i in range(1, len(nums)):
    minvalue = min(minvalue, nums[i-1])
    value = nums[i] - minvalue
    if m <= value:
        m = value

print(m)
### BUGGY CODE ###

import functools
import operator

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

prod = functools.partial(functools.reduce, operator.mul)
for i in range(K, N+1):
    sum_prod = prod(A[i-K:i])
    if i > K:
        if sum_prod > tmp_sum_prod:
            print('Yes')
        else:
            print('No')
    tmp_sum_prod = sum_prod


### FIXED CODE ###

import functools
import operator

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

# prod = functools.partial(functools.reduce, operator.mul)
# tmp_sum_prod = prod(A[:K])
for i in range(K, N):
    sum_prod = (A[i]/A[i-K])
    if sum_prod > 1.0:
        print('Yes')
    else:
        print('No')
    tmp_sum_prod = sum_prod
### BUGGY CODE ###

N, K=map(int, input().split())
A=list(map(int, input().split()))
for i in range(K):
  p=[0]*N
  n=[0]*N
  for i in range(N):
    if i-A[i]>0:
      p[i-A[i]]+=1
    else:
      p[0]+=1
    if i+A[i]<N-1:
      n[i+A[i]+1]+=1
  light=0
  Ncount=0
  for i in range(N):
    light=light+p[i]-n[i]
    A[i]=light
    if light==N:
      Ncount+=1
  if Ncount==N:
    out=[N]*N
    print(*out, sep=' ')
print(*A, sep=' ')

### FIXED CODE ###

N, K=map(int, input().split())
A=list(map(int, input().split()))
for i in range(K):
  p=[0]*N
  n=[0]*N
  for i in range(N):
    if i-A[i]>0:
      p[i-A[i]]+=1
    else:
      p[0]+=1
    if i+A[i]<N-1:
      n[i+A[i]+1]+=1
  light=0
  Ncount=0
  for i in range(N):
    light=light+p[i]-n[i]
    A[i]=light
    if light==N:
      Ncount+=1
  if Ncount==N:
    out=[N]*N
    print(*out, sep=' ')
    exit()
print(*A, sep=' ')
### BUGGY CODE ###

n, k, *hs = [int(x) for x in open(0).read().split()]                           
dp = [float("inf")] * n                                                        
dp[0] = 0                                                                      
for i in range(1, n):                                                          
    dp[i] = min([dp[j] + abs(hs[i] - hs[j]) for j in range(max(0, i - k), i)]) 
print(dp[n-1])                                                                 


### FIXED CODE ###

def main():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j, i)])
    print(dp[n-1])

main()
### BUGGY CODE ###

def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    dp=[[0]*13 for _ in range(n)]
    if s[-1]=="?":
        dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp[0][int(s[-1])]=1
    
    for i in range(1,n):
        ss=s[n-i-1:n]
    #     print(i,ss)
        ss0=ss[0]
        if ss0!="?":
            dp[i] = [ dp[i-1][(j-int(ss0)*10**i)%13] %mod for j in range(13)]
        else:
            dp[i] = [sum( dp[i-1][(j-k*10**i)%13] for k in range(10)) %mod for j in range(13) ]
    print(dp[-1][5])
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#d
def main():
    s=input()
    n=len(s)
    mod=10**9+7
    
    if s[-1]=="?":
        dp=[1,1,1,1,1,1,1,1,1,1,0,0,0]
    else:
        dp=[0]*13
        dp[int(s[-1])]=1
    
    for i in range(1,n):
        imod=10**(i %12)
        ss0=s[n-i-1]
        if ss0!="?":
            dpnew = [ dp[(j-int(ss0)*imod)%13] %mod for j in range(13)]
        else:
            dpnew = [sum( dp[(j-k*imod)%13] for k in range(10)) %mod for j in range(13) ]
        dp=dpnew[:]
    print(dp[5])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
Q = int(input())
query_q = [input().split() for _ in range(Q)]

for query in query_q:
    if query[0] == '1':
        S = S[::-1]
    elif query[0] == '2':
        if query[1] == '1':
            S = ''.join([query[2],S])
        elif query[1] == '2':
            S = ''.join([S,query[2]])

print(S)

### FIXED CODE ###

def main():

    S = input()
    Q = int(input())

    reverse = False
    head = ''
    tail = ''

    for _ in range(Q):
        query= input()
        if query == '1':
            reverse = not reverse
            head, tail = tail, head
        else:
            _, f, c = query.split()
            if f == '1':
                head = ''.join([head,c])
            else:
                tail = ''.join([tail,c])

    if reverse:
        S = S[::-1]

    print(''.join([head[::-1], S, tail]))

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

R,G,B,N=map(int,input().split())

cnt=0
for r in range(N+1):
    for g in range(N-r+1):
        b=N-(r+g)
        if b>=0 and r%R==g%G==b%B==0:
            cnt+=1
print(cnt)



### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(int(N / R) + 1):
    for j in range(int((N - i * R) / G) + 1):
        if ((N - (i * R + j * G)) % B == 0):
            ans += 1
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]

B=[]
for i in A:
    if i in B:
        B.remove(i)
    else:
        B.append(i)
print(len(B))

### FIXED CODE ###

N=int(input())
B=set()

for i in range(N):
    a=int(input())
    if a in B:
        B.remove(a)
    else:
        B.add(a)
print(len(B))
### BUGGY CODE ###

n, m = list(map(int, input().split()))
lst = range(n, (m//2)+1)
for i in lst:
    if m % i == 0:
        print(m // i)
        break
else:
    print(1)

### FIXED CODE ###

from math import sqrt
n, m = list(map(int, input().split()))
i = 1
lst = []
while i <= sqrt(m):
    if m % i == 0:
        j = m // i
        if i >= n:
            lst.append(i)
        if j >= n:
            lst.append(j)
    i += 1
print(m//min(lst))