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

import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    stack=[]
    d=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            stack.append(i)
            d[i]=1
    while stack:
        v=stack.pop()
        for x in edge1[v]:
            d[x]=max(d[x],d[v]+1)
            stack.append(x)
    print(max(d))
        

    

        
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=[[] for _ in range(N)]
    for i in range(N):
        A[i]=deque(list(map(lambda x: int(x)-1,input().split())))
    days=1
    c=0
    pre=[]
    tmp=[]
    for i in range(N):
        if A[i] and A[A[i][0]][0]==i:
            tmp.append(i)
            tmp.append(A[i][0])
    tmp=list(set(tmp))
    for i in tmp:
        A[i].popleft()
        c+=1
    pre=tmp
    if c<N*(N-1):
        while c<N*(N-1):
            tmp=[]
            for i in pre:
                if A[i] and A[A[i][0]][0]==i:
                    tmp.append(i)
                    tmp.append(A[i][0])
            tmp=list(set(tmp))
            for i in tmp:
                A[i].popleft()
                c+=1
            pre=tmp
            days+=1
            if days>N*(N-1)//2:
                print(-1)
                exit()
    print(days)
                
            
        
    
        
        

    

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

import time
N = int(input())
s = [str(input()) for i in range(N)]

e = []
f = [0] * N
j = 0
ans = 0
for i in range(N):
  s[i] = "".join(sorted(s[i]))
#print(s)

for i in range(N):
  if s[i] not in e:
    e.append(s[i])
    f[j] = 1
    j += 1
  else:
    a = e.index(s[i])
    ans += f[a]
    f[a] += 1

print(ans)

### FIXED CODE ###

import time
N = int(input())
s = [str(input()) for i in range(N)]

j = 0
ans = 0
for i in range(N):
  s[i] = "".join(sorted(s[i]))
#print(s)

s = sorted(s)
tango = "yeeeh"
x = 0
#print(s)
for i in range(N):
  if s[i] == tango:
    x += 1
  else:
    ans += x * (x + 1) //2
    x = 0
  tango = s[i]
ans += x * (x + 1) //2

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

import sys
import itertools


x = int(input())
for a in itertools.count():
    for b in itertools.count():
        a5b5 = a**5 + b**5
        if a5b5 == x:
            print(a, -b)
            sys.exit(0)
        if x < a5b5:
            break

### FIXED CODE ###

import sys
import itertools


x = int(input())
for b in itertools.count():
    for a in itertools.count(b):
        a5b5 = a**5 + b**5
        if a5b5 == x:
            print(a, -b)
            sys.exit(0)
        a5b5 = a**5 - b**5
        if a5b5 == x:
            print(a, b)
            sys.exit(0)
        if x < a5b5:
            break
### BUGGY CODE ###

# coding: utf-8

N = int(input())
A = [int(x) for x in input().split(" ")]

k = 0
l = -1

for i in range(1, N+1):
    templ = l
    for j in range(k, N):
        if A[j] == i:
            k = j
            l = i
    if templ == l:
        break

if l == -1:
    print(-1)
else:
    print(N - l)

### FIXED CODE ###

# coding: utf-8
N = int(input())
A = [int(x) for x in input().split(" ")]

# j 番目からリストの最後までの間で x があるか確かめ、ある場合は最小のインデックスを返し、ない場合は "n" を返す
def search(A, j, N, x):
    for i in range(j, N):
        if A[i] == x:
            return i
    return "n"


k = 0
tempk = -1
for i in range(1, N+1):
    k = search(A, k, N, i)
    if k == "n":
        break
    else:
        tempk = k

if tempk == -1:
    print(tempk)
else:
    print(N - A[tempk])
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[0]*(n+1)
for i in range(n):
    l[i]+=a[i]
    l[i+1]+=l[i]
c=0
for i in range(n):
    for j in range(i,n):
        if i==0:
            if l[j]%m==0:c+=1
        else:
            if (l[j]-l[i-1])%m==0:c+=1
