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

import numpy as np
from numba import jit

@jit
def main():
    H, W, M = map(int, input().split())
    row = np.zeros(W)
    col = np.zeros(H)
    memo = []
    for _ in range(M):
        h, w = map(int, input().split())
        h -=1
        w -=1
        row[w] += 1
        col[h] += 1
        memo.append((h, w))

    col_max = col.max()
    row_max = row.max()

    max_col_indexs = np.where(col == col_max)[0]
    max_row_indexs = np.where(row == row_max)[0]

    ans = col_max + row_max -1
    for c in max_col_indexs:
        for r in max_row_indexs:
            if (c, r) not in memo:
                ans = ans = col_max + row_max
                break

    print(int(ans))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    H, W, M = map(int, input().split())
    row = np.zeros(W)
    col = np.zeros(H)
    memo = []
    for _ in range(M):
        h, w = map(int, input().split())
        h -=1
        w -=1
        row[w] += 1
        col[h] += 1
        memo.append((h, w))

    col_max = col.max()
    row_max = row.max()

    max_col_indexs = np.where(col == col_max)[0]
    max_row_indexs = np.where(row == row_max)[0]

    ans = col_max + row_max -1
    memo = set(memo)
    for c in max_col_indexs:
        for r in max_row_indexs:
            if (c, r) not in memo:
                ans = ans = col_max + row_max
                print(int(ans))
                exit()

    print(int(ans))

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

n = int(input())
x = list(map(int, input().strip().split()))
sum=0
for i in range(0,n):
    x[i] %= (10**9+7)
for i in range(0,n-1):
    for j in range(i+1,n):
        sum += ((x[i]*x[j])%(10**9+7))

print(sum%(10**9+7))

### FIXED CODE ###

n = int(input())
x = list(map(int, input().strip().split()))
sum=0
minsum=0
for i in range(0,n):
    minsum += x[i]
for i in range(0,n-1):
    minsum-=x[i]
    sum += x[i]*minsum
    if(sum>10**9+7):
        sum%=(10**9+7)
print(sum)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

n = int(input())
l = make_divisors(n)
ans = make_divisors(n-1)
for i in l:
  m=n
  if i==1:
    continue
  else:
    while(m%i==0):
      m//=i
  if m==1:
    ans.append(i)
  else:
    if i in make_divisors(m-1):
      ans.append(i)
ans=set(ans)
print(len(ans)-1)

### FIXED CODE ###

def main():
  def make_divisors(n):
      divisors = []
      for i in range(1, int(n**0.5)+1):
          if n % i == 0:
              divisors.append(i)
              if i != n // i:
                  divisors.append(n//i)
      divisors.sort()
      return divisors

  n = int(input())
  l = make_divisors(n)
  ans = make_divisors(n-1)
  for i in l:
    m=n
    if i==1:
      continue
    else:
      while(m%i==0):
        m//=i
    if m==1:
      ans.append(i)
    else:
      if i in make_divisors(m-1):
        ans.append(i)
  ans=set(ans)
  print(len(ans)-1)  

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

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


def primes(n):
    is_prime = [True] * (n + 1)
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return {i: True for i in range(n + 1) if is_prime[i]}

import fractions
def common_divisors(a, b):
    a = fractions.gcd(a, b)
    divisors =  [d for d in range(2, a // 2 + 1) if a % d == 0] + [a]
    if not 1 in divisors:
        divisors.append(1) 
    return divisors, a


d, max_a= common_divisors(A, B)
p = set(primes(max_a))
ans = 0
for x in d:
    if x in p:
        ans += 1
#print(p)
#print(d)
print(ans)

### FIXED CODE ###

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

import math

def is_prime(n):
    if n == 1: return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

import fractions
x = fractions.gcd(A, B)
divisors = make_divisors(x)
ans = 0
for d in divisors:
    if is_prime(d):
        ans += 1
print(ans)
### BUGGY CODE ###

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

dp = [10**9+10] * N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2, N):
  for j in range(1,min(i+1,K+1)):
    tmp = dp[i-j]+abs(h[i]-h[i-j])
    dp[i] = min(dp[i], tmp)
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(N):
  tmp = []
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i-j] + abs(h[i] - h[i-j]), c[i])
print(c[-1])
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]
# a = [int(input()) for x in range (n)]

