Harryxun/stf_run huggingface dataset:
from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())


visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):z
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.pop()
        elif len(warpkouho) != 0:
            tmp = warpkouho.pop()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                    check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()

        

### FIXED CODE ###

from collections import deque
HW = input().split()
H, W = int(HW[0]), int(HW[1])
C = input().split()
Ch, Cw = int(C[0]), int(C[1])
D = input().split()
Dh, Dw = int(D[0]), int(D[1])
route = []
for h in range(H):
    route.append(input())

visited = [[False]*W for x in range(H)]
kouho = deque()
kouho.append([Ch-1, Cw-1])
warpkouho = deque()

def check_walk(a, b):
    if 0 <= a <= H-1 and 0 <= b <= W-1: 
        if visited[a][b] == False and route[a][b] == ".":
            kouho.append([a, b])
def check_warp(a, b, cwarp):
    if 0 <= a <= H-1 and 0 <= b <= W-1:
        if visited[a][b] == False and route[a][b] == ".":
            warpkouho.append([a, b, cwarp+1])

def wizard():
    warp = 1
    while True:
        if len(kouho) != 0:
            tmp = kouho.popleft()
        elif len(warpkouho) != 0:
            tmp = warpkouho.popleft()
            warp = tmp[2]
        else:
            break
        h = tmp[0]
        w = tmp[1]
        if visited[h][w] == False:
            visited[h][w] = warp
            check_walk(h-1, w)
            check_walk(h+1, w)
            check_walk(h, w-1)
            check_walk(h, w+1)
            for n in range(5):
                for m in range(5):
                  check_warp(h-2+n, w-2+m, warp)
        if h == Dh-1 and w == Dw-1:
            print(visited[h][w]-1)
            return
    print(-1)
wizard()
import re

while True:
    n = int(raw_input())
    for i in range(n):
        print re.sub("Hoshino", "Hoshina", raw_input())

### FIXED CODE ###

n = int(raw_input())
for i in range(n):
    print raw_input().replace("Hoshino", "Hoshina")
N = int(input())            
if N > 999:                 
    print("ABD")            
else:                       
    pritn("ABC")            


### FIXED CODE ###

N = int(input())            
if N > 999:                 
    print("ABD")            
else:                       
    print("ABC")
mod=10**9+7
dic={}
def ADD(x):
	if x in dic:
		dic[x]+=1
	else:
		dic[x]=1
n,m=map(int,input().split())
for i in range(2,int(m**0.5+2)):
	while m%i==0:
		ADD(i)
		m//=i
if m>1:
	ADD(m)
dic=tuple(dic.values())
ans=1
fac=[1]
for i in range(2*n+2):
	fac.append(fac[-1]*(i+1)%mod)
def c(a,b):
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
for x in dic:
	ans*=c(x+n-1,x)
	ans%=mod
print(ans)



### FIXED CODE ###

mod=10**9+7
dic={}
def ADD(x):
	if x in dic:
		dic[x]+=1
	else:
		dic[x]=1
n,m=map(int,input().split())
for i in range(2,int(m**0.5+2)):
	while m%i==0:
		ADD(i)
		m//=i
if m>1:
	ADD(m)
dic=tuple(dic.values())
ans=1
fac=[1]
for i in range(10**6):
	fac.append(fac[-1]*(i+1)%mod)
def c(a,b):
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
for x in dic:
	ans*=c(x+n-1,x)
	ans%=mod
print(ans)
a = list(map(int, input().split()))
a.sort()
K = int(input())

print(a[2]*(2**k) + a[1] + a[0])

### FIXED CODE ###

a = list(map(int, input().split()))
a.sort()
K = int(input())
 
print(a[2]*(2**K) + a[1] + a[0])
s = input()

a = 0
for i in range(4):
  a += 1 if s[i:i+1] == '+' else a -= 1
print(a)

### FIXED CODE ###

s = input()
a = 0
for i in range(4):
  a = a + 1 if s[i:i+1] == '+' else a - 1

print(a)
n, a, b = map(int,input().split())

c = n // (a + b)
if c == 0:
    d = a + b
    assert False