print(c)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter
n,m=map(int,input().split())
s=[0]+list(map(lambda x:x%m,list(accumulate(list(map(int,input().split()))))))
ans=0
for i in Counter(s).values():
    ans+=(i*(i-1)//2)
print(ans)
### BUGGY CODE ###

s = input()
mod = int(1e9 + 7)
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1

if len(s)==1:
    print(dp[5]%mod)
    exit()
else:
    mul = 10
    for i in reversed(range(len(s)-1)):
        nextdp = [0] * 13
        if s[i]=="?":
            for j in range(10):
                for k in range(13):
                    l = (j*mul+k) % 13
                    nextdp[l] += dp[k]
        else:
            for k in range(13):
                l = (int(s[i])*mul+k) % 13
                nextdp[l] += dp[k]
        mul *= 10
        dp = nextdp
    print(dp[5]%mod)
    exit()

### FIXED CODE ###

s = input()
mod = 10**9 + 7
N = len(s)
if s[-1]=="?":
    dp = [1]*13
    dp[10:13] = [0,0,0]
else:
    dp = [0]*13
    dp[int(s[-1])] = 1
if N==1:
    print(dp[5])
    exit()
else:
    mul = 10
    for i in reversed(range(N-1)):
        nextdp = [0] * 13
        if s[i]=="?":
            for j in range(10):
                for k in range(13):
                    l = (j*mul+k) % 13
                    nextdp[l] += dp[k]
                    nextdp[l] %= mod
        else:
            for k in range(13):
                l = (int(s[i])*mul+k) % 13
                nextdp[l] += dp[k]
                nextdp[l] %= mod
        mul *= 10
        mul %= 13
        dp = nextdp
    print(dp[5])
    exit()
### BUGGY CODE ###


# -*- coding: utf-8 -*-
S = input()
Q = int(input())

rev = False

for q in range(Q):
    i = input()
    if i[0] == "1":
        rev = not rev
    elif not rev and i[2] == "1" or rev and i[2] == "2":
        S = i[4] + S
    else:
        S = S + i[4]

if rev:
    S = S[::-1]
print(S)


### FIXED CODE ###


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

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

rev = False
S1 = ['0'] * Q
S1i = 0
S2 = ['0'] * Q
S2i = 0

for q in range(Q):
    i = input()
    if i[0] == "1":
        rev = not rev
    elif not rev and i[2] == "1" or rev and i[2] == "2":
        # S = i[4] + S
        S1[S1i] = i[4]
        S1i += 1
    else:
        # S = S + i[4]
        S2[S2i] = i[4]
        S2i += 1

S1 = S1[0:S1i]
S2 = S2[0:S2i]
S1 = S1[::-1]

S = ''.join(''.join(S1) + S + ''.join(S2))

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

print(S)
### BUGGY CODE ###

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

a = ['']*n
def rev(t):
    m = len(t)
    b = ['']*m
    for j in range(m):
        b[j] = t[m-j-1]
    c = ''
    for k in range(len(b)):
        c += b[k]
    return c

for i in range(n):
    a[i] = input()
    if a[i] == '1':
        s = rev(s)
    else:
        p,q,r = list(a[i].split())
        if q == '1':
            s = r+s
        else:
            s = s+r
print(s)


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
t = 0
for i in range(Q):
    query = input().split()
    if int(query[0]) == 1:
        t += 1
    else:
        query[1] = int(query[1])
        if t % 2 == 1:
            if query[1] == 1:
                query[1] = 2
            else:
                query[1] = 1
        if query[1] == 1:
            S.appendleft(query[2])
        else:
            S.append(query[2])
if t % 2 == 1:
    S.reverse()
print("".join(S))
### BUGGY CODE ###

K = int(input())
def gcd(x,y):
    if x < y:
        x,y = y,x
    if y == 0:return x
    return gcd(y,x%y)
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(i,gcd(j,k))
print(ans)

### FIXED CODE ###

import math
 
k = int(input()) + 1
ans = 0
 
for a in range(1, k):
    for b in range(1, k):
        d = math.gcd(a, b)
        for c in range(1, k):
            ans += math.gcd(d, c)
 
print(ans)
### BUGGY CODE ###

n,A,B = map(int,input().split())
s = list(str(input()))
p =[]
for i in range(0,n):
  if s[i] =="a":
    if A+B>len(p):
      p.append(s[i])
      print("Yes")
    else:
      print("No")
  elif s[i] =="b":
    if A+B>len(p) and p.count("b")<B:
      p.append(s[i])
      print("Yes")
    else:
      print("No")
  else:
    print("No")

### FIXED CODE ###

n,a,b = map(int,input().split(" "))
s = input()
accept = a+b
for i in range(len(s)):
  if s[i] == "c":
    print("No")
  elif accept <= 0:
    print("No")
  elif s[i] == "a":
    print("Yes")
    accept -= 1
  elif s[i] == "b" and b > 0:
    print("Yes")
    b -= 1
    accept -= 1
  else:
    print("No")
### BUGGY CODE ###

import sys
import math
from  collections import defaultdict

sys.setrecursionlimit(1000000000)

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = map(int, input().split())
	dp = {}
	ans = knapsack(wgt, val, 0, n, dp, w)
	print(ans)

def knapsack(wgt, val, i, n, dp, w):
	if (i, w) in dp:
		return dp[(i, w)]
	elif i >= n:
		return 0
	else:
		dp[(i, w)] = knapsack(wgt, val, i + 1, n, dp, w)
		if wgt[i] <= w:
			dp[(i, w)] = max(dp[(i, w)], val[i] + knapsack(wgt, val, i + 1, n, dp, w - wgt[i]))
		return dp[(i, w)]


if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)