b = [0] * n
if(a[0] > a[-1]) : mi = a[-1]
else : mi = a[0]


for x in range(0,mi*2+1,2) :
    # print(x)
    b[0] = x

    for i in range(1,n) :
        b[i] = 2 * a[i-1] - b[i-1]
        # print(b)
        if (b[i] < 0) : 
            break

    else :
        if (b[-1] + b[0] == 2 * a[-1]) :
            break


s = str(b)
# for i in b :
#     s = s + str(i) + " " 

# print(s)
print(str(b).strip("[]").replace(",",""))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]

b = [0] * n
if(a[0] > a[-1]) : mi = a[-1]
else : mi = a[0]

aa = 0
for i in range(1, n, 2) :
    aa += a[i]
b[0] = sum(a) - 2 * aa

for i in range(1,n) :
    b[i] = 2 * a[i-1] - b[i-1]
print(str(b).strip("[]").replace(",",""))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
now = A[0]
start_idx = 0
while now <= A[-1] + 1:
    tmp_max = 0
    flag = True
    for i in range(start_idx, N):
        if flag and now - 1 == A[i]:
            flag = False
            start_idx = i
        if now - 1 <= A[i] <= now + 1:
            tmp_max += 1
    ans = max(tmp_max, ans)
    now += 1
print(ans)

### FIXED CODE ###

from bisect import *
N = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
min_a = min(a)
max_a = max(a)
for x in range(min_a , max_a + 1):
    r = bisect_right(a , x + 1)
    l = bisect_left(a , x - 1)
    tmp_max = r - l
    if tmp_max > ans:
        ans = tmp_max
print(ans)
### BUGGY CODE ###

N, K = [int(x) for x in input().split()] 
h = [int(x) for x in input().split()]

def chmin(a, b):
    return a if a <= b else b

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i + j < len(dp):
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
        
print(dp[-1])

### FIXED CODE ###


N, K = [int(x) for x in input().split()] 
h = [int(x) for x in input().split()]

def chmin(a, b):
    return a if a <= b else b

dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i + j >= len(dp):
            break
        else:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))
        
print(dp[-1])
### BUGGY CODE ###

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

arrSum = list(sum(A[:idx+1]) for idx in range(N))

ans = float('inf')
##2分する区切り目の左のインデックスi: 1 ～ (N - 3)
nextJ, nextK = -1, -1
for i in range(1, (N - 3) + 1):
    ##左側の区間の右端はi番目まである
    ##区切り目の左のインデックスj: 0 ～ (i - 1)
    buf = float('inf')
    nextJ = max(nextJ, 0)
    for j in range(nextJ, i):
        sumB = arrSum[j]
        sumC = arrSum[i] - arrSum[j]
        d = abs(sumB - sumC)
        if buf > d:
            buf = d
            P = sumB
            Q = sumC
            nextJ = j
        else:
            break
    ##右側の区間の左端は(i + 1)番目
    ##区切り目の左のインデックスk: (i + 1) ～ (N - 2)
    buf = float('inf')
    nextK = max(nextK, (i + 1))
    for k in range(nextK, (N - 2) + 1):
        sumD = arrSum[k] - arrSum[i]
        sumE = arrSum[N-1] - arrSum[k]
        d = abs(sumD - sumE)
        if buf > d:
            buf = d
            R = sumD
            S = sumE
            nextK = k
        else:
            break
    arr = list((P, Q, R, S))
    ans = min(ans, max(arr) - min(arr))
print(ans)

### FIXED CODE ###

##https://beta.atcoder.jp/contests/abc102/submissions/2779056
n = int(input())
a = list(map(int, input().split()))
s = [a[0]]
for i in range(n-1):
    s.append(s[i] + a[i+1])
ans = s[n-1]

