Harryxun/stf_run huggingface dataset:
from collections import deque
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    a-=1; b-=1
    g[a].append((b, c))
    g[b].append((a, c))
q, k = map(int, input().split())

# 前処理
dist = [-1] * n

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in g[st]:
        if dist[to] >= 0: continue
        dfs(to, depth+c)

dfs(k-1, 0)

for i in range(q):
    x, y = map(int, input().split())
    x-=1; y-=1
    print(dist[x]+dist[y])



### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)
n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())
    a-=1; b-=1
    g[a].append((b, c))
    g[b].append((a, c))
q, k = map(int, input().split())

# 前処理
dist = [-1] * n

def dfs(st, depth=0):
    dist[st] = depth
    for to, c in g[st]:
        if dist[to] >= 0: continue
        dfs(to, depth+c)

dfs(k-1, 0)

for i in range(q):
    x, y = map(int, input().split())
    x-=1; y-=1
    print(dist[x]+dist[y])
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import random


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
MEIJI = [[0] * W for i in range(H)]

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            MEIJI[i][j] = 1


def findStart():
    while(True):
        x, y = random.randint(H), random.randint(W)
        if MEIJI[x][y] == 0:
            return x, y

    return False


def bfs(H, W, sx, sy):
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

if l < 0:
    l = 0

print(l)


### FIXED CODE ###

import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import random


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
MEIJI = [[0] * W for i in range(H)]

for i in range(H):
    a = input()
    for j in range(len(a)):
        if a[j] == "#":
            MEIJI[i][j] = 1


def findStart():
    for x in range(H):
        for y in range(W):
            if MEIJI[x][y] == 0:
                return x, y

    return False


def bfs(H, W, sx, sy):
    if MEIJI[sx][sy] == 1:
        return 0, 0, 0, -1
    d = [[-1] * W for i in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque([])
    q.append((sx, sy))
    d[sx][sy] = 0

    mx = -1
    gx, gy = -1, -1
    while(len(q) != 0):
        x, y = q.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if (0 <= nx and nx <= (H-1) and 0 <= ny and ny <= (W-1) and MEIJI[nx][ny] == 0 and d[nx][ny] == -1):
                q.append((nx, ny))
                l = d[x][y] + 1
                d[nx][ny] = l

                if l > mx:
                    gx, gy = nx, ny
                    mx = l
    return d, gx, gy, mx


mx = 0
for x in range(H):
    for y in range(W):
        _, _, _, l = bfs(H, W, x, y)
        if l > mx:
            mx = l

print(mx)
exit()

sx, sy = findStart()
_, x, y, _ = bfs(H, W, sx, sy)
_, _, _, l = bfs(H, W, x, y)

if l < 0:
    l = 0

print(l)
n, k = map(int, input().split())

for i in range(k):
    d[i] = int(input())
    a[i] = list(map(int, input().split()))

for i in range(n):
    if all((x != i for x in a)):
        print(i)

### FIXED CODE ###

n, k = map(int, input().split())

d = [0]*k
a = [0]*k

for i in range(k):
    d[i] = int(input())
    a[i] = list(map(int, input().split()))

k = 0

b = sum(a, [])
    
for i in range(n):
    if i+1 not in b:
        k = k + 1

print(k)
N, Q = map(int, input().split())
S=list(input())
list=[]
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        list.append[i]
lis=[]
count=0
for j in range(Q):
    l, r = map(int, input().split())
    for h in range(l-1, r+1):
        lis.append(h)
        count+=len(set(list) & set(lis))
print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

ans = [0]*N
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        ans[i+1] += (ans[i]+1)
    else:
        ans[i+1] = ans[i] 

for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])
S = input()
cnt = S[2:-1].count('C')

if s in S[1:]:
    if s.isupper() and s != 'C':
        print('WA')
        break
else:
    if S[0] == 'A' and cnt == 1:
        print('AC')
    else:
        print('WA')

### FIXED CODE ###

S = input()
cnt = S[2:-1].count('C')
 
for s in S[1:]:
    if s.isupper() and s != 'C':
        print('WA')
        break
else:
    if S[0] == 'A' and cnt == 1:
        print('AC')
    else:
        print('WA')
import heapq

mod = 998244353

def dfs(v: int, child) -> int:
  res = 1
  for u in child[v]:
    res = res * dfs(u) % mod
  return res + 1

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort()
child = [[] for _ in range(n)]

root = []
for i in range(n-1, -1, -1):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      child[i].append(r[1])
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
for r in root:
  count = count * dfs(r[1], child) % mod
print(count)

### FIXED CODE ###

import heapq

mod = 998244353