### FIXED CODE ###

import sys
import math
from  collections import defaultdict


# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve(test):
	n, w = map(int, input().split())
	val = [None] * n
	wgt = [None] * n
	for i in range(n):
		wgt[i], val[i] = map(int, input().split())
	dp = [[0 for j in range(w + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			dp[i][j] = dp[i - 1][j]
			if wgt[i - 1] <= j:
				dp[i][j] = max(dp[i][j], val[i - 1] + dp[i - 1][j - wgt[i - 1]])
	ans = dp[-1][-1]
	print(ans)



if __name__ == "__main__":
	test_cases = 1
	for t in range(1, test_cases + 1):
		solve(t)
### BUGGY CODE ###

N=int(input())
a=str(input())
ans=0
for i in range(0,1000):
  if i<10:
    n='0'+'0'+str(i)
  elif i<100:
    n='0'+str(i)
  else:
    n=str(i)
  v1,v2,v3=n[0],n[1],n[2]
  j=0
  while j+1<=N-2 and a[j]!=v1:
    j+=1
  if j>N-2:
    break
  k=j+1
  while k+1<=N-1 and a[k]!=v2:
    k+=1
  if k>N-1:
    break
  l=k+1
  while l+1<=N and a[l]!=v3:
    l+=1
  if l<=N-1:
    ans+=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
s=list(str(input()))
cnt=0
index={}
for i in range(n):
  v=s[i]
  if v not in index.keys():
    index[v]=[]
  index[v].append(i)
for i in range(1000):
  i_str='0'*(3-len(str(i)))+str(i)
  x,y,z=i_str[0],i_str[1],i_str[2]
  if x in index.keys() and y in index.keys() and z in index.keys():
    a=index[x][0]
    v=bisect.bisect_left(index[y],a+1)
    if v<len(index[y]):
      b=index[y][v]
      if b<=a or b>=n:
        pass
      else:
        v=bisect.bisect_left(index[z],b+1)
        if v<len(index[z]):
          c=index[z][v]
          if c<=b or c>=n:
            pass
          else:
            cnt+=1
print(cnt)
### BUGGY CODE ###

s = input()
t = input()
len_s = len(s)
len_t = len(t)

# dp[i][j] = sのi-1文字目,tのj-1文字目まででの最長共通部分列の長さ
dp = [[0]*(len_t+1) for i in range(len_s+1)]
# 遷移記録用（0,1が両方-1ならその文字を追加する）
prevs = [[0]*(len_t+1) for i in range(len_s+1)]
prevt = [[0]*(len_t+1) for i in range(len_s+1)]
for i in range(len_s+1) :
    for j in range(len_t+1) :
        # どちらかが空文字列の場合
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
        # i-1文字目とj-1文字目が一致する場合
        if s[i-1] == t[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            prevs[i][j] = -1
            prevt[i][j] = -1
        # 一致しない場合
        else : 
            if dp[i-1][j] >= dp[i][j-1] :
                if dp[i-1][j] > dp[i][j] :
                    dp[i][j] = dp[i-1][j]
                    prevs[i][j] = -1
            else :
                if dp[i][j-1] > dp[i][j] :
                    dp[i][j] = dp[i][j-1]
                    prevt[i][j] = -1

ans = 0
si = len_s
ti = len_t
ans = ['' for i in range(dp[len_s][len_t])]
index = dp[len_s][len_t] - 1
# 遷移をたどっていく
for i in range(10**18) :
    if prevs[si][ti] == -1 and prevt[si][ti] == -1 :
        ans[index] = s[si-1]
        index -= 1
    st = si ; tt = ti
    si += prevs[st][tt] ; ti += prevt[st][tt]
    if si == st and ti == tt :
        break

print(*ans, sep='')

### FIXED CODE ###

s = input()
t = input()
len_s = len(s)
len_t = len(t)

# dp[i][j] = sのi-1文字目,tのj-1文字目まででの最長共通部分列の長さ
dp = [[0]*(len_t+1) for i in range(len_s+1)]
# 遷移記録用（0,1が両方-1ならその文字を追加する）
prevs = [[0]*(len_t+1) for i in range(len_s+1)]
prevt = [[0]*(len_t+1) for i in range(len_s+1)]
for i in range(len_s+1) :
    for j in range(len_t+1) :
        # どちらかが空文字列の場合
        if i == 0 or j == 0 :
            dp[i][j] = 0
            continue
        # i-1文字目とj-1文字目が一致する場合
        if s[i-1] == t[j-1] :
            dp[i][j] = dp[i-1][j-1] + 1
            prevs[i][j] = -1
            prevt[i][j] = -1
        # 一致しない場合
        else : 
            if dp[i-1][j] >= dp[i][j-1] :
                if dp[i-1][j] > dp[i][j] :
                    dp[i][j] = dp[i-1][j]
                    prevs[i][j] = -1
            else :
                if dp[i][j-1] > dp[i][j] :
                    dp[i][j] = dp[i][j-1]
                    prevt[i][j] = -1

ans = 0
si = len_s
ti = len_t
ans = ['' for i in range(dp[len_s][len_t])]
index = dp[len_s][len_t] - 1
# 遷移をたどっていく
for i in range(10**18) :
    if prevs[si][ti] == -1 and prevt[si][ti] == -1 :
        ans[index] = s[si-1]
        index -= 1
    st = si ; tt = ti
    si += prevs[st][tt] ; ti += prevt[st][tt]
    if si == st and ti == tt :
        break

print(*ans, sep='')
### BUGGY CODE ###

n,m=map(int,input().split(" "))
ans=range(1,n+1)
for i in range(m):
	l,r=map(int,input().split(" "))
	ans=list(set(ans)&set(range(l,r+1)))
if len(ans)>n:
	print(n)
else:
	print(len(ans))

### FIXED CODE ###

n,m=map(int,input().split(" "))
l_init,r_init=map(int,input().split(" "))
ans_l=l_init
ans_r=r_init
isPossible=True
for i in range(m-1):
	l,r=map(int,input().split(" "))
	isupdated=False
	next_ans_l=ans_l
	next_ans_r=ans_r
	if ans_l <= l and l <= ans_r:
		next_ans_l=l
		isupdated=True
	if ans_l <= r and r <= ans_r:
		next_ans_r=r
		isupdated=True
	if l <= ans_l and ans_r <= r:
		isupdated=True
	if not isupdated:
		isPossible=False
		break
	ans_l=next_ans_l
	ans_r=next_ans_r
ans=ans_r-ans_l
if isPossible:
	print(ans+1)
else:
	print(0)
### BUGGY CODE ###

from collections import deque


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)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
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]

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

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        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))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        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))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    from collections import deque

    H, W = [int(item) for item in input().split()]
    Ch, Cw = [int(item)-1 for item in input().split()]
    Dh, Dw = [int(item)-1 for item in input().split()]
    grid = [input() for _ in range(H)]
    max_num = 10**6
    fp = [[max_num] * W for _ in range(H)]

    que = deque([[Ch, Cw, 0]])
    fp[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 que:
        y, x, w_num = que.popleft()

        for dy, dx in walk:
            ny = y + dy
            nx = x + dx

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > w_num:
                que.appendleft([ny, nx, w_num])
                fp[ny][nx] = w_num

        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            nw = w_num +1

            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and grid[ny][nx] == '.' and fp[ny][nx] > nw:
                que.append([ny, nx, nw])
                fp[ny][nx] = nw

    if fp[Dh][Dw] != max_num:
        print(fp[Dh][Dw])
    else:
        print(-1)

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

N=int(input())
S=str(input())
#W=左
#E=右
ans=[]
for i in range(1,N-1):
    count=0
    ans.append(S[0:i-1].count("W")+S[i:N].count("E"))


print(min(ans))


### FIXED CODE ###

N=int(input())
S=str(input())
#W=左
#E=右
ans=[]
count=0
#一番左
for i in range(1,N):
    
    if S[i]=="E":
        count+=1    
        
        
ans.append(count)


for i in range(1,N):
    
    if S[i-1]=="W":
        count+=1
    if S[i]=="E":
        count-=1

    ans.append(count)

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

n = input()

total = 0
for i in range(len(n)):
	total += int(n)

if total % 9 == 0:
	print('Yes')
else:
	print('No')

### FIXED CODE ###

n = list(map(int, list(input())))

total = sum(n)

if total % 9 == 0:
	print('Yes')
else:
	print('No')
### BUGGY CODE ###

n = int(input())
ans_a = 0
ans_b = 0
ans_c = 0
for b in range(1, 3501):
    for c in range(1, 3501):
        sita = 4 * b * c - (n * (b + c))
        if sita <= 0:
            continue
        ue = n * b * c
        if ue % sita == 0:
            ans_a, ans_b, ans_c = ue // sita, b, c
            break
print(ans_a, ans_b, ans_c)

### FIXED CODE ###

n = int(input())
ans_a = 0
ans_b = 0
ans_c = 0
for b in range(1, 3501):
    for c in range(1, 3501):
        sita = 4 * b * c - (n * (b + c))
        if sita <= 0:
            continue
        ue = n * b * c
        if ue % sita == 0:
            ans_a, ans_b, ans_c = ue // sita, b, c
            break
print(ans_a, ans_b, ans_c)
### BUGGY CODE ###

H, W = map(int, input().split())
MAP = [[] for _ in range(H)]
L = [[[] for h in range(W)] for _ in range(H)]
R = [[[] for h in range(W)] for _ in range(H)]
D = [[[] for h in range(W)] for _ in range(H)]
U = [[[] for h in range(W)] for _ in range(H)]

for i in range(H):
    MAP[i] = list(input())

for i in range(H):
    for j in range(W):
        if MAP[i][j] == "#":
            L[i][j] = 0
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j - 1] + 1

        if MAP[i][W - j - 1] == "#":
            R[i][W - j - 1] = 0
        elif j == 0:
            R[i][W - j - 1] = 1
        else:
            R[i][W - j - 1] = R[i][W - j] + 1