else:
    d = n - (c * (a+b))

if d > a:
    ans = (c*a) + a
else:
    ans = (c*a) + d
    
print(ans)


### FIXED CODE ###

N, A, B = map(int, input().split())
s = A+B
num = N // s * A
mod = N % s
num += min(mod, A)
print(num)
def abc070_b():
    a, b, c, d = map(int, input().split())
    
    if c > b:
        return 0
    
    if c < a < b < d:
        return b - a
    
    if a < c < b < d:
        return b - c
    
    if a < c < d < b:
        return d - c
    
    
if __name__ == '__main__':
    print(abc048_b())

### FIXED CODE ###

def abc070_b():
    a, b, c, d = map(int, input().split())

    if c <= a < b <= d:
        return b - a

    if a <= c < d <= b:
        return d - c

    if a <= c < b <= d:
        return b - c

    if c <= a < d <= b:
        return d - a

    if b <= c or d <= a:
        return 0


if __name__ == '__main__':
    print(abc070_b())
N,M = map(int,input.split())


#iから進める場所をリストにして保管
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)


#深さ優先探索
def dfs(list):
    #lst(通過点)の数がN(頂点数)と等しくなったら探索終了（成功）
  if len(list) == N:
    return 1
  else:
    a = list[-1]
    #lstの最後尾（現在地）が次に進める場所をnextとしてリスト化
    #nextに以前通った場所が入っていないか確認
    next = [n for n in edges[a] if n not in list]
    #次に進める場所がなくなったら探索終了（失敗）
    if len(next) == 0:
      return 0

    total = 0
    #再帰でさらに探索
    for n in next:
      total += dfs(list + [n])

    return total


ans = dfs([1])

print(ans)


### FIXED CODE ###

N,M = [int(a) for a in input().split()]
edges = {i:[] for i in range(1,N+1)}
for i in range(M):
  a,b = [int(a) for a in input().split()]
  edges[a].append(b)
  edges[b].append(a)

def search(lst):
  if len(lst) == N:
    return 1
  else:
    a = lst[-1]
    next = [n for n in edges[a] if n not in lst]
    if len(next) == 0:
      return 0

    tot = 0
    for n in next:
      tot += search(lst + [n])
    
    return tot


ans = search([1])

