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

import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 998244353
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

n,k = LI()
p = LI()

def a(num):
    return 0.5*num + 0.5

ans = 0
for i in range(n-k+1):
    ans = max(ans,sum([a(j) for j in p[i:i+k]]))
print(ans)


### FIXED CODE ###

import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 998244353
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

n,k = LI()
p = LI()

def a(num):
    return (num+1)/2

l = [a(i) for i in p]
ll = [0] + list(itertools.accumulate(l))
ans=0
for i in range(n-k+1):
    ans = max(ans,ll[i+k]-ll[i])
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
s1="";s2=""
adds=[s1,s2]
sta=0
for i in range(q):
    a=tuple(input().split(" "))#;print(a)
    if a[0]=="1":
        sta^=1
    else:
        if a[1]=="1":
            if not sta:
                s1=a[2]+s1
            else:
                s2+=a[2]
        if a[1]=="2":
            if sta:
                s1=a[2]+s1
            else:
                s2+=a[2]                
ans=s1+s+s2
#print(s1,s,s2)
if sta:
    print(ans[::-1])
else:print(ans)

### FIXED CODE ###

s=input()
q=int(input())
s1="";s2=""
adds=[s1,s2]
sta=0
for i in range(q):
    a=tuple(input().split(" "))#;print(a)
    if a[0]=="1":
        sta^=1
    else:
        if a[1]=="1":
            if not sta:
                s1=a[2]+s1
            else:
                s2+=a[2]
        if a[1]=="2":
            if sta:
                s1=a[2]+s1
            else:
                s2+=a[2]                
ans=s1+s+s2
#print(s1,s,s2)
if sta:
    print(ans[::-1])
else:print(ans)
### BUGGY CODE ###