n = int(input())
robot = [tuple(map(int, input().split())) for _ in range(n)]
robot.sort(reverse=True)
parent = list(range(n))

root = []
for i in range(n):
  x, d = robot[i]
  while root:
    r = heapq.heappop(root)
    if r[0] < x + d:
      parent[r[1]] = i
    else:
      heapq.heappush(root, r)
      break
  heapq.heappush(root, (x, i))
  
count = 1
dp = [1] * n
for i in range(n):
  p = parent[i]
  if p == i:
    count = count * (dp[i] + 1) % mod
  else:
    dp[p] = dp[p] * (dp[i] + 1) % mod
print(count)
import numpy as np

n = int(input())
f = np.zeros((n, 10), dtype=np.int64)
p = np.zeros((n, 11), dtype=np.int64)

for i in range(n):
  tmp = list(map(int, input().split()))
  for j in range(10):
      f[i][j] = tmp[j]
for i in range(n):
  tmp = list(map(int, input().split()))
  for j in range(11):
    p[i][j] = tmp[j]

r = -1e18
for b in range(1, 1<<10):
  s = 0
  for i in range(n):
    c = 0
    for j in range(10):
      if (b >> j) & 1 == 1 and f[i][j]:
        c += 1
    s += p[i][c]
  if r < s:
    r = s

print(r)


### FIXED CODE ###

import numpy as np

n = int(input())
f = np.zeros((n, 10), dtype=np.int64)
p = np.zeros((n, 11), dtype=np.int64)

for i in range(n):
  tmp = list(map(int, input().split()))
  for j in range(10):
      f[i][j] = tmp[j]
for i in range(n):
  tmp = list(map(int, input().split()))
  for j in range(11):
    p[i][j] = tmp[j]

r = -1e18
for b in range(1, 1<<10):
  s = 0
  for i in range(n):
    c = 0
    for j in range(10):
      if (b >> j) & 1 == 1 and f[i][j]:
        c += 1
    s += p[i][c]
  if r < s:
    r = s

print(r)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = list(input().strip())
K = int(input())

L = [i for i in S]