##i,j,kは左側の区間の右端
##iは1からN-3まで
j = 0
k = 2             
for i in range(1, (n - 3) + 1):
    ##BC(i)DE
    ##BCの区間[0, i]: 最低でも2要素→0,1を取るのでi=1から
    ##DEの区間[i+1, N-1]: 最低でも2要素→N-2, N-1を取るので、i+1=N-2よりi=N-3まで

    ##B(j)C(i)DE
    #Bの区間[0, j]
    #Cの区間[j+1, i]
    ##sumB = s[j]
    ##sumC = s[i] - s[j]
    while abs(s[i] - 2 * s[j]) > abs(s[i] - 2 * s[j+1]):
        j += 1

    ##B(j)C(i)D(k)E
    #Dの区間[i+1, k]
    #Eの区間[k+1, N-1]
    ##sumD = s[k] - s[i]
    ##sumE = s[N-1] - s[k]
    while abs(s[n-1] - 2 * s[k] + s[i]) > abs(s[n-1] - 2 * s[k+1] + s[i]):
        k += 1
             
    pqrs = list((s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k]))
    ans = min(ans, max(pqrs) - min(pqrs))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

from collections import deque

def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = deque()
    for i in range(n):
        ai = list(map(int, input().split()))
        for j in range(n - 1):
            x = min(i, ai[j] - 1)
            y = max(i, ai[j] - 1)
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1] - 1)
                yp = max(i, ai[j - 1] - 1)
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = deque()
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

from collections import deque

def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = deque()
    for i in range(n):
        ai = list(map(int, input().split()))
        for j in range(n - 1):
            x = min(i, ai[j] - 1)
            y = max(i, ai[j] - 1)
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1] - 1)
                yp = max(i, ai[j - 1] - 1)
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = deque()
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

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

N = int(raw_input())
A = map(int, raw_input().split())

plus = [A[i] + i for i in range(N)]
minus = [j - A[j] for j in range(N)]

count = 0
for i in range(N):
	h = A[i]
	for j in range(i+h+1, N):
		if plus[i] == minus[j]:
			count += 1
print count

### FIXED CODE ###

N = int(raw_input())
A = map(int, raw_input().split())

x_occurance = {}
minus = []
for i in range(N):
	p = A[i] + i
	m = i - A[i]
	x_occurance[p] = x_occurance.get(p, 0) + 1
	minus.append(m)

count = 0
for i in range(N):
	count += x_occurance.get(minus[i], 0) 

print count
### BUGGY CODE ###

from collections import Counter

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

# サイズA_maxのbool配列dpを用意し、trueで初期化する
A_max = max(A)
dp = [True] * (A_max + 1)

# 数列の要素を昇順に見る O(nloglogn)
for x in range(A_max):
    # すでに計算していれば再度計算しない
    if not dp[x]:
        continue
    # xが数列Aに含まれているとき、xより大きいxの倍数yについて、dp[y]をfalseに変更する
    if x in A:
        t = 2
        while x * t <= A_max:
            dp[x * t] = False
            t += 1

# 同じ値が複数存在するかチェックする用のカウンタ
counter = Counter(A)

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is True:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

# 同じ値が複数存在するかチェックする用のカウンタ
counter = Counter(A)

# D[a] = True: Aにaより小さいaの約数が存在する
A_max = max(A)
dp = {a: False for a in A}

for a in A:
    # xが数列Aに含まれているとき、aより大きいaの倍数tについて、dp[a * t]をTrueに変更する
    if counter[a] > 0:
        t = 2
        while a * t <= A_max:
            dp[a * t] = True
            t += 1

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is False:
        ans += 1

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

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
i_list = [0] * (N+1)
cnt = 0

for k in range(K, N+1):
    A_sum = A[cnt]
    for i in range(cnt, K+cnt-1):
        A_sum = A_sum * A[i+1]
    i_list[k] = A_sum
    A_sum = 0
    cnt = cnt + 1