print(ans)
a,x=list(map(int,input().split()),int(input());print(sum(a)+max(a)*((2**x)-1)

### FIXED CODE ###

a,x=list(map(int,input().split())),int(input());print(sum(a)+max(a)*((2**x)-1))
>>> a,b,c=map(int,input().split())

>>> if a<b:
      if a<c and c<b:
          print("Yes")
      else
          print("No")
    
	elif b<a:
		if b<c and c<a:
			print("Yes")
        else
        	print("No")
	else:
		print("No")

### FIXED CODE ###

a,b,c=map(int,input().split())
if a<b:
	if a<c and c<b:
		print("Yes")
	else:
		print("No")
elif b<a:
	if b<c and c<a:
		 print("Yes")
	else:
		 print("No")
else:
	 print("No")
n = int(input())
t, a = map(int, input().split())
h = list(map(int, input().split()))

li = []
for i in range(len(h)):
  li.append(t - h[i]*0.006)
  
print(index(min(li)))

### FIXED CODE ###

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

li = []
for i in range(n):
  li.append(abs(a - (t - h[i]*0.006)))
  
print(li.index(min(li))+1)
import sys
sys.setrecursionlimit(4100000)

def find(Data, x):
    if Data[x] < 0:
        return x
    else:
        Data[x] = find(Data, x)
        return Data[x] 

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a != b:
        if Data[a] > Data[b]:
            Data[a] = Data[a] + Data[b]
            Data[b] = a
        else:
            Data[b] = Data[b] + Data[a]
            Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    unite(UF, ai, bi)

ans = 0
for i in range(n):
    if UF[i] < 0: ans += 1 
print(ans - 1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def find(Data, x):
    if Data[x] < 0:
        return x
    else:
        Data[x] = find(Data, Data[x])
        return Data[x] 

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a == b:
        pass
    elif Data[a] < Data[b]:
        Data[a] = Data[a] + Data[b]
        Data[b] = a
    else:
        Data[b] = Data[b] + Data[a]
        Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    unite(UF, ai, bi)

ans = 0
for i in range(n):
    if UF[i] < 0: ans += 1 
print(ans - 1)
def div_cnt(input_n):
    cnt = 0
    while input_n % 2 == 0:
        input_n /= 2
        cnt += 1

    return cnt

input_n = int(input())
input_a = list(map(int,input().split()))
cnt = min(map(div_cnt,input_a))

print(cnt)

### FIXED CODE ###

input_s = input().count("1")

print(input_s)
def keta_sum(n):
	a = int(n*0.001)
	b = int(n*0.01) % 10
	c = int(n*0.1) % 10
	d = n % 10
	return a+b+c+d

while 2>1:
	n_try = int(raw_input())
	count = 0
	for n in range(10000):
		if n_try == keta_sum(n):
			count += 1
	print count

### FIXED CODE ###

def keta_sum(n):
	a = int(n*0.001)
	b = int(n*0.01) % 10
	c = int(n*0.1) % 10
	d = n % 10
	return a+b+c+d

while 2>1:
	try:
		n_try = int(raw_input())
		count = 0
		for n in range(10000):
			if n_try == keta_sum(n):
				count += 1
		print count
	except EOFError:
		break
	except ValueError:
		break
a,b,k = map(int,input().split())
m = []
for i in range(1,min(a,b)):
    if a%i == 0 and b%i == 0:
        m.append(i)
print(m)
print(m[k-1])

### FIXED CODE ###

A, B, K = map(int, input().split())
 
cand = []
for i in range(100,0,-1):
  if A%i == 0 and B%i == 0:
    cand += [i]
    
    
print(cand[K-1])
import math
def combinations(n, r):
  if n == r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
s = [sorted(input())]
ans = 0
for i in range(N-1):
  s_i = sorted(input())
  s.append(s_i)
s = sorted(s)
count=1
for j in range(N-1):
  if s[j] == s[j+1]:
    count+=1
  else:
    ans += combinations(count,2)
    count=1
if count != 1:
  ans += combinations(count,2)
print(ans)

### FIXED CODE ###

import math
def combinations(n, r):
  if n == r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
s = [sorted(input())]
ans = 0
for i in range(N-1):
  s_i = sorted(input())
  s.append(s_i)
s = sorted(s)
count=1
for j in range(N-1):
  if s[j] == s[j+1]:
    count+=1
  else:
    if count != 1:
      ans += combinations(count,2)
    count=1
if count != 1:
  ans += combinations(count,2)
print(ans)
N = int(input())
S = list(str(input()))
countlist=[]
if N % 2 == 0:
    split = N / 2
    odd = False
else:
    split = N / 2 + 1
    odd = True
for i in range(1,N-1):
    s1 = set(S[0:i])
    s2 = set(S[i:])
    
    matched_list=list(s1 & s2)
    countlist.append(len(matched_list))

ans = sorted(countlist,reverse=True)


print(ans[0])

### FIXED CODE ###

N = int(input())
S = list(str(input()))
countlist=[]
for i in range(0,N):
    s1 = set(S[:i])
    s2 = set(S[i:])

    matched_list=list(s1 & s2)
    countlist.append(len(matched_list))

ans = max(countlist)
print(ans)
n, k, q = map(int, input().split())
inl = [int[x] for x in range(q)]
chl = [0] * n
for z in inl:
  chl[z-1] += 1
for y in chl:
  if y > (q-k):
    print('Yes')
  else:
    print('No')


### FIXED CODE ###

n, k, q = map(int, input().split())
inl = [int(input()) for x in range(q)]
chl = [0] * n
for z in inl:
  chl[z-1] += 1
for y in range(n):
  if chl[y] > (q-k):
    print('Yes')
  else:
    print('No')
al = 'abcdefghijklmnopqrstuvwxyz'
N=int(input())
S=input()
Q=int(input())
from bisect import bisect_left, bisect_right
dic = {}
for i in range(N):
  if not S[i] in dic:
    dic[S[i]]=[i+1]
  else:
    dic[S[i]].append(i+1)
def fg1(l, r):
  l = int(l)
  dic[S[l-1]].remove(l)
  if not r in dic:
    dic[r]=[l]
  else:
    ins = bisect_left(dic[r], l)
    dicr = dic[r][:ins]
    dicr.append(l)
    dicr += dic[r][ins:]
    dic[r]=dicr
def fg2(l, r):
  l, r = int(l), int(r)
  ret = 0
  for d in list(dic.keys()):
    ll = bisect_left(dic[d], l)
    rr = bisect_right(dic[d], r)
    ret += ll<rr
  print(ret)
  
for i in range(Q):
  fg, l, r = input().split()
  if fg=='1':
    fg1(l, r)
  else:
    fg2(l, r)

### FIXED CODE ###

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

from bisect import bisect_left, bisect_right


n = int(input())
s = list(input())
q = int(input())

al = 'abcdefghijklmnopqrstuvwxyz'
dicq = {i:[] for i in al}
for i, si in enumerate(s):
    dicq[si].append(i)

def q1(iq, cq):
    #print(iq,cq,s[iq],dicq[s[iq]],bisect_left(dicq[s[iq]], iq))
    dicq[s[iq]].pop(bisect_left(dicq[s[iq]], iq))   #更新前から削除
    s[iq] = cq
    dicq[cq].insert(bisect_left(dicq[cq], iq), iq)   #更新後に追加

def q2(l, r):
    ret = 0
    for ai in al:
        if len(dicq[ai])==0: continue
        li = bisect_left(dicq[ai], l)
        ri = bisect_right(dicq[ai], r)
        if li != ri:
            ret += 1
        elif li == len(dicq[ai]): continue
        elif dicq[ai][li] == l:
            ret += 1
    #    print(l,r,ai,dicq[ai],li,ri,ret)
    print(ret)

for i in range(q):
    fg, x, y = input().split()
    if fg == '1':
        q1(int(x)-1, y)
    else:
        q2(int(x)-1, int(y)-1)
N = int(input())
L = [i for i in map(int,input().split()) if i%2 == 0]
even = 1
res = 0
for i in range(len(L)):
  even *= L[i]
while even != 0 and even % 2 == 0:
  even /= 2 
  res += 1
print(res)

	


### FIXED CODE ###

import sys
import numpy
N = int(input())
L = [i for i in map(int,input().split()) if i%2 == 0]
L2 = [0 for i in range(len(L))]
if L == []:
  print(0)
  sys.exit(0)
for i in range(len(L)):
    s = 1
    while L[i] % 2**s == 0:
        s += 1
    L2[i] = s-1
Q = numpy.sum(L2)
print(Q)
import numpy as np
def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=np.zeros([N+1,W+1])

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1,j]=graph[i,j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i,rest]+inputset[i][0]
                nonchoosevalue=graph[i,j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1,j]=choosevalue
                else:
                    graph[i+1,j]=nonchoosevalue

    print(13)

main()

### FIXED CODE ###

def main():
    [N,W]=input().split(" ")
    N=int(N)
    W=int(W)
    inputset=[]
    for i in range(N):
        [vi,wi]=input().split(" ")
        inputset.append([int(vi),int(wi)])

    graph=[]
    for i in range(N+1):
        graph.append([])
        for j in range(W+1):
            graph[i].append(0)

    for i in range(N):
        for j in range(W+1):
            if(inputset[i][1]>j):
                graph[i+1][j]=graph[i][j]
            else:
                rest=j-inputset[i][1]
                choosevalue=graph[i][rest]+inputset[i][0]
                nonchoosevalue=graph[i][j]
                if(choosevalue>nonchoosevalue):
                    graph[i+1][j]=choosevalue
                else:
                    graph[i+1][j]=nonchoosevalue

    print(graph[N][W])

main()
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, K = read_values()
    dp = [
        [[0 for i in range(N ** 2 + 1)] for ii in range(N + 1)] for iii in range(N + 1)
    ]
    dp[0][0][0] = 1

    for i in range(1, N + 1):
        for j in range(N + 1):
            for k in range(K + 1):
                if k - 2 * j < 0:
                    continue

                dp[i][j][k] = (
                    (2 * j + 1) * dp[i - 1][j][k - 2 * j]
                    + (j + 1) * (j + 1) * dp[i - 1][j + 1][k - 2 * j]
                    + dp[i - 1][j - 1][k - 2 * j]
                ) % mod

    print(dp[N][0][K])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, K = read_values()
    dp = [
        [[0 for i in range(N ** 2 + 1)] for ii in range(N + 1)] for iii in range(N + 1)
    ]
    dp[0][0][0] = 1

    for i in range(1, N + 1):
        for j in range(N + 1):
            for k in range(K + 1):
                if k - 2 * j < 0:
                    continue

                dp[i][j][k] = (
                    (2 * j + 1) * dp[i - 1][j][k - 2 * j]
                    + (
                        (j + 1) * (j + 1) * dp[i - 1][j + 1][k - 2 * j]
                        if j + 1 <= N
                        else 0
                    )
                    + dp[i - 1][j - 1][k - 2 * j]
                ) % mod

    print(dp[N][0][K])


if __name__ == "__main__":
    main()
X, A = map(int, input.split());
if X < A:
  print(0);
else:
  print(10);

### FIXED CODE ###

X, A = map(int, input().split());
if X < A:
    print(0);
else:
    print(10);
from math import log10

def main(N):
    A = list(map(int, input().split()))
    st_A = set(A)
    if 0 in st_A:
        print(0)
    else:
        x = 1
        for a in A:
            x *= a
        	if x > 10**18:
            	print(-1)
                exit()
        else:
            print(x)




if __name__ == '__main__':
    N = int(input())
    main(N)


### FIXED CODE ###

def main(N):
    A = list(map(int, input().split()))
    st_A = set(A)
    if 0 in st_A:
        print(0)
    else:
        x = 1
        for a in A:
            x *= a
            if x > 10 ** 18:
                print(-1)
                exit()
        else:
            print(x)





if __name__ == '__main__':
    N = int(input())
    main(N)
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**8)

def operation(s,memo=-1,ans=0):
    if len(s) <= 0:
        return ans
    elif s[0] == memo == "0": #変えるパターン
        return operation(s[1:],"1",ans+1)
    elif s[0] == memo == "1": #変えるパターン
        return operation(s[1:],"0",ans+1)
    else:
        return operation(s[1:],s[0],ans)

def solve(s):
    return min(operation(s,"0"),operation(s,"1"))

def main():
    S = input()
    print(solve(S))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10**6)