for j in range(W):
    for i in range(H):
        if MAP[i][j] == "#":
            U[i][j] = 0
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i - 1][j] + 1

        if MAP[H - i - 1][j] == "#":
            D[H - i - 1][j] = 0
        elif i == 0:
            D[H - i - 1][j] = 1
        else:
            D[H - i - 1][j] = D[H - i][j] + 1
result = 0
for i in range(H):
    for j in range(W):
        result = max(result, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

print(result)


### FIXED CODE ###

H, W = map(int, input().split())
MAP = [list(input()) for _ in range(H)]
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if MAP[i][j] == "#":
            L[i][j] = 0
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i] [j - 1] + 1

        if MAP[i][W - j - 1] == "#":
            R[i][W - j - 1] = 0
        elif j == 0:
            R[i][W - j - 1] = 1
        else:
            R[i][W - j - 1] = R[i][W - j] + 1

for j in range(W):
    for i in range(H):
        if MAP[i][j] == "#":
            U[i][j] = 0
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i - 1][j] + 1

        if MAP[H - i - 1][j] == "#":
            D[H - i - 1][j] = 0
        elif i == 0:
            D[H - i - 1][j] = 1
        else:
            D[H - i - 1][j] = D[H - i][j] + 1
result = 0
for i in range(H):
    for j in range(W):
        result = max(result, U[i][j] + D[i][j] + L[i][j] + R[i][j] - 3)