if len(S) == 1:
    if K == 1:
        print(0)
    else:
        print(K//2)
        print(S[2])
    sys.exit()

count = 0
tmp = S[0]
for i in range(1, len(S)):
    if S[i] == tmp:
        count += 1
        S[i] = "A"
        tmp = S[i]
    else:
        tmp = S[i]

count2 = 0
if S[0] == S[-1]:
    L[0] = "A"
    count2 += 1
    tmp = L[0]
    for i in range(1, len(L)):
        if L[i] == tmp:
            count2 += 1
            L[i] = "A"
            tmp = L[i]
        else:
            tmp = L[i]
    print((K//2)*count2 + (K//2+K%2)*count)
else:
    print(count * K)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = list(input().strip())
K = int(input())

L = [i for i in S]


if len(S) == 1:
    if K == 1:
        print(0)
    else:
        print(K//2)
    sys.exit()

count = 0
tmp = S[0]
for i in range(1, len(S)):
    if S[i] == tmp:
        count += 1
        S[i] = "A"
        tmp = S[i]
    else:
        tmp = S[i]

count2 = 0
if S[0] == S[-1]:
    L[0] = "A"
    count2 += 1
    tmp = L[0]
    for i in range(1, len(L)):
        if L[i] == tmp:
            count2 += 1
            L[i] = "A"
            tmp = L[i]
        else:
            tmp = L[i]
    if L[-1] == "A":
        print((K//2)*count2 + (K//2+K%2)*count)
    else:
        print(count + (K-1)*count2)
else:
    print(count * K)
N = int(input())
A = list(map(int, input().split()))
H = [0] * 3
P = 1
for i in A:
	P *= H.count(i)
	P %= 1000000007
	H[H.index(i)] += 1
print(P)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
H = [0] * 3
P = 1
for i in A:
	if H.count(i) == 0:
		P = 0
		break
	P *= H.count(i)
	P %= 1000000007
	H[H.index(i)] += 1
print(P)
n = int(input())
a = [2,4,5,7,9]
b = [0,1,6,8]

if n[-1] in a:
  print('hon')
elif n[-1] in b:
  print('pon')
else:
  print('bon')

### FIXED CODE ###

n = input()
a = ['2','4','5','7','9']
b = ['0','1','6','8']
if n[-1] in a:
    print('hon')
elif n[-1] in b:
    print('pon')
else:
    print('bon')
#coding:utf-8
        #初期化
        key=[0]*101
        flag = 0;
        #オイラー路：すべての頂点のうち、次数が奇数であるものがちょうど２つ(入口と出口)
        while 1:
            input = map(int, raw_input().split())
            if(input[0] == 0 and input[1] == 0):
                break
            key[input[0]]+=1
            key[input[1]]+=1

        for v in key:
            if v%2 == 1:
                flag+=1
        if(flag == 2):
            print "OK"
        else:
            print "NG"

### FIXED CODE ###

#coding:utf-8
while 1:
    try:
        #初期化
        key=[0]*101
        #オイラー路：すべての頂点のうち、次数が奇数であるものがちょうど２つ(入口と出口)
        while 1:
            input = map(int, raw_input().split())
            if(input[0] == 0 and input[1] == 0):
                break
            key[input[0]]+=1
            key[input[1]]+=1

        if(key[1]%2 == 1 and key[2]%2==1 and len(filter(lambda x:x%2==1,key[3:]))==0):
            print "OK"
        else:
            print "NG"
    except:
        break
import math

A=int(input())
B=int(input())
H=int(input())
M=int(input())
if 1<=A<=1000 and 1<=B<=1000 and 0<=H<=11 and 0<=M<=59:
    hw=(2*math.pi)/12
    mw=(2*math.pi)/60
    aw=hw*H+(hw/60)*M
    bw=mw*M
    rad=abs(bw-aw)
    print(math.sqrt(A**2+B**2-2*A*B*math.cos(rad)))
else: 
    print("各値の条件は次の通り:1<=A,B<=1000,0<=H<=11,0<=M<=59")
    print("あなたの入力:A={},B={},H={},M={}".format(A,B,H,M))

### FIXED CODE ###

import math

A,B,H,M =map(int, input().split())
if 1<=A<=1000 and 1<=B<=1000 and 0<=H<=11 and 0<=M<=59:
    hw=(2*math.pi)/(12*60*60) #時針の角速度[rad/s]
    mw=(2*math.pi)/(60*60) #分針の角速度[rad/s]
    time_h=H*60*60 #Hour時間[s] 
    time_m=M*60 #Min時間[s]
    aw=hw*(time_h+time_m) #Arad[rad] #最後の鬼門だった！！なるほどね！40min経ってる間に時針も進んでるから。。
    bw=mw*time_m #Brad[rad]
    rad=abs(bw-aw)
    # 正弦定理で出力結果を得る(a^2=b^2+c^2-2bccosθ)
    print(math.sqrt(A**2+B**2-2*A*B*math.cos(rad)))
    #確認用
    #print(time_h,time_m,aw,bw,rad) 
else: 
    print("各値の条件は次の通り:1<=A,B<=1000,0<=H<=11,0<=M<=59")
    print("あなたの入力:A={},B={},H={},M={}".format(A,B,H,M))
n,k = map(int,input().split())
if N>=2K-1:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n,k = map(int,input().split())
if n>=2*k-1:
  print("YES")
else:
  print("NO")
n,m = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]

num = 0
ct = 0
while num <= m:
    ct +=1
    num += l[ct-1]
    
print(ct)

### FIXED CODE ###

n,m = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]

num = 0
ans = 1
for i in l:
    num += i
    if num > m:
        break
    else:
        ans +=1
    
print(ans)
N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

aaa = [int(input()) for _ in range(N)]

sum_now = 0
DP = [[0] * (sum(aaa)+1) for i in range(N)]
DP2 = [[0] * (sum(aaa)+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	for j in range(sum(aaa)):
		DP[i][j] += DP[i-1][j] * 2
		DP[i][j] %= mod
		DP[i][j + a] += DP[i-1][j]

		DP2[i][j] += DP2[i-1][j]
		DP2[i][j] %= mod
		DP2[i][j + a] += DP2[i-1][j]

	sum_now += a

# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum(aaa) %2 == 0):
	num_too_long -= DP2[N-1][int(sum(aaa) /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )


### FIXED CODE ###

N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

aaa = [int(input()) for _ in range(N)]
sum_aaa = sum(aaa)

sum_now = 0
DP = [[0] * (sum_aaa+1) for i in range(N)]
DP2 = [[0] * (sum_aaa+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 1):

		if (j >= a):
			DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-a]
		else:
			DP[i][j] = DP[i-1][j]*2

		while (DP[i][j] > mod):
			DP[i][j] -= mod

	for j in range(min(sum_now + 1, int(sum_aaa /2)+1)):
		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

		while (DP2[i][j] > mod):
			DP2[i][j] -= mod

# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum_aaa %2 == 0):
	num_too_long -= DP2[N-1][int(sum_aaa /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )
n=input()
print("No"if int(n)%sum(int(i)for i in n) else"Yes")

### FIXED CODE ###

s=input()
print(s.count("+")-s.count("-"))
def solve(string):
    ins = string.split("\n")
    h, w = map(int, ins[0].split(" "))
    a = [list(map(int, _i.split(" "))) for _i in ins[1:]]
    move = []
    for j in range(h):
        for i in range(w):
            if a[j][i] % 2 != 0:
                if i < w - 1:
                    a[j][i + 1] += 1
                    move.append("{} {} {} {}".format(j + 1, i + 1, j + 1, i + 2))
                elif j < h - 1:
                    a[j][i] -= 1
                    a[j + 1][i] += 1
                    move.append("{} {} {} {}".format(j + 1, i + 1, j + 2, i + 1))
    return "{}\n{}".format(len(move), "\n".join(move))


if __name__ == '__main__':
    line = input()
    tmp = [line]
    for _ in range(int(line[0])):
        tmp.append(input())
    print(solve('\n'.join(tmp)))


### FIXED CODE ###

h,w = map(int,input().split())
a = []
for i in range(h):
    tmp = list(map(lambda x:int(x)%2,input().split()))
    a.append(tmp)
result = []
 
for i in range(h):
    for j in range(w-1):
        if a[i][j] == 1:
            #a[i][j] == 0
            a[i][j+1] = 1 ^ a[i][j+1]
            result.append((i+1,j+1,i+1,j+2)) 
for i in range(h-1):
    if a[i][w-1] == 1:
        a[i+1][w-1] = 1 ^ a[i+1][w-1]
        result.append((i+1,w,i+2,w))
print(len(result))
for row in result:
    print("{} {} {} {}".format(row[0],row[1],row[2],row[3]))
from math import factorial
n, m, k = map(int, input().split())
MOD = 998244353
ans = 0

def nck(q, r):
    a = (factorial(q)) / (factorial(r)) / (factorial(q - r))
    return a%MOD


for i in range(k+1):
    ans += (m * nck(n - 1, i) * ((m - 1)**(n - 1 - i)%MOD))
    
print(int(ans%MOD))

### FIXED CODE ###

n, m, k = map(int, input().split())
MOD = 998244353
ans = 0
c = 1

for i in range(k + 1):
    ans += (((m * pow(m - 1, n - i - 1, MOD)) % MOD) * c) % MOD
    ans %= MOD
    c = (c * (n - 1 - i) * pow(i + 1, MOD - 2, MOD)) % MOD
    
    
print(ans%MOD)
a, b = int(input().split())
x = int((a+b)/2)
print(x)

### FIXED CODE ###

import math
a, b = map(int,input().split())
x = (a + b)/2
print(math.ceil(x))
def a(s):
  if s == 1:
    return s
  return s + a(s-1) 

print(a(int(input()))

### FIXED CODE ###

def a(s):
  if s == 1:
    return s
  return s + a(s-1) 

print(a(int(input())))
a=int(input())
b=0
for i in range(a):
  c=input().split()
  if c[1]=='BTC':
    b+=(float)c[0]*380000.0
  else:
    b+=(int)c[0]
print(b)
    
    
  
  


### FIXED CODE ###

a=input().split('/')
if int(a[1])<=4:
  print("Heisei")
else:
  print("TBD")
s=input()
n=0
while s[n]!=s[n+1]:
    n+=1
    print('Good')
else:
    print('Bad')


### FIXED CODE ###

s=input()
if s[0]!=s[1] and s[1]!=s[2] and s[2]!=s[3]:
    print('Good')
else:
    print('Bad')
a=input()
l=len(a)
a=int(a)
if a==100000:
  print(90909)
elif 99999>=a>=10000:
  print(909+a-9999)
elif 9999>=a>=1000:
  print(909)
elif 999>=a>=100:
  print(9+a-99)
elif 99>=a>=10:
  print(9)
else:
  print(a)


### FIXED CODE ###

a,b,c=map(int,input().split())
d=a-b
print(max(0,c-d))
N,Q=map(int, input().split())

adj_list = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    adj_list[a].append(b)
    adj_list[b].append(a)

def df(current, score, residual):
    counter[current]+=score
    residual = list(set(residual)-set([current]))

    next_nodes = adj_list[current]
    next_nodes = [node for node in next_nodes
            if node in residual]
    for node in next_nodes:
        df(node, score, residual)

for _ in range(Q):
    p,x=map(int, input().split())
    residual = list(set(range(N))-set(range(0,p-1)))
    df(p-1,x,residual)

result = ""
for i in range(N):
    result+="%d"%(counter[i])
    if i!=N-1:
        result+=" "
print(result)


### FIXED CODE ###

import sys
sys.setrecursionlimit(2*10**9)

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

adj_list = [[] for _ in range(N)]
counter = [0 for _ in range(N)]
reached = [0 for _ in range(N)]

for _ in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    adj_list[a].append(b)
    adj_list[b].append(a)

def df(current, score):
    next_nodes = adj_list[current]
    reached[current]=1
    for node in next_nodes:
        if reached[node]==0:
            counter[node]+=score
            df(node, counter[node])

for _ in range(Q):
    p,x=map(int, input().split())
    counter[p-1]+=x
df(0, counter[0])
print(*counter)
n = list(map(int,input()))[::-1]
mon = []
pay = []
ret = []
d = 0
for i in range(len(n)):
    c = d + n[i]
    e = c%10
    mon.append(c)
    if e < 5:
        pay.append(e)
        ret.append(0)
        d = c//10
    elif e == 5:
        if i == len(n):
            pay.append(e)
            ret.append(0)
            d = c//10
        else:
            if n[i+1] < 4:
                pay.append(e)
                ret.append(0)
                d = c//10
            else:
                pay.append(0)
                f = 10-e
                ret.append(f)
                d = c//10 + 1
    else:
        pay.append(0)
        f = 10-e
        ret.append(f)
        d = c//10 + 1
if d == 1:
    pay.append(1)
    

ans = 0
for i in range(len(pay)):
    ans += pay[i]
for j in range(len(ret)):
    ans += ret[j]
    

print(ans)

### FIXED CODE ###

m = input()[::-1]
n = []
for i in range(len(m)):
    n.append(int(m[i]))

dp = [[0, 0] for _ in range(len(n)+1)]

for i in range(len(n)):
    dp[i+1][0] = min((dp[i][0]+n[i]), (dp[i][1]+n[i]+1))
    if i == 0:
        dp[i+1][1] = dp[i][0]+10-n[i]
    else:
        dp[i+1][1] = min((dp[i][0]+10-n[i]), (dp[i][1]+9-n[i]))

s = len(n)
print(min(dp[s][0], (dp[s][1]+1)))
A, B, C, K = list(map(int, input().split()))

if (A >= K):
  print(K*1)

else:
  if (A + B >= K):
    print(A*1 + 0)
  else:
    print(A*1 + 0 + (K-A-B)*(-1))


### FIXED CODE ###

id1 = input()
id2 = input()

if (id1 == id2[:-1]):
  print("Yes")
else:
  print("No")
N=int(input())
S=int(input().split())
i=0
while S%2!==0
i+=1
print(i)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
pre=0
ans = 0
while True:
  for i in range(N):
    if(A[i]/2)%1==0:
      pre+=1
  if pre == N:
      ans+=1
      A=[x/2 for x in A]
      pre =0
  else:
      print(ans)
      exit()
n=int(input().split())
a=[0]*n
b=list(map(int,input().split()))
a[0]=b[0]
a[n-1]=b[n-2]

for i in range(1,n-1):
  a[i]=min(b[i-1],b[i])

print(sum(a))  
  


### FIXED CODE ###

n=int(input())
print(n**3)
#AGC003B

n=int(raw_input())
s=[]
for i in xrange(1,n+1):
 x=int(raw_input())
 for j in xrange(x):
  s.append(i)
cnt=0
i=0
while i<len(s)-1:
 if s[i+1]-s[i]==0 or s[i+1]-s[i]==1:
  cnt+=1
  i+=2
 else:
  i+=1
print cnt


### FIXED CODE ###

#AGC003A

s=raw_input()
l=[s[i] for i in xrange(len(s))]
if l.count('N')==0 and l.count('S')>0:
 print "No"
elif l.count('N')>0 and l.count('S')==0:
 print "No"
elif l.count('E')==0 and l.count('W')>0:
 print "No"
elif l.count('E')>0 and l.count('W')==0:
 print "No"
else:
 print "Yes"
N,K=map(int,input().split())

if N%K==0:
	print(0)
	elif N%K!=0:
		print(1)

### FIXED CODE ###

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

if N%K==0:
	print(0)
else:
	print(1)
a = input().split('/')
a = list(map(int, a))
if a[0] < 2019:
  print('Heisei')
elif a[1] < 5:
  print('Heisei')
else:
  print('TBD')
a = input().split('/')
if a[0] < 2019:
  print('Heisei')
elif a[1] < 5:
  print('Heisei')
else:
  print('TBD')

### FIXED CODE ###

a = input().rstrip().split('/')
a = list(map(int, a))
if a[0] < 2019:
  print('Heisei')
elif a[1] < 5:
  print('Heisei')
else:
  print('TBD')