from math import sqrt
def isprime(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    if n % 2 == 0:
        return 0
    for i in range(2,int(sqrt(n)+1)):
        if n % i == 0:
            return 0
    return 1

from sys import stdin
for i in stdin:
    i = int(i)
    print(sum(isprime(n) for n in range(2,i+1)))

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###


#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

N,W = map(int,input().split())
wv = int_mtx(N)

#f_inf = float("inf")
#dp = [f_inf]*N

# dp[i][w] = "番号 i 以下の商品でバッグの重さが w 以下になるように最適に詰めた場合"
dp = np.array([[0]*(W+1)]*(N+1),dtype=np.int64)

# for i in range(1,N+1):
#     for w in range(1,W+1):
#         if w-wv[i-1][0] >= 0:
#             dp[i][w] = max(dp[i-1][w-wv[i-1][0]]+wv[i-1][1] , dp[i-1][w])
#         else:
#             dp[i][w] = dp[i-1][w]

for i in range(1,N+1):
    for w in range(wv[i-1,0],W+1):
        dp[i,w] = max(dp[i-1,w-wv[i-1,0]]+wv[i-1,1] , dp[i-1,w])
    dp[i,1:wv[i-1,0]] = dp[i-1,1:wv[i-1,0]]

print(dp[N][W])


### FIXED CODE ###

def e():
    import numpy as np

    N, W = map(int, input().split())

    dp = np.zeros(W+1, dtype=np.int64)

    for _ in range(N):
        w, v = map(int, input().split())
        np.maximum(dp[:-w]+v, dp[w:], out=dp[w:])

    print(dp[-1])


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

import math
s=input()
n=len(s)
count=0
a=[0 for i in range(2019)]
a[0]=1
k=0
for i in reversed(range(0,n)):
    k+=10**(n-i-1)*int(s[i])
    a[k%2019]+=1
        

for i in range(len(a)):
    if a[i]>=2:
        count+=(a[i])*(a[i]-1)//2
print(count)

### FIXED CODE ###

import math
s=input()
n=len(s)
count=0
a=[0 for i in range(2019)]
a[0]=1
k=0
b=[0 for i in range(n)]
b[0]=1
for i in range(1,n):
    b[i]=b[i-1]*10%2019
for i in reversed(range(0,n)):
    k+=(b[n-i-1])*int(s[i])%2019
    a[k%2019]+=1        
for i in range(len(a)):
    if a[i]>=2:
        count+=(a[i])*(a[i]-1)//2
print(count)
### BUGGY CODE ###

import sys

n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
for line in sys.stdin:
    b, c = list(map(int, line.split()))
    aaa = sorted(aaa + [c] * b, reverse=True)[:n]
print(sum(aaa))


### FIXED CODE ###

import sys

n, m = list(map(int, input().split()))
aaa = list(map(int, input().split()))
aaa.sort()
bc = []
for line in sys.stdin:
    b, c = map(int, line.split())
    bc.append((c, b))
bc.sort(reverse=True)
ans = 0
cnt = 0
for c, b in bc:
    while aaa and aaa[-1] >= c and cnt < n:
        ans += aaa.pop()
        cnt += 1
    if cnt + b >= n:
        ans += c * (n - cnt)
        cnt = n
        break
    ans += c * b
    cnt += b
if cnt < n:
    ans += sum(aaa[cnt - n:])
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
cnt=0
while True:
    if [a%2 for a in A]==[0]*N:
        A=[a//2 for a in A]
        cnt+=1
print(cnt)

       
       

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
cnt=0
while True:
    if [a%2 for a in A]==[0]*N:
        A=[a//2 for a in A]
        cnt+=1
    else:break
print(cnt)
### BUGGY CODE ###

import re
from collections import Counter
s = input()
res = re.findall(r"<+>+", s) + re.findall(r"^>+", s) + re.findall(r"<+$", s)

def calc(string):
    ct = Counter(string)
    cnt_d = ct[">"]
    cnt_s = ct["<"]
    if cnt_s > cnt_d:
        return (cnt_s * (cnt_s + 1) + (cnt_d - 1) * cnt_d) // 2
    elif cnt_s == cnt_d:
        return cnt_s * cnt_s
    else:
        return ((cnt_d + 1) * cnt_d + (cnt_s - 1) * cnt_s) // 2
score = 0
for r in res:
    score += calc(r)
print(score)

### FIXED CODE ###

import re
from collections import Counter
s = input()
res = re.finditer(r"(<+>+)|(^>+)|(<+$)", s)

def calc(string):
    ct = Counter(string)
    cnt_d = ct[">"]
    cnt_s = ct["<"]
    if cnt_s > cnt_d:
        return (cnt_s * (cnt_s + 1) + (cnt_d - 1) * cnt_d) // 2
    elif cnt_s == cnt_d:
        return cnt_s * cnt_s
    else:
        return ((cnt_d + 1) * cnt_d + (cnt_s - 1) * cnt_s) // 2
score = 0
for r in res:
    score += calc(r.group())
print(score)
### BUGGY CODE ###

h,w=map(int,input().split())
t=[["#"]*(w+2)]+[list("#"+input()+"#")for i in range(h)]+[["#"]*(w+2)]
p=[[[0,0]for i in range(w+2)] for i in range(h+2)]
def  f(a,b,c):
    d=0
    if c=="h":
        while t[a][b]==".":
            a+=1
            d+=1
    else:
        while t[a][b]==".":
            b+=1
            d+=1
    return d
a=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if t[i][j]!="#":
            if p[i-1][j][0]==0:
                p[i][j][0]=f(i,j,"h")
            else:
                p[i][j][0]=p[i-1][j][0]
            if p[i][j-1][1]==0:
                p[i][j][1]=f(i,j,"w")
            else:
                p[i][j][1]=p[i][j-1][1]
            a=max(a,sum(p[i][j]))
print(a-1)        

### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
a=np.array([[0 if i!="." else 1 for i in input()]for j in range(h)])
s,t,u,p=np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w)),np.zeros((h,w))
for i in range(h):
    s[i]=(s[i-1]+1)*a[i]
    t[-i-1]=(t[-i]+1)*a[-i-1]
for i in range(w):
    u[:,i]=(u[:,i-1]+1)*a[:,i]
    p[:,-i-1]=(p[:,-i]+1)*a[:,-i-1]
print(int(np.max(s+t+u+p))-3)
### BUGGY CODE ###

n = int(input())
s=[]
for i in range(n):
    s.append(input())
list_s = []
for j in range(n):
    list_s.append(sorted(list(s[j])))
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]
unique_list = get_unique_list(list_s)
ans = []
for k in range(len(unique_list)):
    count = 0
    for l in range(n):
        if unique_list[k] == list_s[l]:
            count += 1
    ans.append(count * (count-1) // 2)

print(sum(ans))

### FIXED CODE ###

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

list_s = []
for j in range(n):
    #list_s.append(sorted(list(s[j])))
    list_s.append(''.join(sorted(s[j])))

m = {}
for i in range(n):
    if list_s[i] not in m:
        m[list_s[i]] = 1
    else:
        m[list_s[i]] += 1

def cmb(num):
    if num == 1:
        return 0
    elif num == 2:
        return 1
    else:
        return (num * (num-1) // 2)
  
count = 0
for k in m.keys():
        count += cmb( m[k] )


print(count)
### BUGGY CODE ###


from collections import deque
def resolve():
    drc4 = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + drc4]

    def bfs(start, goal):
        sy, sx = start
        gy, gx = goal
        q = deque()
        q.append(start)
        ans[sy][sx] = 0

        while q:
            sy, sx = q.popleft()
            for dy, dx in drc4:
                ny, nx = dy + sy, dx + sx
                if 0 <= ny < H and 0 <= nx < W:
                    if G[ny][nx] == "." and ans[ny][nx] > ans[sy][sx]:
                        ans[ny][nx] = ans[sy][sx]
                        q.append((ny, nx))

            for dy8, dx8 in warp:
                ny8, nx8 = dy8 + sy, dx8 + sx
                if 0 <= ny8 < H and 0 <= nx8 < W:
                    if G[ny8][nx8] == "." and ans[ny8][nx8] > ans[sy][sx] + 1:
                        ans[ny8][nx8] = ans[sy][sx] + 1
                        q.append((ny8, nx8))

    H, W = map(int, input().split())
    sy, sx = map(lambda x: int(x) - 1, input().split())
    gy, gx = map(lambda x: int(x) - 1, input().split())
    G = [input() for _ in range(H)]

    INF = 10 ** 7
    ans = [[INF] * W for _ in range(H)]

    bfs((sy, sx), (gy, gx))

    print(ans[gy][gx] if ans[gy][gx] < INF else '-1')


if __name__ == "__main__":
    resolve()


### FIXED CODE ###


from collections import deque
def resolve():
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x) - 1, input().split())
    Dh, Dw = map(lambda x: int(x) - 1, input().split())
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))
        for dx, dy in warp:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else -1
    print(ans)


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

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