for k in range(K, N):
    if i_list[k] < i_list[k+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
i_list = [0] * N

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

n=int(input())
s=input()
l=[0+(s[0]=="W")]
for i in range(1,n):
  l.append(l[i-1]+(s[i]=="W"))
r=[0+(s[-1]=="E")]
for i in range(1,n):
  r.append(r[i-1]+(s[::-1][i]=="E"))
print(min([x+y for (x,y) in zip(l,r[::-1])])-1)

### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    ans = c = s[1:].count("E")
    for i in range(1, n):
        if s[i - 1] == "W":
            c += 1
        if s[i] == "E":
            c -= 1
        ans = min(ans, c)
    print(ans)


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

def main():
    from bisect import bisect_left
    from collections import deque
    import sys
    input = sys.stdin.readline

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [None for _ in range(N)]
    lis[0] = [inf] * N

    dq = deque([0])

    while dq:
        v = dq.popleft()

        if ans[v]: continue

        i = bisect_left(lis[v], a[v])
        lis[v][i] = a[v]
        ans[v] = bisect_left(lis[v], inf)

        for u in g[v]:
            if ans[u]: continue
            dq.append(u)
            lis[u] = lis[v].copy()

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


if __name__ == '__main__':
    main()

# dp[i]=長さiの増加部分列の末尾としてありえる最小値
# というテーブルを持っておいて、数列を列を前から見ながら二分探索で更新箇所を探す


### FIXED CODE ###

def main():
    from bisect import bisect_left
    import sys
    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [inf] * N
    lis[0] = a[0]

    def dfs(v, p=-1):
        ans[v] = bisect_left(lis, inf)
        for u in g[v]:
            if p == u: continue
            i = bisect_left(lis, a[u])
            prev_at_i = lis[i]
            lis[i] = a[u]
            dfs(u, v)
            lis[i] = prev_at_i

    dfs(0)

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


if __name__ == '__main__':
    main()

# dp[i]=長さiの増加部分列の末尾としてありえる最小値
# というテーブルを持っておいて、数列を列を前から見ながら二分探索で更新箇所を探す
### BUGGY CODE ###

def solve() :
  N,M,Q = raw_input().split()
  N = int(N)
  M = int(M)
  Q = int(Q)
  
  grid = []
  for i in range(N):
    raw = raw_input()
    grid.append(raw)
  qs = []
  for ii in range(Q):
    raw = raw_input()
    qs.append(raw)

  for q in qs:
    qq = q.split()
    #print 'q=',q
    y1 = int(qq[0]) - 1
    x1 = int(qq[1]) - 1
    y2 = int(qq[2]) - 1
    x2 = int(qq[3]) - 1
    w = x2 - x1 + 1
    h = y2 - y1 + 1

    mapp = [[0 for col in range(w)] for row in range(h)]
    eqs = 0
    next = 1
    for y in range(h):
      for x in range(w):
        c = grid[y+y1][x+x1]
        if c == '0': continue
        up = -1 if y == 0 else mapp[y-1][x]
        left = -1 if x == 0 else mapp[y][x-1]
        #print 'y=',y,'x=',x,'up=',up,',left=',left
        if up > 0:
          if left > 0:
            if up == left : mapp[y][x] = up
            else :
              #print 'eq! :up=',up,',left=',left
              eqs += 1
              mapp[y][x] = left
          else :
            mapp[y][x] = up
        else:
          if left > 0:
            mapp[y][x] = left
          else: 
            mapp[y][x] = next
            next += 1
        #print 'up=',up,',left=',left,',mapp[',y,'][',x,']=',mapp[y][x]
    #print 'mapp=',mapp

    sett = set()
    for y in range(h) :
      for x in range(w) :
        #print 'y,x=',y,x
        if(mapp[y][x] > 0):  sett.add(mapp[y][x])
    #print 'sett=',sett,',eqs=',eqs
    print len(sett)-eqs

if __name__ == '__main__' :
  solve()

### FIXED CODE ###

N,M,Q = map(int,input().split())
src = [input() for i in range(N)]
qs = [tuple(map(int,input().split())) for i in range(Q)]

blue_cum = [[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        blue_cum[i+1][j+1] += blue_cum[i+1][j] + int(src[i][j])
for i in range(N):
    for j in range(M+1):
        blue_cum[i+1][j] += blue_cum[i][j]

h_edge = [[0 for j in range(M)] for i in range(N+1)]
for i in range(N):
    for j in range(M-1):
        h_edge[i+1][j+1] += h_edge[i+1][j] + int(src[i][j:j+2]=='11')
for i in range(N):
    for j in range(M):
        h_edge[i+1][j] += h_edge[i][j]

v_edge = [[0 for j in range(M+1)] for i in range(N)]
for i in range(N-1):
    for j in range(M):
        v_edge[i+1][j+1] += v_edge[i+1][j] + int(src[i][j]=='1' and src[i+1][j]=='1')
for i in range(N-1):
    for j in range(M+1):
        v_edge[i+1][j] += v_edge[i][j]

ans = []
for y1,x1,y2,x2 in qs:
    y1 -= 1
    x1 -= 1
    blue = blue_cum[y1][x1] - blue_cum[y1][x2] - blue_cum[y2][x1] + blue_cum[y2][x2]
    edge = h_edge[y1][x1] - h_edge[y1][x2-1] - h_edge[y2][x1] + h_edge[y2][x2-1]
    edge+= v_edge[y1][x1] - v_edge[y1][x2] - v_edge[y2-1][x1] + v_edge[y2-1][x2]
    ans.append(blue - edge)
print(*ans, sep='\n')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

dp = [0 for _ in range(N+1)]

for i in range(N+1):
    for s in S:
        if i - s >= 0:
            dp[i] = max(dp[i], dp[i-s]+1)

digit = dp[N]

def dfs(N, digit, ans):
    if digit == 0:
        if N == 0:
            return ans
        else:
            return 0
    for a in A:
        temp = dfs(N - d[a], digit - 1, ans * 10 + a)
        if temp:
            return temp

print(dfs(N, digit, 0))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
d = [0,2,5,5,4,5,6,3,7,6]
S = set()
for a in A:
    S.add(d[a])

INF = 10 ** 8
dp = [-INF for _ in range(N+1)]
dp[0] = 0

for i in range(N+1):
    for s in S:
        if i - s >= 0:
            dp[i] = max(dp[i], dp[i-s]+1)

ans = 0
digit = dp[N]

for i in range(digit-1, -1, -1):
    if i != 0:
        for a in A:
            if dp[N-d[a]] == i:
                ans = ans * 10 + a
                N -= d[a]
                break
    else:
        for a in A:
            if N == d[a]:
                ans = ans * 10 + a
                break
print(ans)
### BUGGY CODE ###

def main():  
  import sys
  input = sys.stdin.readline
  from collections import deque
  n,m,s,t = map(int,input().split())
  es = deque([])
  der = deque([])
  for _ in range(m):
    u,v,a,b = map(int,input().split())
    es.append((u-1,v-1,a))
    es.append((v-1,u-1,a))
    der.append((u-1,v-1,b))
    der.append((v-1,u-1,b))

  es = tuple(es)
  der = tuple(der)
  def shortest_path(S,g,w,es): 
    d = [10**15] * n #d[i] : s→iの最短距離
    d[S] = 0
    while True:
      update = False
      for p,q,r in es: # e: 辺iについて [from,to,cost]
        if d[p] != 10**15 and d[q] > d[p] + r:
          d[q] = d[p] + r
          update = True       
      if not update:
        break
    return d[g]

  chk = deque([])
  for i in range(n):
    chk.append(10**15-shortest_path(s-1,i,m*2,es)-shortest_path(t-1,i,m*2,der))

  chk = tuple(chk)
  for i in range(n):
    print(max(chk[i:]))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
egg = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  egg[u-1].append([b,v-1])
  egg[v-1].append([b,u-1]) 

es = tuple(es)
egg = tuple(egg)

import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**18] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1,es)
EDGE = dijkstra_heap(t-1,egg)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")
### BUGGY CODE ###

n = input()
p = input().split()

i_cnt = 1
for j in range(len(p)):
  for i in range(j):
    if int(p[i]) < int(p[j]):
      break
    if j-1 == i:
      i_cnt += 1

print(i_cnt)

### FIXED CODE ###

n = input()
p = input().split()

i_cnt = 1
current_max = {'idx': 0, 'value': 0}

for j in range(len(p)):
  for i in range(current_max['idx'], j):
    current_max['idx'] = i
    if current_max['value'] <= int(p[i]): 
      current_max['value'] = int(p[i])
    if int(p[i]) < int(p[j]):
      break
    if j-1 == i:
      i_cnt += 1

print(i_cnt)
### BUGGY CODE ###

def lcm(a,b):
    if a < b:
        a,b = b,a
    while a % b != 0:
        a,b = b,a%b
    return b

K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += lcm(lcm(i,j),k)
print(ans)


### FIXED CODE ###

def lcm(a,b):
    if a < b:
        a,b = b,a
    while a % b != 0:
        a,b = b,a%b
    return b

K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += lcm(lcm(i,j),k)
print(ans)