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

import sys
from io import StringIO
import unittest

sys.setrecursionlimit(10 ** 7)


def memoize(f):
    cache={}
    def helper(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return helper


def resolve():
    n = int(input())
    h = list(map(int, input().split()))
    inf = n * 10 ** 7

    """
    ボトムアップ型: for loopを使う
    ans = [inf for _ in range(n)]
    ans[0] = 0
    ans[1] = abs(h[1] - h[0])

    for i in range(2, n):
        ans[i] = min(ans[i], ans[i - 1] + abs(h[i] - h[i - 1]), ans[i - 2] + abs(h[i] - h[i - 2]))

    print(ans[-1])
    """

    # トップダウン(メモ再帰型)
    memo = [inf for _ in range(n)]

    # @memoize
    def dp(n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return abs(h[1] - h[0])
        else:
            return min(dp(n - 1) + abs(h[n] - h[n - 1]), dp(n - 2) + abs(h[n] - h[n - 2]))

    print(dp(n - 1))

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
10 30 40 20"""
        output = """30"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """2
10 10"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
30 10 60 10 60 50"""
        output = """40"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

### FIXED CODE ###

import sys
from io import StringIO
import unittest

def resolve():
    n = int(input())
    h = list(map(int, input().split()))

    inf = n * 10 ** 7
    ans = [inf for _ in range(n)]
    ans[0] = 0
    ans[1] = abs(h[1] - h[0])

    for i in range(2, n):
        ans[i] = min(ans[i], ans[i - 1] + abs(h[i] - h[i - 1]), ans[i - 2] + abs(h[i] - h[i - 2]))

    print(ans[-1])


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4
10 30 40 20"""
        output = """30"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """2
10 10"""
        output = """0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6
30 10 60 10 60 50"""
        output = """40"""
        self.assertIO(input, output)

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

n, K = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**10
dp = [inf]*n
dp[0] = 0
for i in range(1, n):
    di = dp[i]
    hi = h[i]
    for k in range(max(i-K, 0), i):
        a = dp[k]+abs(hi-h[k])
        if di > a:
            di = a
    dp[i] = di
print(dp[n-1])

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = 10**10
    dp = [inf]*n
    dp[0] = 0
    for i, (di, hi) in enumerate(zip(dp[1:], h[1:]), 1):
        num = max(i-K, 0)
        for dk, hk in zip(dp[num:i], h[num:i]):
            a = dk+abs(hi-hk)
            if di > a:
                di = a
        dp[i] = di
    print(dp[n-1])

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

s=input()
b=0
m=len(s)
c=0
for i in range(m-1,2,-1):
    a=s[i-2]+s[i-1]+s[i]
    for j in range(i-3,-1,-1):
        # if c==1 and int(s[j])%3!=0:
        #     c=0
        #     continue
        a=str(a)
        a=int(s[j]+a)
        # print(a)
        # c=0
        # if a%3!=0:
        #     continue
        # c=1
        if a%2019==0:
            # print(b)
            b+=1

            if i>=3:
                c=int(s[i-3]+s[i-2]+s[i-1]+s[i])
                if c%2019==0:

                    b+=1
                    break

print(b)


### FIXED CODE ###

s=input()
b=0
m=len(s)
c=[0 for i in range(2019)]
c[0]=c[0]+1
a=""
e=0
f=1
s= ''.join(list(reversed(s)))
for i in s:
    e+=int(i)*f
    g=e%2019
    c[g]+=1
    f*=10
    f%=2019
e = sum(i * (i - 1) // 2 for i in c)
print(e)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [False] * (W * H)
    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i, j, 0))
                k = i * W + j
                visited[k] = True
    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k] and 0 < n:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if rem == 0:
            break
        if 0 < j and not visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1]:
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W]:
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

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

def myAnswer(N:int,P:list) -> int:
   total = 0
   for i in range(N):
      for j in range(0,i):
         if(P[j]< P[i]):
            break
      else:
         total += 1
   return total

def modelAnswer():
   tmp=1
def main():
   N = int(input())
   P = list(map(int,input().split()))
   print(myAnswer(N,P[:]))

if __name__ == '__main__':
   main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
P = list(map(int,input().split()))


cnt=1
M=P[0]#現在の最小値
for i in range(1,N):
    if(M > P[i]):#Pの値が現在の最小値より小さかったら最小値を更新しcnt++する
        M=P[i]
        cnt+=1



print(cnt)
### BUGGY CODE ###

from itertools import combinations
from operator import itemgetter
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))

P = [abs(x1 - x2) for x1, x2 in combinations(X, 2)]
P = set(P)
if 0 in P:
    P.remove(0)
P = list(P)
Q = [abs(y1 - y2) for y1, y2 in combinations(Y, 2)]
Q = set(Q)
if 0 in Q:
    Q.remove(0)
Q = list(Q)
ans = 10**10
geta = 10**10
for p in P:
    S = {(x+p)*geta+y for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)

for q in Q:
    S = {x*geta+y+q for x, y in XY}
    la = 0
    for x, y in XY:
        if x*geta + y not in S:
            la += 1
    ans = min(ans, la)

for p in P:
    for q in Q:
        S1 = {(x+p)*geta+y+q for x, y in XY}
        S2 = {(x+p)*geta+y-q for x, y in XY}
        la1 = 0
        la2 = 0
        for x, y in XY:
            if x*geta + y not in S1:
                la1 += 1
            if x*geta + y not in S2:
                la2 += 1
        ans = min(ans, la1, la2)
        
if N == 1:
    ans = 1
print(ans)


### FIXED CODE ###

from collections import Counter
from itertools import combinations
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()
A = Counter()
for (x1, y1), (x2, y2) in combinations(XY, 2):
    A[(x1-x2, y1-y2)] += 1
if N == 1:
    print(1)
else:
    print(N - max(A.values()))
### BUGGY CODE ###

from itertools import product as prod

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

gr = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    gr[a].append((b, c))
    gr[b].append((a, c))

def dist(i, j, gr=gr):
    tmp_d = float("inf")
    if i == j:
        return 0
    for (node, d) in gr[i]:
        if node == j:
            tmp_d = d
    gr_cp = gr.copy()
    gr_cp[i] = []
    routes = [d + dist(n, j, gr=gr_cp) for (n, d) in gr[i]]

    return min(routes + [tmp_d])

ans = 0
for i in range(n):
    for (j, d) in gr[i]:
        if dist(i, j) < d:
            ans += 1

print(ans // 2)


### FIXED CODE ###

import copy
from itertools import product as prod

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

wait = [[float("inf") for _ in range(n)] for _ in range(n)]
for i in range(n):
    wait[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    wait[a-1][b-1] = c
    wait[b-1][a-1] = c

dist = copy.deepcopy(wait)
for k, i, j in prod(range(n), range(n), range(n)):
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    dist[j][i] = min(dist[j][i], dist[j][k] + dist[k][i])

ans = 0
for i, j in prod(range(n), range(n)):
    if not wait[i][j] == float("inf") and dist[i][j] < wait[i][j]:
        ans += 1

print(ans // 2)
### BUGGY CODE ###

#abc177 e
import sys,math,collections,itertools
import functools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
fact = set()
for a in A:
    if a==1:
        fact.add(1)
        continue
    if a%2 == 0 and 2 in fact:
        break
    while a%2==0:
        fact.add(2)
        a//=2
            
    i =3
    while i*i <= a:
        if a%i ==0 and i in fact:
            break
        while a%i==0:
            fact.add(i)
            a//=i
        else:
            i +=2
    else:
        if a != 1:
            if a in fact:
                break
            fact.add(a)
        continue
    break
else:
    print('pairwise coprime')
    exit()
if functools.reduce(math.gcd,A)!=1:
    print('not coprime')
else:
    print('setwise coprime')





### FIXED CODE ###

#abc177 e
import sys,math,collections,itertools
import functools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
fact = set()
for a in A:
    if a==1:
        fact.add(1)
        continue
    if a%2 == 0 and 2 in fact:
        break
    while a%2==0:
        fact.add(2)
        a//=2
            
    i =3
    while i*i <= a:
        if a%i ==0 and i in fact:
            break
        while a%i==0:
            fact.add(i)
            a//=i
        else:
            i +=2
    else:
        if a != 1:
            if a in fact:
                break
            fact.add(a)
        continue
    break
else:
    print('pairwise coprime')
    exit()
if functools.reduce(math.gcd,A)!=1:
    print('not coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###



n, k = [int(x) for x in input().split()]

hs = [int(x) for x in input().split()]

dp = [0] * n

for i in range(1, n):
	smallest = 1000*1000*1000
	for j in range(max(0,i-k), i):
		#print("i =", i, ", j =", j)
		smallest = min(smallest, dp[j] + abs(hs[i] - hs[j]))
	dp[i] = smallest
    
print(dp[n-1])



### FIXED CODE ###

n, k = [int(x) for x in input().split()]

hs = [int(x) for x in input().split()]

dp = [0] * n

for i in range(1, min(k,n)):
	dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[:i], hs[:i])])

if k < n:
	for i in range(k, n):
		dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[i-k:i], hs[i-k:i])])

print(dp[-1])
### BUGGY CODE ###

N = int(input())
S = list(map(lambda x: 1 if x == "W" else 0, input()))

N -= 1

min_turn = min(N - sum(S[1:]), sum(S[:N - 2]))
for i in range(1, N - 1):
    to_east = sum(S[:i])
    to_west = N - i - sum(S[i + 1:])
    min_turn = min(to_east + to_west, min_turn)

print(min_turn)


### FIXED CODE ###

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

# import random
# N = 3 * 10 ** 5
# S = "".join(["WE"[random.randint(0, 1)] for _ in range(N)])

to_east = 0
to_west = S[1:].count("E")

min_turn = to_east + to_west
for i in range(1, N):
    if min_turn == 0:
        break
    if S[i - 1] == "W":
        to_east += 1
    if S[i] == "E":
        to_west -= 1
    min_turn = min(to_east + to_west, min_turn)

print(min_turn)
### BUGGY CODE ###

# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

# 無限大の値
f_inf = float('inf')
# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# 初期条件
dp[0] = 0

for i in range(0, n):
    for j in range(1, k+1):
        if i-j >= 0:
            dp[i] = chmin(dp[i], dp[i-j] + abs(h[i] - h[i - j]))

print(dp[n-1])



### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = np.zeros(n, dtype=int)
h = np.array(h)


for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
from numpy.linalg import norm
xs, ys, xt, yt = map(int, input().split())
N = int(input())
p=[(xs, ys, 0), (xt, yt, 0)]
edge = [[-1]*(N+2) for _ in range(N+2)]
edge[0][1] = edge[1][0] = norm([xs-xt, ys-yt])
for i in range(N):
    x, y, r = map(int, input().split())
    for j in range(len(p)):
        x1, y1, r1 = p[j]
        edge[i+2][j] = edge[j][i+2] = max(norm([x-x1, y-y1])-r-r1, 0.0)
    p.append((x, y, r))
G = csgraph_from_dense(edge,null_value=-1)  
print(dijkstra(G,indices=0)[1])   


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

xs, ys, xt, yt = map(int, input().split())
n = int(input())

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[-1]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)

#ここから
G = csgraph_from_dense(edge,null_value=-1)
print(dijkstra(G,indices=0)[1])
### BUGGY CODE ###

import sys
from collections import defaultdict

sys.setrecursionlimit(4000)


def main():
  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = defaultdict(int)

  def cal(ln, rn):
    if ln + rn > n:
      return

    p, a = arr[ln + rn - 1]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

    cal(ln + 1, rn)
    cal(ln, rn + 1)

  cal(1, 0)
  cal(0, 1)

  print(max([dp[i, n - i] for i in range(n + 1)]))


main()


### FIXED CODE ###


def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
from copy import deepcopy

h, w = map(int, input().split())
board = [list(input().rstrip()) for j in range(h)]

start_list = []

# すべてのスタート地点を記録
for i in range(w):
    for j in range(h):
        if board[j][i] == "#":
            start_list.append([i, j])

# dx,dy
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs():

    # キュー
    task_deque = deque()
    # キューにスタート地点リストを追加
    task_deque.append(start_list)
    next_task_list = []
    turn_count = 0

    while task_deque:
        next_task_list.clear()
        task_list = task_deque.popleft()


        # タスクリストからそれぞれの座標を取り出す
        for x, y in task_list:

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

                # 条件に合う座標をnext_task_listに追加
                if 0 <= nx < w and 0 <= ny < h and board[ny][nx] == ".":
                    board[ny][nx] = "#"
                    next_task_list.append([nx, ny])


        # 一つもnext_task_listに入っていなければ終了
        if len(next_task_list) == 0:
            return turn_count

        # タスクリストが全部終わったらキューに追加
        turn_count += 1
        lst = deepcopy(next_task_list)
        task_deque.append(lst)


print(bfs())


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
# from copy import deepcopy


def bfs(h, w, board, start_list, dx, dy):

    # キュー
    task_deque = deque()
    # キューにスタート地点リストを追加
    task_deque.append(start_list)
    next_task_list = deque()
    turn_count = 0

    while task_deque:
        next_task_list.clear()
        task_list = task_deque.popleft()


        # タスクリストからそれぞれの座標を取り出す
        for x, y in task_list:

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

                # 条件に合う座標をnext_task_listに追加
                if 0 <= nx < w and 0 <= ny < h and board[ny][nx] == ".":
                    board[ny][nx] = "#"
                    next_task_list.append([nx, ny])


        # 一つもnext_task_listに入っていなければ終了
        if len(next_task_list) == 0:
            return turn_count

        # タスクリストが全部終わったらキューに追加
        turn_count += 1
        lst = []
        for task in next_task_list:
            lst.append(task)
        task_deque.append(lst)



h, w = map(int, input().split())
board = [list(input().rstrip()) for j in range(h)]

start_list = deque()

# すべてのスタート地点を記録
for i in range(w):
    for j in range(h):
        if board[j][i] == "#":
            start_list.append([i, j])

# dx,dy
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


print(bfs(h, w, board, start_list, dx, dy))
### BUGGY CODE ###

n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort()
A_l.reverse()

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    yb = n - (j-1)
    x = A_l[j-1][1] + 1
#    if yb-i <0:
#        dp[j][0] = -float('inf')
#    else:
    dp[j][0] = dp[j-1][0] + A_l[j-1][0]*(yb-x)
for k in range(1,n+1): # all go smaller
    ys = 1 + (k-1)
    x = A_l[k-1][1] + 1
#    if i-ys <0:
#        dp[0][k] = -float('inf')
#    else:
    dp[0][k] = dp[0][k-1] + A_l[k-1][0]*(x-ys)

for j in range(1,n+1):
    for k in range(1,n-j+1):
        yb = n - (j-1)
        ys = 1 + (k-1)
        x = A_l[j+k-1][1] + 1
        j_plus = A_l[j+k-1][0]*(yb-x)
        k_plus = A_l[j+k-1][0]*(x-ys)
        if j_plus <0:
            j_plus = -float('inf')
        elif k_plus <0:
            k_plus = -float('inf')
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])

### FIXED CODE ###

n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort(reverse=True)

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(n-(j-1) - (i+1))
for k in range(1,n+1): # all go smaller
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1) - (1+(k-1)))

for j in range(1,n+1):
    for k in range(1,n-j+1):
        a, i = A_l[j+k-1]
        j_plus = a*(n-(j-1) - (i+1))
        k_plus = a*((i+1) - (1+(k-1)))
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])
### BUGGY CODE ###

a = [[0] * 3005 for i in range(3005)]
dp = [[[0] * 4 for i in range(3005)] for j in range(3005)]
R,C,K = map(int, input().split())

for i in range(K):
  r,c,v = map(int, input().split())
  a[r-1][c-1] = v

for i in range(R):
  for j in range(C):
    for k in range(2, -1, -1):
      dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+a[i][j])
    for k in range(4):
      dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
      dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])
    
ans = 0
for k in range(4):
  ans = max(ans, dp[R-1][C-1][k])
print(ans)


### FIXED CODE ###

R,C,K = map(int, input().split())
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]
for i in range(K):
  r,c,v = map(int, input().split())
  a[r-1][c-1] = v

for i in range(R):
  for j in range(C):
    for k in range(2, -1, -1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j]+a[i][j])
    for k in range(4):
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])

    
ans = 0
for k in range(4):
  ans = max(ans, dp[k][R-1][C-1])
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import heapq

n,m,s,t = map(int, input().split())
s -= 1
t -= 1
ea = [[] for _ in range(n)]
eb = [[] for _ in range(n)]
for _ in range(m):
    v,u,a,b = map(int, input().split())
    v -= 1
    u -= 1
    ea[v].append((u,a))
    ea[u].append((v,a))
    eb[v].append((u,b))
    eb[u].append((v,b))


def dijkstra(e,n,s):
    d = [None]*n
    d[s] = 0
    q = [(s,0)]
    heapq.heapify(q)

    while len(q)>0:
        v,c = heapq.heappop(q)
        if d[v] is not None and d[v]<c:
            continue
        for u,ud in e[v]:
            if d[u] is None or d[u]>c+ud:
                d[u] = c + ud
                heapq.heappush(q, (u, d[u]))
    return d


da = dijkstra(ea,n,s)
db = dijkstra(eb,n,t)
res = []
m = None
for i in range(n-1,-1,-1):
    r = da[i]+db[i]
    if m is None:
        m = r
    else:
        m = min(m,r)

    res.append(m)

for i in range(n-1,-1,-1):
    print(10**15 - res[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
n,m,s,t = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u,v,a,b = map(int, input().split())
    g[u].append((v,(a,b)))
    g[v].append((u,(a,b)))

inf = 10**18
def dijkstra(s, currency):
    d = [inf]*(n+1)
    d[s] = 0

    que = [(d[s],s)]
    heapq.heapify([que])
    while len(que)>0:
        _,v = heapq.heappop(que)
        for u,c in g[v]:
            if d[v]+c[currency]>=d[u]:
                continue
            d[u] = d[v]+c[currency]
            heapq.heappush(que, (d[u], u))
    return d

yen_c = dijkstra(s,0)
snuuk_c = dijkstra(t,1)

res = [0]*n
res[n-1] = yen_c[n] + snuuk_c[n]
for i in range(n-2,-1,-1):
    res[i] = min(res[i+1], yen_c[i+1]+snuuk_c[i+1])

for r in res:
    print(10**15-r)