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

import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
for i in k:
  dp = [[0]*4 for _ in range(n)]
  dp[-1][0] = 1
  for j in range(n):
    dp[j] = dp[j-1]
    kon = x[j]
    if kon:
      dp[j][kon] += dp[j-1][kon-1]
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[j][1] -= 1
        dp[j][2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp[n-1][3])

### FIXED CODE ###

import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
dp = [0,0,0,0]
dp1 = [0,0,0,0]
for i in k:
  dp = [1,0,0,0]
  for j in range(n):
    dp1 = dp
    kon = x[j]
    if kon:
      dp1[kon] += dp[kon-1]
    dp = dp1
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[1] -= 1
        dp[2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp1[3])
### BUGGY CODE ###

has_duplicates= lambda seq:len(seq) == len(set(seq))
def main():
    n=int(input())
    l=list(map(int,input().split()))
    tel=[-1,-1,-1]
    temp=0
    bn=0
    tc=0
    pc=0
    i=0
    while len(bin(i))-3<n:
        if str(bin(i)).count('1')==3:
            bn=bin(i)
            tc=0
            tel=[-1,-1,-1]
            for j in range(len(str(bn)[2:])):
                if (i>>j)&1:
                    tel[tc]=l[n-j-1]
                    tc+=1
            if has_duplicates(tel):
                tel.sort()
                if abs(tel[1]-tel[2])<tel[0] and tel[0] < tel[1]+tel[2]:
                    pc+=1
        i+=1
    print(pc)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n=int(input())
    l=list(map(int,input().split()))
    ans=0
    for i in range(n):
        for k in range(i+1,n):
            for j in range(k+1,n):
                temp=[l[i],l[k],l[j]]
                if len(set(temp))==len(temp):
                    temp.sort()
                    if temp[0]+temp[1]>temp[2]:
                        ans+=1
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import math

N = int(raw_input())
S = [raw_input() for _ in range(N)]
D = {}
for s in S:
    k = "".join(sorted(s))
    if k not in D:
        D[k] = []
    D[k].append(s)

ans = 0
for k,v in D.items():
    n = len(v)
    if n > 1:
        ans += math.factorial(n) / (2 * math.factorial(n-2))
print ans

### FIXED CODE ###

import math

N = int(raw_input())
S = [raw_input() for _ in range(N)]
D = {}
for s in S:
    k = "".join(sorted(s))
    if k not in D:
        D[k] = []
    D[k].append(s)

ans = 0
for k,v in D.items():
    n = len(v)
    if n > 1:
        ans += math.factorial(n) / (2 * math.factorial(n-2))
print ans
### BUGGY CODE ###

import collections
def resolve_c():
    n = input()
    s_l = [input() for i in range(int(n))]
    c = collections.Counter(s_l)
    results = [k for k, v in c.items() if v == c.most_common()[0][1]]
    results = sorted(results)
    for r in results:
        print(r)
resolve_c()

### FIXED CODE ###

import collections
def resolve_c():
    n = input()
    s_l = [input() for i in range(int(n))]
    c = collections.Counter(s_l)
    values, counts = zip(*c.most_common())
    results = sorted(list(values[:collections.Counter(counts)[max(counts)]]))
    fin = [print(r) for r in results]
resolve_c()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

import re

for _ in range(Q):
  l, r = map(int, input().split())
  r = re.findall('AC', S[l-1:r])
  print(len(r))
  
  

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
tmp = [0] * (N+1)

for i in range(N):
  w = 1 if S[i:i+2] == 'AC' else 0
  tmp[i+1] = tmp[i] + w
  
for _ in range(Q):
  l, r = map(int, input().split())
  print(tmp[r-1] - tmp[l-1])
### BUGGY CODE ###

#
from collections import deque

import sys

def main():
    n, m = map(int, input().split())

    edges = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        edges[u].append(v)
    # print(edges)

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

    def next_kenp(node):
        nodes = set()
        nodes2 = set()

        for n1 in edges[node]:
            for n2 in edges[n1]:
                if n2 not in nodes2:
                    nodes2.add(n2)

        for nn in nodes2:
            for n3 in edges[nn]:
                if n3 in dones or n3 in nodes:
                    continue
                nodes.add(n3)
        return nodes

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            que.append((n, step + 1))
            dones.add(n)

    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

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

    # print(new_edges)

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


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

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

B = A[1:N]   # A1を除外

C = []

Num = 0
Dum = 0
Gum = 0

for i in range(N-1):
    Num = i
    for j in range(Num+1):
        Dum += A[j]
    C.append(Dum)
    Dum = 0

for k in range(N-1):
    Gum += B[k] * C[k]

print(Gum % 1000000007)

### FIXED CODE ###

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

