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

import queue

h, w = map(int, input().split())
s, count = [], 0
for _ in range(h):
    a = input()
    count += a.count('#')
    s.append(list(a))

def cal():
    ans = float('inf')
    q = queue.Queue()
    q.put((0, 0, 1))
    while not q.empty():
        c0, c1, c2 = q.get()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            ans = min(ans, h*w-count-c2)
            continue
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#':
                    q.put((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

def cal():
    import queue
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    cost = [[-1]*w for _ in range(h)]
    INF = float('inf')
    count, ans = 0, INF
    for i in range(h):
        for j in range(w):
            if s[i][j] != '#':
                cost[i][j] = INF
            else:
                count += 1        
    q = queue.Queue()
    q.put((0, 0, 1))
    while not q.empty():
        c0, c1, c2 = q.get()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#' and cost[x][y] == INF:
                    cost[x][y] = c2+1
                    q.put((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

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

A = list(map(int, input().split()))

B = []
for i in range(M):
    b, c = map(int, input().split())
    B.append([b, c])

B.sort(key=lambda x:(-x[1]))
cnt = 0
ans = []
for i in range(len(B)):
    for j in range(B[i][0]):
        ans.append(B[i][1])
        if cnt == N:
            break
ans += A
ans.sort(reverse=True)
print(sum(ans[:N]))

### FIXED CODE ###

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

A = sorted(list(map(int, input().split())), reverse=True)

B = []
for i in range(M):
    b, c = map(int, input().split())
    B.append([b, c])

B.sort(key=lambda x:(-x[1]))

cnt = 0
ans = 0
a = 0
b = 0
while True:
    if b <= M-1 and A[a] <= B[b][1]:
        n = min(B[b][0], N-cnt)
        ans += B[b][1]*n
        cnt += n
        if cnt == N:
            print(ans)
            break
        b += 1
    elif a <= N-1:
        cnt += 1
        ans += A[a]
        if cnt == N:
            print(ans)
            break
        a += 1
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
AA = []
for i in range(N - K + 1):
  f = 1
  for j in range(i, i + K):
    f *= A[j]
  AA.append(f)
  
for i in range(len(AA) - 1):
  if AA[i] < AA[i + 1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

for i in range(K, N):
  if A[i - K] < A[i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

baisu=set([])

i=1
while 1:
    temp=2019*i
    if "0" not in str(temp):
        baisu.add(str(temp))
    
    if temp>200000:
        break
    i+=1

n=input()
cnt=0
for i in range(len(n)-3):
    for j in range(i+4,len(n)+1):
        if n[i:j] in baisu:
            cnt+=1

print(cnt)



### FIXED CODE ###

s=input()



"""
◆エッセンス1：割り切れるとは、二つに分けた数字のmodが一緒
例)
1817181712114の
18171が2019で割り切れるかどうかを判断する。

18171は(181712114-2114)/10000となるので、
181712114mod2019＝2114mod2019の時、2019で割り切れる。

1817181712114mod2019
 817181712114mod2019
  17181712114mod2019
   7181712114mod2019
    181712114mod2019
     81712114mod2019
      1712114mod2019
       712114mod2019
    　　・・・・
とmodを調べていき、値が同じペアは割り切れる。
"""

"""
◆エッセンス2：大きい数字は都度modを取る

これだけでもループは1回になるんだけど、
|S|が長すぎてTLEとなってしまう（|S|は10**5）
1234567 mod 2019
=(1*10**7)mod2019 + (234567mod2019)
=(1*10mod2019 * 10**6mod2019)+ (234567mod2019)

10**nを毎回modを取ることで、計算する数字の長さを短くする。

"""



#modの値を保持する配列
cnt=[0]*2019
#mod2019 =0 は、それ一つで割り切れるので。引き算をする必要が無い。
cnt[0]=1

#10の倍数を保持する
fac=1
ss=0
for i in range(len(s)):
    #後ろの数字から順番にとってくる
    ss += int(s[len(s)-i-1])*fac
    ss%=2019
    fac=fac*10
    fac%=2019
    cnt[ss]+=1
    

result=0
for c in cnt:
    result+=c*(c-1)//2

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

N = int(input())

A_list = []
B_list = []
dif_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)
    dif_list.append(B - A)

takahashi_score = 0
aoki_score = 0
for i in range(N):
    if len(dif_list) != 0:
        dish_index = dif_list.index(max(dif_list))
        score = A_list[dish_index]
        takahashi_score += score

        del A_list[dish_index]
        del B_list[dish_index]
        del dif_list[dish_index]

    if len(dif_list) != 0:
        dish_index = dif_list.index(max(dif_list))
        score = B_list[dish_index]
        aoki_score += score

        del A_list[dish_index]
        del B_list[dish_index]
        del dif_list[dish_index]

print(takahashi_score - aoki_score)


### FIXED CODE ###

N = int(input())

A_list = []
B_list = []
dif_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)
    dif_list.append(A + B)

my_list = [[dif, a, b] for dif, a, b in zip(dif_list, A_list, B_list)]
my_list.sort(reverse=True)

takahashi_score = 0
aoki_score = 0

for i, list_items in enumerate(my_list):
    a = list_items[1]
    b = list_items[2]
    if i % 2 == 0:
        takahashi_score += a
    else:
        aoki_score += b

print(takahashi_score - aoki_score)
### BUGGY CODE ###

from itertools import permutations
n, m, r = map(int, input().split())
INF = 1 << 60

d = [[INF] * n for i in range(n)]
rs = list(map(int, input().split()))

for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

def warshall_floyd(d):
    """
    input
        d : 初期全点対距離
    output
        d : 最適化後全点対距離
    """
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d

d_optimized = warshall_floyd(d)
# print(d_optimized)

ans = INF
for inds in permutations([r-1 for r in rs]):
    cnt = 0
    for i in range(r-1):
        prev = inds[i]
        nxt = inds[i+1]
        cnt += d_optimized[prev][nxt]
    ans = min(ans,cnt)
print(ans)

### FIXED CODE ###

from itertools import permutations
n, m, r = map(int, input().split())
INF = 1 << 60

d = [[INF] * n for i in range(n)]
rs = list(map(int, input().split()))

for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

def warshall_floyd(d):
    """
    input
        d : 初期全点対距離
    output
        d : 最適化後全点対距離
    """
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    return d

d_optimized = warshall_floyd(d)
# print(d_optimized)

ans = INF
for inds in permutations([r-1 for r in rs]):
    cnt = 0
    for i in range(r-1):
        prev = inds[i]
        nxt = inds[i+1]
        cnt += d_optimized[prev][nxt]
    ans = min(ans,cnt)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))
score = [0]*(N+1)

score[1] = A[1]
for i in range(2, K+1):
    score[i] = score[i-1]*A[i]

for i in range(K+1, N+1):
    score[i] = score[i-1]*A[i]//A[i-K]
    print('Yes' if score[i] > score[i-1] else 'No')


### FIXED CODE ###

N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))