print(result)
### BUGGY CODE ###

N = int(input())
a = list(map(str,input().split()))
ans = []

if N %2 == 0:
    for i in range(N):
        if N%2 == 1:
            ans.append(a[i])
        else:
            ans.insert(0,a[i])
        ans.reverse()
    ans.reverse()
else:
    for i in range(N):
        if N%2 == 1:
            ans.append(a[i])
        else:
            ans.insert(0,a[i])
        ans.reverse()


print(" ".join(ans))

### FIXED CODE ###

n = int(input())
a = list(map(str,input().split()))
odd = []
even = []

for i in range(0,n,2):
    odd.append(a[i])
for i in range(1,n,2):
    even.append(a[i])

if n%2 == 0:
    even.reverse()
    ans = even + odd
else:
    odd.reverse()
    ans = odd + even
print(" ".join(ans))
### 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(1,N):
    for j in range(max(0,i-K),i):
        # print(h[j],':',h[i])
        dp[i] = min(dp[i], dp[j]+abs(h[j]-h[i]))
    # print(dp)
print(dp[-1])


### FIXED CODE ###

import numpy as np

N,K = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.full(N,10**10)
dp[0] = 0
for i in range(1,N):
    start = max(0,i-K)
    dp[i] = np.min(dp[start:i]+np.abs(h[i]-h[start:i]))