def readInts():
  return [int(s) for s in input().split(" ")]

def gcd(m, n):
  m, n = max(m, n), min(m, n)
  if n == 0:
    return m
  return gcd(n, m % n)

def gcds(A):
  ret = A[0]
  for n in A[1:]:
    ret = gcd(ret, n)
  return ret

def main():
  N = readInts()[0]
  A = readInts()

  m = 1
  for i in range(N):
    m = max(m, gcds(A[0:i] + A[i+1:]))
  print(m)

if __name__ == "__main__":
  main()


### FIXED CODE ###

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

def readInts():
  return [int(s) for s in input().split(" ")]

def gcd(m, n):
  m, n = max(m, n), min(m, n)
  if n == 0:
    return m
  return gcd(n, m % n)

def gcds(A):
  ret = A[0]
  for n in A[1:]:
    ret = gcd(ret, n)
  return ret

def main():
  N = readInts()[0]
  A = readInts()

  lgcds = [1 for _ in range(N)]
  lgcds[0] = A[0]
  for i in range(N-1):
    lgcds[i+1] = gcd(lgcds[i], A[i+1])

  rgcds = [1 for _ in range(N)]
  rgcds[N-1] = A[N-1]
  for i in range(1, N):
    rgcds[N-1-i] = gcd(rgcds[N-i], A[N-1-i])

  m = 1
  for i in range(N):
    if i == 0:
      m = max(m, rgcds[i+1])
    elif i == N - 1:
      m = max(m, lgcds[i-1])
    else:
      m = max(m, gcd(lgcds[i-1], rgcds[i+1]))
  print(m)

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

s = input()

d = ["z"*5010]*5

for i in range(len(s)):
    for j in range(i, len(s)):
        x = s[i:j+1]
        if x in d or x == '':
            continue
        k = 0
        while k < 5 and x > d[k]:
            k += 1
        # print(k, d[0:k], x, d[k:])
        if k < 5:
            d = d[0:k] + [x] + d[k:]
            d = d[0:5]
        # print(f"->{d}")
# l = list(d)
# l.sort()
# print(l)
# if l[0] == '':
    # l = l[1:]

k = int(input())
print(d[k-1])


### FIXED CODE ###

s = input()

d = ["z"*5010]*5

k = int(input())
for i in range(len(s)):
    for j in range(i, i+k):
        x = s[i:j+1]
        if x in d or x == '':
            continue
        l = 0
        while l < 5 and x > d[l]:
            l += 1
        # print(k, d[0:k], x, d[k:])
        if l < 5:
            d = d[0:l] + [x] + d[l:]
            d = d[0:5]
        # print(f"->{d}")
# l = list(d)
# l.sort()
# print(l)
# if l[0] == '':
    # l = l[1:]

print(d[k-1])
### BUGGY CODE ###

