Harryxun/stf_run huggingface dataset:
import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf]*w for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
def bfs(d):
    global h,w,k,x1,y1,x2,y2,c,dp,now
    l=len(now)
    if l==0:
        return
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,max(k+1,w-y)):
            if c[x][y+j]==".":
                if dp[x][y+j]==inf:
                    dp[x][y+j]=d
                    now.append([x,y+j])
            else:
                break
        for j in range(1,max(k+1,y+1)):
            if c[x][y-j]==".":
                if dp[x][y-j]==inf:
                    dp[x][y-j]=d
                    now.append([x,y-j])
            else:
                break
        for j in range(1,max(k+1,h-x)):
            if c[x+j][y]==".":
                if dp[x+j][y]==inf:
                    dp[x+j][y]=d
                    now.append([x+j,y])
            else:
                break
        for j in range(1,max(k+1,x+1)):
            if c[x-j][y]==".":
                if dp[x-j][y]==inf:
                    dp[x-j][y]=d
                    now.append([x-j,y])
            else:
                break
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
13
insert AAA
insert AAC
insert AGA
insert AGG
insert TTT
find AAA
find CCC
find CCC
insert CCC
find CCC
insert T
find TTT
find T

### FIXED CODE ###

from collections import defaultdict

d = defaultdict(lambda: 0)

N = int(input())

for _ in range(N):
    ord, str = input().split()
    if ord == 'insert':
        d[str] = 1
    else:
        if str in d:
            print('yes')
        else:
            print('no')
a,b,c=str(int, input().split())
if b == '+':
  print(int(a)+int(b))
else:
  print(int(a)-int(b))

### FIXED CODE ###

a,b,c=map(str, input().split())
if b == '+':
  print((int(a)+int(c)))
else:
  print(int(a)-int(c))
N,M=map(int,input().split())
LR=list(map(int,input().split()) for _ in range(M) )
L=0
R=N
for i in range(M):
    L=max(L,LR[i][0])
    R=min(R,LR[i][1])
print(R-L+1 if R<=L else 0)

### FIXED CODE ###

N,M=map(int,input().split())
LR=list(list(map(int,input().split())) for _ in range(M))
L=1
R=N
for i in range(M):
    L=max(L,LR[i][0])
    R=min(R,LR[i][1])