Dum = 0
Gum = 0

for i in range(0, N-1):
    Dum += A[i]
    Gum += Dum * A[i+1]

print(Gum % 1000000007)
### BUGGY CODE ###

N = int(input())

ans = 0

def c(x, y):
    cnt = 0
    for i in range(1, N+1):
        if int(str(i)[0]) == x and int(str(i)[-1]) == y:
            cnt += 1
    return cnt

for i in range(10):
    for j in range(10):
        ans += c(i, j) * c(j, i)

print(ans)


### FIXED CODE ###

N = int(input())

cnt = 0
for i in range(1, N+1):
    first = str(i)[0]
    last = str(i)[-1]
    if first == last:
        cnt += 1
    if last != '0':
        if len(str(N)) == 2:
            if int(last+first) <= N:
                cnt += 1
        if len(str(N)) >= 3:
            for j in range(len(str(N))-2):
                cnt += 10**j
            middle = str(N)[1:-1]
            if last < str(N)[0]:
                cnt += 10**(len(str(N))-2)
            elif last == str(N)[0]:
                if first > str(N)[-1]:
                    cnt += int(middle)
                else:
                    cnt += int(middle) + 1

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

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

evaluations = []
for n in range(N):
    if n < K-1:
        evaluations.append(0)
    else:
        evaluation = 1
        for i in range(K):
            evaluation *= A[n-i]
        evaluations.append(evaluation)
# print(evaluations)

for n in range(K, N):
    print('Yes' if evaluations[n] > evaluations[n-1] else 'No')


### FIXED CODE ###

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

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

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in lists:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1
        lists.append(input_data)

print(count)

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
while True:
    if (N - K) < 0:
        if N > K - N:
            N = K - N
        else:
            break
    elif (N - K) > 0:
        N = N - K
    elif N - K == 0:
        N = 0
print(N)

### FIXED CODE ###

N,K = map(int,input().split())
S = N // K
Answer = abs(N - K*S)
if abs(Answer - K) <= Answer:
    Answer = abs(Answer - K)
print(Answer)
### BUGGY CODE ###

import numpy as np

def sum(n):
	s = 0
	y = 1
	while y <= n:
		s += y
		y += 1
	return s

N, K = map(int, input().split())
x = np.array(list(map(int, input().split())))

m = 0

for i in range(N-K+1):
	ans = 0
	for j in range(i, i+K):
		ans += sum(x[j]) / x[j]

	if ans > m:
		m = ans

print(m)

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
x = np.array(list(map(float, input().split())))

for i in range(N):
	x[i] = (1 + x[i]) / 2

data = np.sum(x[:K])
ans = data

for i in range(N-K):
	data = data + x[i+K] - x[i]
	if data > ans:
		ans = data

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

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

x=[]
a=1
if L<=2019<=R:
    a=0
else:
    for i in range(L,R):
        for j in range(L+1,R+1):
            y=((i*j)%2019)
            x.append(y)

if a==0:
    print(a)
else:
    print(min(x))


### FIXED CODE ###

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

x=[]
a=0
for i in range(L,R):
    for j in range(L+1,R+1):
        y=((i*j)%2019)
        x.append(y)
        if y==0:
            break
    if y==0:
            break

print(min(x))
### BUGGY CODE ###

S = input()

MOD=(10**9) + 7
N=13

dp=[[0 for i in range(N)] for j in range(100005)]
dp[0][0] = 1

dpi = 1
mul = 1
for c in S[::-1]:    
    for i in range(N):
        if c=='?':
            for j in range(10):
                ii = (i + (int(j)*mul)) % N
                dp[dpi][ii] += dp[dpi-1][i] % MOD
        else:
            ii = (i + (int(c)*mul)) % N
            dp[dpi][ii] += dp[dpi-1][i] % MOD
    mul *= 10
    dpi += 1

print(dp[dpi-1][5] % MOD)

### FIXED CODE ###

S = input()

MOD=(10**9) + 7
N=13

dp=[[0 for i in range(N)] for j in range(100005)]
dp[0][0] = 1

dpi = 1
mul = 1

for c in S[::-1]:    
    for i in range(N):
        if c=='?':
            for j in range(10):
                ii = (i + (j*mul)) % N
                dp[dpi][ii] += dp[dpi-1][i] % MOD
                #pass
        else:
            j = int(c)
            ii = (i + (j*mul)) % N
            dp[dpi][ii] += dp[dpi-1][i] % MOD
            #pass
    mul *= 10
    mul %= N
    dpi += 1

print(dp[dpi-1][5] % MOD)
### BUGGY CODE ###

def m(list1): 
      
    mul=1
    for x in list1: 
         mul=mul*x  
    return mul 
      