n,x,y = map(int,input().split())
ans = [0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        p= min(abs(i-j),(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))
        ans[p] += 1
for i in range(1,n):
    print(ans[i])


### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*n
for i in range(n):
    for j in range(i,n):
        ans[min(j-i,(abs(i-(x-1))+1+abs(y-1-j)),(abs(i-(x-1))+1+abs(y-1-j)))] += 1
for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

dp=[[0]*(w+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,w+1):
        if j-W[i]>=0:
            dp[i][j]=max(dp[i-1][j-W[i]]+V[i],dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,w=n1()
WV=n3(n)

W=[0]
W.extend([x[0] for x in WV])
V=[0]
V.extend([x[1] for x in WV])

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

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if not ANS[idx]:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if not ANS[i] : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if not ANS[i] : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
 
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.9907
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
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 ###

S = input()
N = len(S)
CNT = [0]*2019
CNT[0] = 1

for i in range(1, N+1):
    CNT[int(S[:i]) * pow(10, N-i)%2019] += 1
ans = 0
for cnt in CNT:
    if cnt==0: continue
    ans += (cnt*(cnt - 1)) // 2
print(ans)

### FIXED CODE ###

S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)
### BUGGY CODE ###

n,y=map(int,input().split())
anslist=[]
for i in range(n+1):
    for j in range(n-i+1):
        for k in range(n-i-j+1):
            if i*10000+j*5000+k*1000 == y :
                list=[i,j,k]
                anslist.append(list)
if len(anslist)>0:
    print("{} {} {}".format(anslist[0][0],anslist[0][1],anslist[0][2],))
else:
    print("{} {} {}".format(-1,-1,-1))

### FIXED CODE ###

n,y=map(int,input().split())
anslist=[]
for i in range(n+1):
    for j in range(n-i+1):
        if i*10000+j*5000+(n-i-j)*1000 == y :
            print(i,j,n-i-j)
            exit()
print("{} {} {}".format(-1,-1,-1))
### BUGGY CODE ###

_,*a = open(0).read().split()
for n,m in enumerate(a):
    b = a + []
    del b[n]
    print(eval("^".join(b)),end=" ")

### FIXED CODE ###

_,*a = open(0).read().split()
x = eval("^".join(a))
for i in a:
    print(x^int(i),end=" ")
### BUGGY CODE ###

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

### FIXED CODE ###

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

n = int(input())
a = [int(x) for x in input().split()]

#a = [x * 2 for x in a]
sol = []

for i in range(n):
    b = 1
    temp = 0
    for j in range(n):
        temp += a[j] * b
        b = b * -1
    sol.append(temp)
    x = a.pop(0)
    a.append(x)

print(' '.join(map(str, sol)))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

c = 0
for i in range(n):
    c += a[i] * (-2 * (i%2) + 1)

sol = [c]

for i in range(1,n):
    c = c * (-1) + 2 * a[i-1]
    sol.append(c)
    
print(' '.join(map(str, sol)))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
total = 0
while cnt != len(a):
    cnt = 0
    for i in range(len(a)):
        if a[i] % 2 == 0:
            a[i] //= 2
            total += 1
            break
        else:
            cnt += 1
print(total)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
total = 0
for i in range(len(a)):
    while a[i] % 2 == 0:
        total += 1
        a[i] //= 2
print(total)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans = ans*A[i]



if ans == 0:
    print(ans)
else:
    if ans > pow(10,18):
        print(-1)
    else:
        print(ans)


### FIXED CODE ###

import math,sys
N = int(input())
A = list(map(int, input().split()))
ans = 1

if 0 in A:
    print(0)
    sys.exit()

for i in range(N):
    ans = ans*A[i]
    if ans > pow(10,18):
        print(-1)
        sys.exit()

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

L=list(map(int,input()))
n=len(L)
X=pow(3,n-1)
count=1
for i in range(1,n):
    if L[i]==1:
        k=n-i-1
        count+=1
        X+=pow(3,k)*pow(2,count-1)
X+=pow(2,count)
print(X%(10**9+7))


### FIXED CODE ###

L=list(map(int,input()))
n=len(L)
def power(a,n):
    x=1
    L=list(format(n,'b'))
    l=len(L)
    for i in range(l):
        if int(L[l-i-1])==1:        
            x=(x*a)%(10**9+7)
        a=(a*a)%(10**9+7)
    return x
X=power(3,n-1)%(10**9+7)
count=1
for i in range(1,n):
    if L[i]==1:
        k=n-i-1
        count+=1
        X+=(power(3,k)%(10**9+7))*(power(2,count-1)%(10**9+7))
X+=power(2,count)%(10**9+7)
print(X%(10**9+7))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0
while all(A % 2 == 0 for A in a):
    A = [i / 2 for i in a]
    ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
cnt = 0
while True:
    for i in range(n):
        if a[i] % 2 == 1:
            print(cnt)
            quit()
        a[i] /= 2
    cnt += 1
print(cnt)