for i in range(K+1, N+1):
    print('Yes' if A[i] > A[i-K] else 'No')
### BUGGY CODE ###

from math import log2, ceil


class SegTree:
    #####単位元######
    ide_ele = 0

    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    #####segfunc######
    def segfunc(self, x, y):
        return x+y

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


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

seg_trees = []
ts = [chr(ord('a')+i) for i in range(26)]
for t in ts:
    init_val = [int(s == t) for s in S]
    seg_tree = SegTree(init_val)
    seg_trees.append(seg_tree)

ans = []
for _ in range(Q):
    i, l, r = input().split()
    i = int(i)
    l = int(l)
    if i == 1:
        for i,t in enumerate(ts):
            seg_trees[i].update(l-1, int(r == t))
    else:
        r = int(r)
        num = [seg_trees[i].query(l-1, r, 0, 0, seg_trees[i].num) > 0 for i, t in enumerate(ts)]
        ans.append(sum(num))

for a in ans:
    print(a)


### FIXED CODE ###

from math import log2, ceil


class SegTree:
    #####単位元######
    ide_ele = 0

    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    #####segfunc######
    def segfunc(self, x, y):
        return x|y

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


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

li = [1 << (ord(s) - ord('a')) for s in S]
seg_tree = SegTree(li)
ans = []
for _ in range(Q):
    i, l, r = input().split()
    i = int(i)
    l = int(l)
    if i == 1:
        seg_tree.update(l-1, 1 << (ord(r) - ord('a')))
    else:
        r = int(r)
        num = seg_tree.query(l-1, r, 0, 0, seg_tree.num)
        ans.append(bin(num).count('1'))

for a in ans:
    print(a)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]

ans=[]

for i in range(H):
    for j in range(W):
        sy=i
        sx=j
        for k in range(H):
            for l in range(W):
                ey=k
                ex=l
                route=deque([(sy,sx,0)])
                while route:
                    a,b,n=route.popleft()
                    if a==ey and b==ex:
                        ans.append(n)
                        break
                    if 0<=a<=H-1 and 0<=b<=W-1:
                        if S[a][b]=='.':
                            S[a][b]=='#'
                            route.append((a+1,b,n+1))
                            route.append((a-1,b,n+1))
                            route.append((a,b+1,n+1))
                            route.append((a,b-1,n+1))

print(max(ans))

### FIXED CODE ###

from collections import deque
import copy
H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]
S1=copy.deepcopy(S)
ans=[]