n=int(input())
arr=list(map(int,input().split()))
if m(arr)>pow(10,18):
    print(-1)
else:
    print(m(arr)) 
 


### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
ans=int(1)
temp=int(0)
for i in range(n):
  if(ans>(10**18)):
    ans=-1
  if(ans!=-1):
  	ans*=arr[i]
  if(arr[i]==0):
    temp=int(1)
if(ans>(10**18)):
  ans=-1
if(temp==1):
  ans=0
print(int(ans))
### BUGGY CODE ###

#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools as fts
import itertools as its
import math
import sys

INF = float('inf')


def solve(N: int, A: "List[int]"):
    return sum(max(A[:i+1]) for i in range(N)) - sum(A)


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(f'{solve(N, A)}')


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools as fts
import itertools as its
import math
import sys

INF = float('inf')


def solve(N: int, A: "List[int]"):
    ans = 0
    m = A[0]
    for a in A[1:]:
        ans += max(0, m - a)
        m = max(m, a)
    return ans


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(f'{solve(N, A)}')


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

n = int(input())
arr = list(map(int, input().split()))
cnt = len(arr)

for i in range(len(arr)):
  for j in range(len(arr)):
    if arr[i] % arr[j] == 0 and i != j:
      cnt -= 1
      break

print(cnt)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

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

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)
dp = [[0] * (suma+1) for i in range(N)]
dp2 = [[0] * (suma+1) for i in range(N)]
dp[0][0] = 2
dp[0][a[0]] = 1
dp2[0][0] = 1
dp2[0][a[0]] = 1 
allc = 3
flag = 0
if(suma%2 == 0):
	flag = 1
for i in range(1,N):
	allc = allc*3
	k = a[i]
	for j in range(sum(a[:i+1])+1):
		if(j < k):
			dp[i][j] = dp[i-1][j]*2
			if(flag == 1):
				dp2[i][j] = dp2[i-1][j]
		else:
			dp[i][j] = dp[i-1][j]*2+dp[i-1][j-k]
			if(flag == 1):
				dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-k]
allc = allc - sum(dp[N-1][suma-suma/2:])*3
if(flag == 1):			
	allc += dp2[N-1][suma/2]*3
print(allc%DIV)

### FIXED CODE ###

import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2),dtype = np.int)
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],1] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,:-k,1]
	dp[i,:,1] += dp[i-1,:,1]
	if(i%10 == 0):
		dp[i,:,:] = dp[i,:,:]%DIV
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(suma % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))
### BUGGY CODE ###

import math
A,B=map(int,input().split())
def is_prime(n):
  if n==1:return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n%k==0:
      return False
  return True

def cf(a,b):
  cf=[]
  for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
      if is_prime(i):
        cf.append(i)
  return cf
print(len(cf(A,B))+1)

### FIXED CODE ###

from fractions import gcd
A,B=map(int,input().split())
s=set()
x=gcd(A,B)
y=2
while y*y<=x:
  while x%y==0:
    s.add(y)
    x//=y
  y+=1
if x>1:
  s.add(x)
print(len(s)+1)
### BUGGY CODE ###

A,B,K = map(int,input().split())
for _ in range(K):
    if A > 0:
        A -= 1
    elif A == 0 and B > 0:
        B -= 1
print(A,B)


### FIXED CODE ###

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

if A >= K :
    print(A-K,B)
elif A < K <= A + B:
    print(0,B-(K-A))
else:
    print(0,0)
### BUGGY CODE ###

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    a2=set(a)
    a2=list(sorted(a2))
    if a2[0]==1:
        if a.count(1)==1:
            ans=1
        else:
            ans=0
    else:
        def c1(num1):
            return a.count(num1)
        for i in range(len(a2)):
            num=0
            if c1(a2[i])==1:
                for j in range(i):
                    if a2[i]%a2[j]==0:
                        num=1
                        break
                    if a2[i]/2+1<a2[j]:
                        break
                if num==0:
                    ans+=1
    print(ans)