def operation(s,f):
    c = 0
    for i in range(len(s)):
        if (s[i] == f and i % 2 == 1) or (s[i] != f and i % 2 == 0):
            c += 1
    return c

def solve(s):
    return min(operation(s,"0"),operation(s,"1"))

def main():
    S = input()
    print(solve(S))


if __name__ == '__main__':
    main()
from collections import defaultdict


class Dijkstra():
    def __init__(self):
        self.e = defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:  # defaultではFalseとなる
                continue

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d


N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(S)
result_b = graph2.search(T)

ans_list = [float('inf')]

for i in range(N, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10**15 - ans_list[-(i+1)])

### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.readline


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                new_d = k + d
                if distance[v] > new_d:
                    distance[v] = new_d
                    heappush(queue, (new_d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in uvab:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for ans in ans_list[n:0:-1]:
    print(10 ** 15 - ans)
a,b = map(int, input().split())
if 2b >= a:
  print(0)
else:
  print(a - 2*b)

### FIXED CODE ###

a,b = map(int, input().split())
if 2*b >= a:
  print(0)
else:
  print(a - 2*b)
string = list(input("");
if (string[2] == string[3]):
  if (string[4] == string[5]):
    print("Yes");
  else:
    print("No");
else:
  print("No");

### FIXED CODE ###

string = list(input());
if (string[2] == string[3]):
  if (string[4] == string[5]):
    print("Yes");
  else:
    print("No");
else:
  print("No");