sy=0
sx=0
for i in range(H):
    for j in range(W):
        c=0
        route=deque([(i,j,0)])
        S=copy.deepcopy(S1)
        while route:
            a,b,n=route.popleft()
            c=n
            if 0<=a<=H-1 and 0<=b<=W-1:
                if S[a][b]=='.':
                    S[a][b]='#'
                    route.append((a+1,b,n+1))
                    route.append((a-1,b,n+1))
                    route.append((a,b+1,n+1))
                    route.append((a,b-1,n+1))
                    
        ans.append(c-1)

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

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

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

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

H,N = LI()
A = []
B = []
for i in range(N):
    a,b = LI()
    A.append(a)
    B.append(b)

dp = [inf]*(H+1)
ans = inf

dp[H] = 0

for i in range(N):
    for h in range(H+1)[::-1]:
        dp[h] = min(dp[h],dp[min(H,h+A[i])]+B[i])
print(dp[0])

### FIXED CODE ###

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

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

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

H,N = LI()
A = []
B = []
for i in range(N):
    a,b = LI()
    A.append(a)
    B.append(b)

dp = [inf]*(H+1)
ans = inf

dp[H] = 0

for i in range(N):
    for h in range(H+1)[::-1]:
        dp[h] = min(dp[h],dp[min(H,h+A[i])]+B[i])
print(dp[0])
### BUGGY CODE ###