solve()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
a.sort()
num=a[-1]
dp=[True]*num
seen=[0]*num
for i in range(n):
    num2=a[i]
    if dp[num2-1]==True:
        if seen[num2-1]==1:
            dp[num2-1]=False
        for j in range(2,num//num2+1):
            dp[j*num2-1]=False
    seen[a[i]-1]=1
ans=0
for i in range(n):
    if dp[a[i]-1]==True:
        ans+=1
print(ans)
### BUGGY CODE ###

n = int(raw_input())
l = [map(int, raw_input().split()) for _ in range(n-1)]
m = []
for i in range(n-1):
    m.append(l[i][1]+l[i][0])
    for j in range(i):
        if m[j] <= l[i][1]:
            m[j] = m[i]
        else:
            k = l[i][1] + l[i][2]
            while m[j] > k:
                k += l[i][2]
            m[j] = k +  l[i][0]
m.append(0)
for i in m:
    print i


### FIXED CODE ###

n = int(raw_input())
l = [map(int, raw_input().split()) for _ in range(n-1)]
m = []
for i in range(n-1):
    m.append(l[i][1]+l[i][0])
    for j in range(i):
        if m[j] <= l[i][1]:
            m[j] = m[i]
        else:
            k = (m[j] + l[i][2] - 1) / l[i][2] * l[i][2]
            m[j] = k +  l[i][0]
m.append(0)
for i in m:
    print i
### BUGGY CODE ###

class SegmentTree:
    def __init__(self, N, id, fun):#id:単位元
        self.N0 = 2**(N-1).bit_length()
        self.id = id
        self.data = [self.id]*(2*self.N0)
        self.fun = fun
 
    def update(self, l, r, val):#[l, r)をvalで更新
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1 :
                self.data[l] = self.fun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r-1] = self.fun(self.data[r-1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += self.N0
        ret = self.data[i]
        while i > 0 :
            i //= 2
            ret = self.fun(ret, self.data[i])
        return ret
N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
S = SegmentTree(N, 0, lambda x, y:x+y)
ans = 0
from bisect import bisect
for i in range(N):
    x, h = XH[i]
    c = S.query(i)
    h-=c
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect(XH, [x+D*2+1, -1])
    S.update(i, j, n*A)
    ans+=n
print(ans)
    





### FIXED CODE ###


N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]
XH.sort()
X = [XH[i][0] for i in range(N)]
ans = 0
res = 0
from bisect import bisect_left
cnt = [0]*(N+1)
for i in range(N):
    x, h = XH[i]
    res-=cnt[i]
    h-=res
    if h<=0:
        continue
    n = ((h-1)//A+1)
    j = bisect_left(X, x+D*2+1)
    cnt[j]+=n*A
    res += n*A
    ans+=n
print(ans)
### BUGGY CODE ###

import heapq
INF = 10 ** 17
def dijkstra(s):
    #始点sから各頂点への最短距離
    d = [INF] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_a[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 graph_a[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dijkstra1(s):
    #始点sから各頂点への最短距離
    d = [INF] * (n+1)
    used = [True] * (n+1) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in graph_b[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 graph_b[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n, m, s, t = map(int, input().split())
# graph作成
graph_a = {i: [] for i in range(1, n + 1)}
graph_b = {i: [] for i in range(1, n + 1)}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    graph_a[u].append([a, v])
    graph_a[v].append([a, u])
    graph_b[u].append([b, v])
    graph_b[v].append([b, u])

yen = dijkstra(s)
snu = dijkstra1(t)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i + 1] + snu[i + 1],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)


### FIXED CODE ###

import heapq
INF = 10**18
def dijkstra(s, edge, n):
    d = [INF] * n
    used = [True] * n #True: not used
    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
 
n, m, s, t = map(int, input().split())
s -= 1
t -= 1
graph_a = [[] for _ in range(n)]
graph_b = [[] for _ in range(n)]
for i in range(m):
    u, v, a, b = map(int, input().split())
    u, v = u-1, v-1
    graph_a[u].append((a, v))
    graph_a[v].append((a, u))
    graph_b[u].append((b, v))
    graph_b[v].append((b, u))
 
yen = dijkstra(s, graph_a, n)
snu = dijkstra(t, graph_b, n)

cost = [0] * n
for i in range(n):
    cost[i] = (yen[i] + snu[i],i)

heapq.heapify(cost)
c = -1
aaa = 10 ** 15
for i in range(n):
    if c < i:
        while cost:
            nn, t = heapq.heappop(cost)
            if t >= i:
                c = t
                break
    print(aaa - nn)
### BUGGY CODE ###

import math
import sys

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())

ans = 0

for k in range(1, N+1):

    if k == 1:
        ans += 1
    else:
        ans += k * len(make_divisors(k))

print(ans)


### FIXED CODE ###

N = int(input())

def calc(start, end):
	n = end // start
	return (n * (n+1) // 2) * start

ans = 0
for i in range(1, N+1):
	ans += calc(i, N//i * i)

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

import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')

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

a = [0]

for i in range(1, n):
	a.append(pow(10, 10))
	for j in range(1, k+1):
		if i-j >= 0:
			b = a[i-j] + abs(h[i-j]-h[i])
			if b < a[i]:
				a[i] = b

print(a[n-1])

### FIXED CODE ###

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

INF = int(pow(10, 10))

a = [INF] * n
a[0] = 0

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

print(a[n-1])