print(int(dp[-1]))
### BUGGY CODE ###

s = input().strip()

DIV = 10**9 + 7
digit = 1
log = []

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log.append([int(t < 10) for t in range(13)])
        else:
            log.append([int(t == int(c)) for t in range(13)])
    else:
        log.append([0 for t in range(13)])
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in enumerate(log[i - 1]):
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt)
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in enumerate(log[i - 1]):
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt)
        log[i] = [v % DIV for v in log[i]]
    digit = (digit * 10) % 13

print(log[len(s) - 1][5])

### FIXED CODE ###

s = input().strip()

DIV = 10**9 + 7
new = list(range(13))
old = None

c = s[-1]
if c == '?':
    old = [int(t < 10) for t in range(13)]
else:
    c = int(c)
    old = [int(t == c) for t in range(13)]

digit = 10
for i, c in enumerate(reversed(s[:-1])):
    for j in range(13):
        new[j] = 0
    if c == '?':
        for m in range(10):
            for mod, cnt in enumerate(old):
                shifted = (mod + m * digit) % 13
                new[shifted] += cnt
    else:
        c = int(c)
        for mod, cnt in enumerate(old):
            shifted = (mod + c * digit) % 13
            new[shifted] += cnt
    for j in range(13):
        new[j] %= DIV
    new, old = old, new
    digit = (digit * 10) % 13

print(old[5])