n=int(input())
s=str(input())
ans=0
for i in range(0,1000):
  temp=[]
  temp.append(i//100)
  temp.append((i-(i//100)*100)//10)
  temp.append(i%10)
  cnt=0
  k=0
  for j in range(0,n):
    if temp[0]==int(s[j]):
      cnt=cnt+1
      k=j
      break
  if cnt==1:
    for j in range(k+1,n):      
      if temp[1]==int(s[j]):
        cnt=cnt+1
        k=j
        break
  if cnt==2:
    for j in range(k+1,n):
      if temp[2]==int(s[j]):
        ans=ans+1
        break
print(ans)

### FIXED CODE ###

n=int(input())
s=str(input())
ans=0
i=0
while i<1000:
  temp=i//100
  cnt=0
  k=0
  for j in range(0,n):
    if temp==int(s[j]):
      cnt=cnt+1
      k=j
      break
  if cnt==0:
    i=i+100
  else:
    temp=(i-(i//100)*100)//10
    for j in range(k+1,n):      
      if temp==int(s[j]):
        cnt=cnt+1
        k=j
        break
    if cnt==1:
      i=i+10
    else:
      temp=i%10
      i=i+1
      for j in range(k+1,n):
        if temp==int(s[j]):
          ans=ans+1
          break
print(ans)
### BUGGY CODE ###

import sys

while 1:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    sumMax = 0

    for i in range(len(a)+1):
        for j in range(i, len(a)+1):
            if sum(a[i:j]) > 0:
                sumMax = sum(a[i:j])

    print(sumMax)

### FIXED CODE ###

while 1:
    n = int(input())
    if n == 0:
        break
    a = []
    for _ in range(n):
        a.append(int(input()))

    dp = []
    dp.append(a[0])
    for i in range(1,len(a)):
        dp.append(max(dp[i-1] + a[i], a[i]))

    print(max(dp))
### BUGGY CODE ###

L, R = list(map(int, input().split()))

a = 0
ans = 10 ** 9
for i in range(L, R):
    for j in range(i + 1, R + 1):
        a = (i * j) % 2019
        ans = min(a, ans)
print(ans)

### FIXED CODE ###

L, R = list(map(int, input().split()))

a = 0
ans = 10 ** 9
r = min((L + 2018), R)

for i in range(L, r):
    n = min((i + 2019), R)
    for j in range(i + 1, n + 1):
        a = (i * j) % 2019
        # print(a)
        ans = min(a, ans)
print(ans)
### BUGGY CODE ###

import collections
n,k = map(int , raw_input().split())

q = collections.deque([])
cumul = 1
prev = 0
for ai in map(int, raw_input().split()):
	cumul *= ai
	q.append(ai)
	if len(q) == k + 1:
		cumul /= q.popleft()


	if len(q) == k:
		if prev != 0:
			print 'Yes' if cumul > prev else 'No'
		prev = cumul

### FIXED CODE ###

n,k = map(int , raw_input().split())
ais = map(int, raw_input().split())
for ii in range(k, n):
	print 'Yes' if ais[ii] > ais[ii - k] else 'No'
### BUGGY CODE ###

import heapq
n = int(input())
a = list(map(int,input().split()))
p = []
for b in a:
  heapq.heappush(p,b)
for i in range(n):
  x = heapq.heappop(p)
  y = a.index(x)
  print(y+1,end=' ')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0] * n
for i,j in enumerate(a):
  b[j-1] = i+1
print(' '.join(map(str,b)))
### BUGGY CODE ###

def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [[0 for _ in range(h+1)] for _ in range(h+1)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    w[x][y] = 0
                    for z in range(h-max(x,y)):
                        if c[y+z][j] == c[x+z][j+1]:
                            w[x][y] += 1
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x][y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[x-1][y]
                    continue
                w[x][y] = w[x-1][y-1]
                if c[h-x][j] == c[h-y][j+1]:
                    w[x][y] -= 1
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x][y-1],dp[(x-1)*(h+1)+y]+w[x-1][y])
        ans += dp[(h+1)**2-1]
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[-1]
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n,m = map(int,input().split())
dic = {}
lst = [list(map(int,input().split())) for _ in range(m)]
for p,y in lst:
    if p in dic.keys():
        dic[p].append(y)
    else:
        dic[p] = [y]
nx_dic = {}
for k, v in dic.items():
    nx_dic[k] = sorted(v)

for p,y in lst:
    print(str(p).zfill(6)+str(nx_dic[p].index(y)+1).zfill(6))

### FIXED CODE ###

n,m = map(int,input().split())
city_inf = []
for i in range(m):
    array = [i]
    array.extend(list(map(int,input().split())))
    city_inf.append(array)

city_inf.sort(key=lambda x:x[2])
order_counter = {}

for list in city_inf:
    if list[1] in order_counter.keys():
        order_counter[list[1]] += 1
        list.append(order_counter[list[1]])
    else:
        order_counter[list[1]] = 1
        list.append(1)

city_inf.sort(key=lambda x:x[0])
zero_p = ''
zero_y = ''
for list in city_inf:
    zero_p = '0'*(6-len(str(list[1])))
    zero_y = '0'*(6-len(str(list[3])))
    list.append(zero_p + str(list[1]) + zero_y + str(list[3]))
    print(list[4])
### BUGGY CODE ###

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
if n<1000:
  for i in range(1,n):
    if m%i==0 and (is_prime(i) or i==1) and is_prime(m//i) and (i==1 or m//i<n):
      print('1')
      exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m-i-n>0 and m%(m-i-n)==0 and m//(m-i-n)>n:
    print(m-i-n)
    break


### FIXED CODE ###

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and (is_prime(i) or i==1) and is_prime(m//i) and (i==1 or m//i<n):
    print('1')
    exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m-i-n>0 and m%(m-i-n)==0 and m//(m-i-n)>n:
    print(m-i-n)
    break
### BUGGY CODE ###

def main():
    import heapq
    import sys
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra

    input = sys.stdin.readline

    MAX  = 10 ** 15

    N, M, s, t = map(int, input().split())

    edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
    g1 = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
    g2 = csr_matrix((edge[3], (edge[:2] - 1)), (N, N))

    d1 = dijkstra(g1, directed = False, indices = s - 1)
    d2 = dijkstra(g2, directed = False, indices = t - 1)

    # print (d1)
    # print (d2)

    # print (g1)
    # print (g2)

    # print (edge)

    tmp = MAX
    ans = [MAX] * N
    for i in range(N - 1, -1, -1):
        tmp = min(tmp, d1[i] + d2[i])
        ans[i] -= int(tmp)

    print (*ans, sep = '\n')

if __name__ == "__main__":
    main()



### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

MAX  = 10 ** 15

N, M, s, t = map(int, input().split())

g1 = [[] for _ in range(N + 1)]
g2 = [[] for _ in range(N + 1)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    
    g1[u].append((a, v))
    g1[v].append((a, u))
    
    g2[u].append((b, v))
    g2[v].append((b, u))

d1 = [MAX] * (N + 1)
d2 = [MAX] * (N + 1)

d1[s] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, s]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d1[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g1[v])): #頂点vの隣接リストを走査
        e = g1[v][i]
        if d1[e[1]] > d1[v] + e[0]: #距離が更新できるかを検討
            d1[e[1]] = d1[v] + e[0]
            heapq.heappush(pque, [d1[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d1)

d2[t] = 0 #始点の距離を0にする
pque = []
heapq.heappush(pque, [0, t]) #要素を[距離、頂点]として管理　最初の位置を入れる

while len(pque) != 0: #queの中に要素が残っている時
    p = heapq.heappop(pque) #最も距離が短いものを取り出す
    v = p[1] #距離が最も短い頂点
    if d2[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
        continue
    for i in range(len(g2[v])): #頂点vの隣接リストを走査
        e = g2[v][i]
        if d2[e[1]] > d2[v] + e[0]: #距離が更新できるかを検討
            d2[e[1]] = d2[v] + e[0]
            heapq.heappush(pque, [d2[e[1]], e[1]]) #更新できた場合、その値をpqueに入れる

# print (d2)

tmp = MAX
ans = [MAX] * N
for i in range(N, 0, -1):
    tmp = min(tmp, d1[i] + d2[i])
    ans[i - 1] -= tmp

print (*ans, sep = '\n')