print(R-L+1 if L<=R else 0)
a,b,c,d,e,f=map(int,input().split())
ans=100
for i in range(f//(100*a)+1):
    for j in range(f//(100*b)+1):
        s=100*a*i+100*b*j
        if s==0:
            break
        for ii in range((f-100*a)//c+1):
            for jj in range((f-100*a)//d+1):
                t=c*ii+d*jj
                if t==0:
                    break
                u=(100*t)/s
                if s+t<=f and u==f:
                    print(str(s+t)+" "+str(t))
                    exit()
                if s+t<=f and u<e:
                    if ans>e-u:
                        ans=e-u
                        x,y=s,t
print(str(x+y)+" "+str(y))
                    

### FIXED CODE ###

a,b,c,d,e,f=map(int,input().split())
t=100
for i in range(0,f+1,a*100):
    for j in range(0,f-i+1,b*100):
        k=i+j
        if k==0:
            continue
        s=min(f-i-j,(i+j)*e//100)
        for ii in range(0,s+1,c):
            for jj in range(0,s-ii+1,d):
                if t>e-(ii+jj)*100/(i+j):
                    t=e-(ii+jj)*100/(i+j)
                    x,y=ii+jj+i+j,ii+jj
print(str(x)+" "+str(y))
N,W=map(int,input().split())
wv=[[int(j) for j in input().split()] for _ in range(N) ]
w0=wv[0][0]
w1=w0+1
w2=w1+1 
w3=w2+1
wv=sorted(wv,key=lambda x:x[1],reverse=True)
wv=sorted(wv)

ans=0
from bisect import bisect_left as bll
for e1 in range(0,W//w0+1):
  l2=W-w0*e1
  for e2 in range(0,l2//(w0+1)+1):
    l3=l2-(w0+1)*e2
    for e3 in range(0,l3//(w0+2)+1):
      l4=l3- (w0+2)*e3
      e4 =l4//(w0+3)    
      tmp=0
      i1=bll(wv, (w0,inf))
      i2=bll(wv, (w1,inf))
      i3=bll(wv, (w2,inf))
      i4=bll(wv, (w3,inf))
      tmp+=sum(wv[i1:i1+e1])  \
         +sum(wv[i2:i2+e2])  \
         +sum(wv[i3:i3+e3])  \
        +sum(wv[i4:i4+e4])
      ans=max(ans,tmp)
      
print(ans)

### FIXED CODE ###

N,W=map(int,input().split())
wv=[ tuple([int(j) for j in input().split()]) for _ in range(N) ]
w1=wv[0][0]
w2=w1+1
w3=w1+2 
w4=w1+3

wv=sorted(wv,key=lambda x:x[1],reverse=True)
wv=sorted(wv,key=lambda x:x[0])
wvv = list(map(lambda x:x[1], wv))

# print(wv)
inf = float("inf")
ans=0
from collections import defaultdict
counter = defaultdict(int)

for i in range(N):
    w,v = wv[i]
    counter[w] += 1

from bisect import bisect_left as bll

for e1 in range(0, counter[w1]+1):
  for e2 in range(0, counter[w2]+1):
    for e3 in range(0,counter[w3]+1):
      for e4 in range(0, counter[w4]+1):
          tmp=0

          if w1*e1 + w2*e2 + w3*e3 + w4*e4 > W:
              continue

          i1=bll(wv, (w1,-inf))
          i2=bll(wv, (w2,-inf))
          i3=bll(wv, (w3,-inf))
          i4=bll(wv, (w4,-inf))

          tmp= tmp \
             +sum(wvv[i1:i1+e1])  \
             +sum(wvv[i2:i2+e2])  \
             +sum(wvv[i3:i3+e3])  \
             +sum(wvv[i4:i4+e4])

          ans=max(ans,tmp)
      
print(ans)
import math


n = int(input())
a = list(map(int, input().split()))

left_gcd_list = [a[0]]
right_gcd_list = [a[n - 1]]

for i in range(1, n):
    left_gcd_list.append(math.gcd(a[i], left_gcd_list[i - 1]))
    right_gcd_list.insert(0, math.gcd(a[n - 1 - i], right_gcd_list[0]))

print(max([left_gcd_list[n - 2]] +
          [math.gcd(left_gcd_list[i], right_gcd_list[i + 2]) for i in range(0, n - 2)] +
          [right_gcd_list[1]]))


if __name__ == '__main__':
    pass


### FIXED CODE ###

import fractions
import numpy as np


n = int(input())
a = list(map(int, input().split()))

left_gcd_array = np.array([0] * n)
left_gcd_array[0] = a[0]

right_gcd_array = np.array([0] * n)
right_gcd_array[n - 1] = a[n - 1]

for i in range(1, n):
    left_gcd_array[i] = fractions.gcd(a[i], left_gcd_array[i - 1])
    right_gcd_array[n - 1 - i] = fractions.gcd(a[n - 1 - i], right_gcd_array[n - i])

print(max([left_gcd_array[n - 2]] +
          [fractions.gcd(left_gcd_array[i], right_gcd_array[i + 2]) for i in range(0, n - 2)] +
          [right_gcd_array[1]]))


if __name__ == '__main__':
    pass
N = int(input())
M = 1
prev_M = 0
A = []
for i in range(N):
  a = int(input())
  A += [a]
  if a == M:
    prev_M = M
  elif a > M:
    M = a
for i in range(N):
  if a[i] != M:
    print(M)
  else:
    print(prev_M)

### FIXED CODE ###

N = int(input())
M = 1
prev_M = 0
A = []
for i in range(N):
  a = int(input())
  A += [a]
  if a == M:
    prev_M = M
  elif a > M:
    prev_M = M
    M = a
  elif a > prev_M:
    prev_M = a
for i in range(N):
  if A[i] != M:
    print(M)
  else:
    print(prev_M)
N,K = map(int,input().split())
bosu = [1]*N
for i in range(1:N+1):
    point = i
    while i < K:
        point *= 2
        bosu[i-1] *= 2

print(N/sum(bosu))


### FIXED CODE ###

N,K = map(int,input().split())
bosu = [N]*N
for i in range(1,N+1):
    point = i
    while point < K:
        point *= 2
        bosu[i-1] *= 2
        
ans = 0
for i in bosu:
    ans += 1/i

print(ans)
A=int(input())
B=int(input())
if(A==1 and B==2):
	x=3
elif(A==2 and B==3):
	x=1
elif(A==3 and B==1):
	x=2
print(x)


### FIXED CODE ###

A=int(input())
B=int(input())
if(A==1 and B==2):
  answer=3
elif(A==1 and B==3):
  answer=2
elif(A==2 and B==3):
  answer=1
elif(A==2 and B==1):
  answer=3
elif(A==3 and B==1):
  answer=2
elif(A==3 and B==2):
  answer=1
print(answer)
a = input()
b = input()
h = input()

print((a+b)*h/2)

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
 
print(int((a+b)*h/2))
import numpy as np
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for i in A:
  for j in B[np.searchsorted(B, i, side="right"):]:
    ans += n - np.searchsorted(C, j, side="right")
print(ans)

### FIXED CODE ###

import bisect
from itertools import accumulate
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
b_to_c = [0]*n
for i in range(n):
  b_to_c[i] = n - bisect.bisect_right(C, B[i])
Q = list(accumulate(b_to_c[::-1]))[::-1]
  
for i in A:
  t = bisect.bisect_right(B, i)
  if t < n:
    ans += Q[t]
print(ans)
n,k = map(int,input().split())
L = list(map(int,input().split()))
ok = 0
ng = 10**9
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    cur = 0
    for i in range(n):
        cur += L[i]//mid
    if cur > k:
        ok = mid
    elif cur <= k:
        ng = mid
    print(mid,cur)
K = [mid-1, mid, mid+1]
P = []
for i in range(3):
    res = 0
    for j in range(n):
        res += (L[j]-1)//K[i]
    if res <= k:
        P.append(K[i])
print(min(P))

### FIXED CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
ok = 0
ng = 10**9
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    cur = 0
    for i in range(n):
        cur += L[i]//mid
    if cur > k:
        ok = mid
    elif cur <= k:
        ng = mid
K = [mid-1, mid, mid+1]
P = []
for i in range(3):
    res = 0
    if K[i] > 0:
        for j in range(n):
            res += (L[j]-1)//K[i]
        if res <= k:
            P.append(K[i])
print(min(P))
import sys
import queue

def ni():
    return int(sys.stdin.readline())


def nia():
    data = sys.stdin.readline().split(' ')
    return [int(g) for g in data]


n = ni()
graph = []
for i in range(0, n):
    graph.append([])

for i in range(1, n):
    a, b = nia()
    a = a - 1
    b = b - 1

    graph[a].append(b)
    graph[b].append(a)


q = queue.Queue()
q.put(0)
visited = set()
visited.add(0)
last = 0
while not q.empty():
    n = q.get()
    last = n
    for nb in graph[n]:
        if nb not in visited:
            visited.add(nb)
            q.put(nb)

diam = 0
visited = set()
next = [(last, 0)]
while next:
    ind, x = next.pop()
    diam = max(diam, x)
    for nb in graph[ind]:
        if nb not in visited:
            visited.add(nb)
            next.append((nb, x + 1))


if (diam + 1) % 3 == 2:
    print 'Second'
else:
    print 'First'



### FIXED CODE ###

import sys
from collections import deque

def ni():
    return int(sys.stdin.readline())


def nia():
    data = sys.stdin.readline().split(' ')
    return [int(g) for g in data]

n = ni()
graph = []
for i in range(0, n):
    graph.append([])

for i in range(1, n):
    a, b = nia()
    a = a - 1
    b = b - 1

    graph[a].append(b)
    graph[b].append(a)


q = deque()
q.append(0)
visited = set()
visited.add(0)
last = 0
while q:
    n = q.popleft()
    last = n
    for nb in graph[n]:
        if nb not in visited:
            visited.add(nb)
            q.append(nb)

diam = 0
visited = set()
next = [(last, 0)]
while next:
    ind, x = next.pop()
    diam = max(diam, x)
    for nb in graph[ind]:
        if nb not in visited:
            visited.add(nb)
            next.append((nb, x + 1))

if (diam + 1) % 3 == 2:
    print 'Second'
else:
    print 'First'
import numpy as np
n,k = map(int,input().split())
s = list(input())
memory = s[0]
count = 1
lst = np.array([0])
M = 0
for i in range(1,n):
    if s[i] == memory:
        count += 1
    else:
        lst = np.append(lst,count)
        memory = s[i]
        count = 1
lst = np.append(lst,count)
cs = lst.cumsum()
if s[0] == '1':
    if 2*k+3 >= len(cs):
        print(cs[-1])
        exit()
    else:
        i = 0
        while i+2*k+2 <= len(cs):           
            M = max(M,cs[i+2*k+1]-cs[i])
            i += 2
        print(M)
        exit()
if s[0] == '0':
    if 2*k+2 >= len(cs):
        print(cs[-1])
        exit()
    else:
        i = 1
        while i+2*k+2 <= len(cs):
            M = max(M,cs[i+2*k+1]-cs[i])
            i += 2
        M = max(M,cs[2*k]-cs[0])
        print(M)
        exit()

### FIXED CODE ###

n,k = map(int,input().split())
s = input()
x = len(s)
lst = [0]
ans = 0
if s[0] == "1" and s[x-1] == "0":
    s = s[::-1]
for i in range(1,x):
    if s[i-1] != s[i]:
        lst.append(i)
lst.append(x)
if s[0] == "0" and s[x-1] == "1":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
if s[0] == "0" and s[x-1] == "0":
    if 2*k >= len(lst):
        ans = x
    else:
        i = 1
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
        ans = max(ans,lst[2*k])
        ans = max(ans,x-lst[len(lst)-2*k-1])
if s[0] == "1" and s[x-1] == "1":
    if 2*k+1 >= len(lst):
        ans = x
    else:
        i = 0
        while i+2*k+1 <= len(lst)-1:
            ans = max(ans,lst[i+2*k+1]-lst[i])
            i += 2
print(ans)
N,M=int(input())
s=[input() for _ in range(N)]
t=[input() for _ in range(M)]
ans=input()
print(s.count(ans)-t.count(ans))

### FIXED CODE ###

N=int(input())
s=[input() for _ in range(N)]
M=int(input())
t=[input() for _ in range(M)]
def ans1(x):
    return s.count(x)-t.count(x)
ans2=0
ans_1=0
for S in s:
    if ans1(S)>0 and ans1(S)>ans2:
            ans2=ans1(S)
if ans2>=0:
    print(ans2)
else:
    print("0")
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
if sum(a)<=k:
    print(0)
    exit()
f.sort(reverse=True)
l=0
r=10**12
m=(r+l)//2
def check(x):
    p=0
    for i in range(n):
        if x//f[i]<a[i]:
            p+=a[i]-x//f[i]
            if p>k:
                return False
    if p>k:
        return False
    else:
        return True
while l<r:
    if check(x):
        r=x
        x=(r+l)//2
    else:
        l=x
        x=(r+l)//2
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

a = []
f = []
n = 0

def rec(l, r, k):
    if l+1 < r:
        mid = (l + r) // 2
        s = 0
        for i in range(n):
            s += max(a[i] - mid // f[i], 0)
        if s <= k:
            return rec(l, mid, k)
        else:
            return rec(mid, r, k)
    else:
        return r

def main():
    global a, f, n
    n, k = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    f = list(map(int, input().strip().split()))
    a = sorted(a)
    f = sorted(f, reverse=True)
    print(rec(-1, 10**12, k))

if __name__ == '__main__':
    main()
X,N = map(int,input().split())
P = list(map(int,input().split()))

P_n = [i for i in range(1,101,1) if i not in P]
abs_value = [abs(X-P_n[j]) for j in range(len(P_n))]


min_abs = min(abs_value)
for k in range(len(abs_value)):
    if abs_value[k] == min_abs:
        print(P_n[k])
        break

### FIXED CODE ###

X, N = map(int, input().split())
 
p = list(map(int, input().split()))
 
p_none = [i for i in range(110) if i not in p]
p_none_sa = [abs(p_none[i]-X) for i in range(len(p_none))]
 
import sys
 
min_p_none = min(p_none_sa)
for i in range(len(p_none_sa)):
    if p_none_sa[i] == min_p_none:
        print(p_none[i])
        sys.exit()
# -*- coding:utf-8 -*-

x,y = int(input()),int(input())

print(x*y)

### FIXED CODE ###

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

x = input()
k = x.split(' ')
a = int(k[0])
b = int(k[1])

area = int(a) * int(b)
length = int(a)*2 + int(b)*2

print(area,length)
W,H,x,y = input().split()
W = int(W)
H = int(H)
x = int(x)
y = int(y)

print("{} 0".format(W*H/2)

### FIXED CODE ###

W,H,x,y = input().split()
W =float(W)
H = float(H)
x = float(x)
y = float(y)
sq = W*H/2
if x == W/2 and y == H/2:
  print("{} 1".format(sq))
else:
  print("{} 0".format(sq))
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

t = 1
for i in range(1, N - 1):
  t *= i

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    x1, y1 = xy[i]
    x2, y2 = xy[j]
    ans += (((x1 - x2) ** 2 + (y1 - y2) ** 2) ** (1 / 2)) * (N - 1) * 2 * t

n = 1
for i in range(1, N + 1):
  n *= i

ans /= n

print(ans)


### FIXED CODE ###

N = int(input())

print(N*N)
import math
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k = int(read())
ans = 0
for a in range(1, n+1):
    for b in range(1, n + 1):
        n = math.gcd(a, b)
        for c in range(1, n+1):
            ans += math.gcd(n, c)
print(ans)

### FIXED CODE ###

import math
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k = int(read())
ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        n = math.gcd(a, b)
        for c in range(1, k + 1):
            ans += math.gcd(n, c)
print(ans)
print('YNeos'[int(input()) in[1,2,3,5,6,9,10,13,17]::2])


### FIXED CODE ###

print(0 if eval(input().replace(' ','%'))==0 else 1)
import numpy as np
import heapq
dif = 10 ** 6
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = np.full(n, initial_cost)
    costs[s] = 0
    node_list = []
    serched_node = set()
    heapq.heappush(node_list, s)
    
    while(len(node_list) != 0 and len(serched_node) != n):
        index = int(heapq.heappop(node_list) % dif)
        if index in serched_node:
            continue
        serched_node.add(index)
        link = links[index]
        for j in link:
            if j in serched_node:
                continue
        
            cost = link_costs[index][j]
            newcost =  costs[index] + cost
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(node_list, newcost * dif + j)
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links = [set() for _ in range(n)]
links_cost_en = np.full((n, n), initial_cost)
links_cost_sn = np.full((n, n), initial_cost)

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    links[u-1].add(v-1)
    links[v-1].add(u-1)
    links_cost_en[u - 1][v - 1] = a
    links_cost_en[v - 1][u - 1] = a
    links_cost_sn[u - 1][v - 1] = b
    links_cost_sn[v - 1][u - 1] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)

trans = n - 1
costs = np.full(n, initial_cost)
for i in range(n - 1, -1, -1):
    newcost = cost_en_from_s[i] + cost_sn_to_t[i]
    if newcost < costs[trans]:
        trans = i
        costs[i] = newcost
        continue
    
    costs[i] = costs[trans]
    
for cost in costs:
    print(int(initial - cost))

### FIXED CODE ###

import heapq
initial_cost = 10 ** 9
initial = 10 ** 15

def di(link_costs, s):
    costs = [initial] * n
    costs[s] = 0
    q = []
    heapq.heappush(q, (0, s))
    
    while(len(q) != 0):
        index_cost, index = heapq.heappop(q)
        if costs[index] < index_cost:
            continue

        for j in link_costs[index]:
            newcost = costs[index] + link_costs[index][j]
            if newcost < costs[j]:
                costs[j] = newcost
                heapq.heappush(q, (newcost, j))
    return costs
    
n, m, s, t  = list(map(int, input().split()))
s -= 1
t -= 1
links_cost_en = [{} for _ in range(n)]
links_cost_sn = [{} for _ in range(n)]

for _ in range(m):
    u, v, a, b  = list(map(int, input().split()))
    u -= 1
    v -= 1
    links_cost_en[u][v] = a
    links_cost_en[v][u] = a
    links_cost_sn[u][v] = b
    links_cost_sn[v][u] = b

cost_en_from_s = di(links_cost_en, s)
cost_sn_to_t = di(links_cost_sn, t)
cost_list = [cost_en_from_s[i] + cost_sn_to_t[i] for i in range(n)]

ans = [initial] * n
ans[-1] = cost_list[-1]
for i in list(range(n - 1))[::-1]:
    ans[i] = min(ans[i + 1], cost_list[i])
for i in range(n):
    print(initial - ans[i])
#payment=桁DPの復習方法
n=input()
#0の方がちょうど、1の方が余裕持って払う
dp0=[0 for i in range(1000001)]
dp1=[0 for i in range(1000001)]
nums=int(n[-1])
dp0[1]=nums
dp1[1]=11-nums
#dp0、dp1でそれぞれぴったり払う時と余裕を持たせて払うときのiけためまでを一つの数としてみたときの最小の値を表すものとする
for i in range(1,len(n)):
    s=int(n[-(i+1)])
    dp0[i+1]=s+min(dp0[i],dp1[i])
    dp1[i+1]=min(9-s+dp1[i],11-s+dp0[i])
print(min(dp0[len(n)],dp1[len(n)]))

### FIXED CODE ###

#payment=桁DPの復習方法
n=input()
#0の方がちょうど、1の方が余裕持って払う
dp0=[0 for i in range(1000002)]
dp1=[0 for i in range(1000002)]
nums=int(n[-1])

dp0[1]=nums
dp1[1]=11-nums
#dp0、dp1でそれぞれぴったり払う時と余裕を持たせて払うときのiけためまでを一つの数としてみたときの最小の値を表すものとする
for i in range(1,len(n)):
    s=int(n[-(i+1)])
    dp0[i+1]=s+min(dp0[i],dp1[i])
    dp1[i+1]=min(9-s+dp1[i],11-s+dp0[i])
print(min(dp0[len(n)],dp1[len(n)]))
n = int(input())
p=list(map(int,input().split()))
z=0
for i in range(n):
    if p[i]!=i+1:
        z+=1
if z>2:print(NO)
else:
    print(YES)


### FIXED CODE ###

n = int(input())
p=list(map(int,input().split()))
z=0
for i in range(n):
    if p[i]!=i+1:
        z+=1
if z>2:print("NO")
else:
    print("YES")
S = input()

count0, count1 = 0, 0
val = []
for i in range(len(S)):
    if S[i] == '<':
        count0 += 1
        if count1 != 0:
            val.append(count1)
        if i == len(S)-1:
            val.append(count0)
        count1 = 0
    else:
        count1 += 1
        if count0 != 0:
            val.append(count0)
        if i == len(S)-1:
            val.append(count1)
        count0 = 0

ans = 0
for i in range(0, len(val)-1, 2):
    a = max(val[i], val[i+1])
    b = min(val[i], val[i+1])
    ans += a*(a+1)/2 + (b-1)*b/2
if len(val) % 2 == 1:
    b = min(val[-2], val[-1])
    ans += (b+1)*b/2    
print(int(ans))


### FIXED CODE ###

s = input()
num = len(s)
a = [0]*(num+1)

for i in range(num):
    if s[i] is '<':
        a[i+1] = max(a[i+1], a[i]+1)

for i in range(1, num+1):
    if s[-i] is '>':
        a[-(i+1)] = max(a[-(i+1)], a[-i]+1)
print(sum(a))
mod = 10**9 + 7
n = int(input())
A = list(map(int,input().split()))
S = sum(A)%mod
ans = 0
for a in A:
    ans += a * (S - a)
print(ans*pow(2,-1,mod)%mod)


### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
A = list(map(int,input().split()))
S = sum(A)%mod
ans = 0
for a in A:
    ans += a * (S - a)
print(ans*pow(2,-1,mod)%mod)
from sys import stdin

S = stdin.readline().rstrip()
days = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

for i in range(len(days)):
    if S == days[i]:
        t = i
        break
    else:
        i += 1

print(days[t + 1])

### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()
days  = ["MON","TUE","WED","THU","FRI","SAT","SUN"]

if S == "SUN":
    print(7)
else:
    i = days.index(S)
    print(6 - i)
if input()[0]==input()[2]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

a=input()
if a[0]==a[2]:
    print('Yes')
else:
    print('No')