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


import sys
from itertools import accumulate
mod = pow(10, 9) + 7
N, = [int(i) for i in input().split(' ')]
As = [int(i) % mod for i in input().split(' ')]
sys.setrecursionlimit(pow(10, 8))

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def fractional(N):
    if N == 0:
        return 1
    else:
        return mul(N, fractional(N-1))

T = fractional(N)
fracs = list(accumulate([0] + [div(T, (i+1)) for i in range(N)]))


result = 0
for i in range(N):
    i = i+1
    x = mul(As[i-1], fracs[N-i+1] + (fracs[i] - fracs[1]))
    result = (result + x) % mod 
print(result)


### FIXED CODE ###


import sys
from itertools import accumulate
mod = pow(10, 9) + 7
N, = [int(i) for i in input().split(' ')]
As = [int(i) for i in input().split(' ')]
sys.setrecursionlimit(pow(10, 8))

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod

NNN = 10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def fractional(N):
    if N == 0:
        return 1
    else:
        return mul(N, fractional(N-1))

T = g1[N]
fracs = list(accumulate([0] + [mul(T, inverse[(i+1)]) for i in range(N)]))


result = 0
for i in range(N):
    i = i+1
    x = mul(As[i-1], fracs[N-i+1] + (fracs[i] - fracs[1]))
    result = (result + x) % mod 
print(result)
### BUGGY CODE ###

from collections import Counter
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
k = list(map(int,input().split()))

#print(n)
#print(k)

c = Counter(k)

li = c.most_common()

a_li = [x for x in li if x[1] != 1]

#print(a_li)

max = 0

for i in a_li:
    num = i[1]
    max = max + cmb(num,2)
    
#print(max)

for i in k:
    num = 0
    for a in a_li:
        if a[0] == i:
            num = a[1]
    if num == 0:
        ans = max
    elif num == 2:
        ans = max - 1
    else:
      pre = cmb(num,2)
      cur = cmb(num-1,2)
      ans = max - pre + cur
    print(ans)


### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n = int(input())
k = list(map(int,input().split()))

c = Counter(k)

li = c.most_common()

a_li = [x for x in li if x[1] != 1]

max = 0

for i in a_li:
    num = i[1]
    max = max + cmb(num,2)
    
#print(max)

for i in k:
    num = c[i]
    if num == 1:
        ans = max
    elif num == 2:
        ans = max - 1
    else:
      pre = cmb(num,2)
      cur = cmb(num-1,2)
      ans = max - pre + cur
    print(ans)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def init(n):
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

def nPk(n, k):
    return fact[n] * factinv[n - k] % MOD

def nCk(n, k):
    return fact[n] * factinv[n - k] * factinv[k] % MOD

K = int(input())
N = len(input())

init(N + K)
p25 = [1]
p26 = [1]

for k in range(K):
    p25.append(p25[-1] * 25 % MOD)
    p26.append(p26[-1] * 26 % MOD)

ans = 0
for m in range(K + 1):
    n = N + K
    ans += p25[K - m] * p26[m] * nCk(n - 1 - m, N - 1) % MOD
print(ans % MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def init(n):
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

def nPk(n, k):
    return fact[n] * factinv[n - k] % MOD

def nCk(n, k):
    return fact[n] * factinv[n - k] * factinv[k] % MOD

K = int(input())
N = len(input())

init(N + K)
p25 = [1]
p26 = [1]

for k in range(K):
    p25.append(p25[-1] * 25 % MOD)
    p26.append(p26[-1] * 26 % MOD)

ans = 0
for m in range(K + 1):
    n = N + K
    ans += p25[K - m] * p26[m] * nCk(n - 1 - m, N - 1) % MOD
print(ans % MOD)
### BUGGY CODE ###

N = int(input())
A = tuple(map(int,input().split()))
S = ''

for i in range(N):
    S += str((A.index(i+1))+1) + ' '

print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
O = [0] * N

for i , a  in enumerate(A): #リストAのインデックスiと値a
    O[a-1] = i+1

print(*O)
### BUGGY CODE ###

n,k = map(int, input().split())
min = n + 1

while True:
    if n < min:
        min = n
        n = abs(n - k)
    else:
        break

print(min)


### FIXED CODE ###

n,k = map(int, input().split())
min = n + 1
if n >= k:
    n = n % k
    
while True:
    if n < min:
        min = n
        n = abs(n - k)
    else:
        break

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

#-*-coding:utf-8-*-

def count(s, c):
    cnt = 0
    for i in s:
        if i == c:
            cnt += 1
    return cnt

def main():
    #入力
    N = int(input())
    S = input()

    min_cnt = 300000
    ew = ['E', 'W']

    for i in range(N):
        first_str = S[:i]
        last_str = S[i+1:]

        cnt = 0
        cnt += count(first_str, 'W')
        cnt += count(last_str, 'E')
        if cnt < min_cnt:
            min_cnt = cnt
        #print(first_str, last_str, cnt)
    
    
    print(min_cnt)
            

        


if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

#累積和を求める
def get_cum_sum(s, c):
	cum_sum =[]
	cnt = 0
	
	for i in s:
		if i == c:
			cnt += 1
			cum_sum.append(cnt)
		else:
			cum_sum.append(cnt)
			
	return cum_sum
    
	

def main():
    #入力
    N = int(input())
    S = input()
		
    cum_sum_w = get_cum_sum(S, 'W')
    cum_sum_e = get_cum_sum(S, 'E')
    min_cnt = 300000
    
    for i in range(N):
    	if S[i] == 'W':
    		first_total_w = cum_sum_w[i] - 1
    	else:
    		first_total_w = cum_sum_w[i]
    		
    	last_total_e = cum_sum_e[-1] - cum_sum_e[i]
    	
    	#print(S[:i], S[i+1:], first_total_w, last_total_e)
    	
    	if min_cnt > first_total_w + last_total_e:
    		min_cnt = first_total_w + last_total_e
    
    print(min_cnt)
    	
    	
        


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

from itertools import combinations

N = int(input())
*L, = map(int, input().split())
ans = 0
while len(L) >= 3:
    c = L.pop()
    for a, b in combinations(L, 2):
        if abs(a - b) < c < a + b: ans += 1
print(ans)

### FIXED CODE ###

from itertools import combinations
from bisect import bisect_left

N = int(input())
*L, = map(int, input().split())
L = sorted(L)
ans = 0
for i, j in combinations(range(N), 2): # i < j
    idx = bisect_left(L, L[i] + L[j])
    ans += idx - j - 1
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*N

for i in range(N-1):
    for j in range(K):
        if i < j:
            break
        elif j == 0:
            dp[i+1] = abs(h[i]-h[i+1]) + dp[i]
        else:
            dp[i+1] = min(dp[i+1], abs(h[i-j]-h[i+1]) + dp[i-j])


print(dp[N-1])

### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N
 
  for i in range(1, N):
    dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i - K, 0), i))
 
  return dp[N - 1]
 
print(solve())
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


from functools import lru_cache

@lru_cache(maxsize=None)
def binbin(binn):
    return bin(binn).count("1")


def popcount(n, nc):
    if n == 0:
        return 0
    return 1 + popcount(n % nc, binbin(n % nc))

def main():
    N = int(input())
    X = input().strip()

    x = int(X, 2)
    xc = X.count("1")
    for i in range(N):
        if X[i] == '0':
            print(popcount(x + (2 ** (N - i - 1)), xc + 1))
        else:
            print(popcount(x - (2 ** (N - i - 1)), xc - 1))



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def binbin(binn):
    return bin(binn).count("1")


def popcount(n):
    if n == 0:
        return 0
    return 1 + popcount(n % binbin(n))


def main():
    N = int(input())
    X = input().strip()

    x1 = 0
    xc = binbin(int(X, 2))
    if xc == 1:
        x2 = -1
    else:
        x2 = 0
    for i in range(N):
        if X[-1 - i] == '1':
            x1 += pow(2, i, xc + 1)
            if x2 != -1:
                x2 += pow(2, i, xc - 1)
    for i in range(N):
        if X[i] == '0':
            print(1 + popcount((x1 + pow(2, N - i - 1, xc + 1)) % (xc + 1)))
        else:
            if x2 == -1:
                print(0)
            else:
                print(1 + popcount((x2 - pow(2, N - i - 1, xc - 1) + xc - 1) % (xc - 1)))


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

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        import time
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        t = time.time()
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        assert(time.time() - t <= 0.3)
        done = [0] * n

        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res *= rem * dfs(x, k - 2)
                res %= MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

n = int(input())
l = list()
for i in range(n):
    l.append(i)
print(sum(l))

### FIXED CODE ###

n=int(input())
n-=1
print(n*(n+1)//2)
##############################################################################################################################################################################################################################
### BUGGY CODE ###

import math
def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False


def solve(n):
    ans = 0
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            z1, z2 = 0, 0
            try:
                z1 = -(y + x) + math.sqrt(-3 * x ** 2 -
                                        3 * y ** 2 - 2 * x * y + 4 * n)
                z2 = -(y + x) - math.sqrt(-3 * x ** 2 -
                                        3 * y ** 2 - 2 * x * y + 4 * n)
            except:
                pass

            if z1 >= 1 and is_integer_num(z1):
                ans += 1
                continue
            if z2 >= 1 and is_integer_num(z2):
                ans += 1
                continue

    return ans


def resolve():
    N = int(input())
    for n in range(1, N + 1):
        print(solve(n))

    return

resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    ans = [0 for _ in range(100005)]
    for x in range(1, 105):
        for y in range(1, 105):
            for z in range(1, 105):
                tmp = x * x + y * y + z * z + x * y + y * z + z * x
                if tmp < 10005:
                    ans[tmp] += 1
    
    for i in range(1, N+1):
        print(ans[i])
    return
 
resolve()
### BUGGY CODE ###

try:
    K, S = map(int, input().split())
    cnt = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if x+y+z==S:
                    cnt += 1
                    break
    print(cnt)
except EOFError:
    pass

### FIXED CODE ###

try:
    K, S = map(int, input().split())
    cnt = 0
    for x in range(K+1):
        for y in range(K+1):
            z = S-x-y
            if 0<=z<=K:
                cnt += 1
    print(cnt)
except EOFError:
    pass
### BUGGY CODE ###

n =int(input())
A=[]
for I in range(n):
  moji=input()
  A.append(moji)
N=0
for i in range(n):
  a=list(A[i])
  a.sort()
  #print(a)
  for s in range(i+1,n,1):
    b=list(A[s])
    b.sort()
    #print(b)
    if a==b:
      N+=1
print(N)

### FIXED CODE ###

n =int(input())
A=[]
for I in range(n):
  moji=list(input())
  moji.sort()
  moji=''.join(moji)
  A.append(moji)
A.sort()
N=0
SUM=0
i=0
while True:
  if i==n-1:
    SUM=SUM+int(0.5*N*(N+1))
    break
  a=A[i]
  for s in range(i+1,n,1):
    b=A[s]
    if a==b:
      N+=1
      i+=1
    else:
      SUM=SUM+int(0.5*N*(N+1))
      N=0
      i=s
      break
print(SUM)
### BUGGY CODE ###


N, Q = list(map(int, input().split()))
eda = [[] for i in range(N)]
ope = [0]*N
score = [0]*N
parent = [-1]*N


for i in range(N - 1):
	a, b = list(map(int, input().split()))
	eda[a - 1].append(b - 1)
	eda[b - 1].append(a - 1)

for i in range(Q):
	p, x = list(map(int, input().split()))
	ope[p - 1] += x


que = []
que.append(0)
score[0] = ope[0]
for ss in range(N - 1):
	loc = que.pop()
	for edge in eda[loc]:
		if parent[loc] != edge:
			score[edge] += score[loc] + ope[edge]
			que.append(edge)
			parent[edge] = loc

for i in range(N - 1):
	print(score[i], end = "")
	print(" ", end = "")
print(score[N - 1])






### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


N, Q = list(map(int, input().split()))
eda = [[] for i in range(N)]
ope = [0]*N
score = [0]*N
parent = [-1]*N


for i in range(N - 1):
	a, b = list(map(int, input().split()))
	eda[a - 1].append(b - 1)
	eda[b - 1].append(a - 1)

for i in range(Q):
	p, x = list(map(int, input().split()))
	ope[p - 1] += x


que = []
que.append(0)
score[0] = ope[0]
for ss in range(N - 1):
	loc = que.pop()
	for edge in eda[loc]:
		if parent[loc] != edge:
			score[edge] += score[loc] + ope[edge]
			que.append(edge)
			parent[edge] = loc

for i in range(N - 1):
	print(score[i], end = "")
	print(" ", end = "")
print(score[N - 1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q=map(int,input().split())
graph=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

ans=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x

used=[False]*N
def solve(x):
    used[x]=True
    for y in graph[x]:
        if used[y]:
            continue
        ans[y]+=ans[x]
        solve(y)

for i in range(N):
    solve(i)

print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q,*abpx=map(int,sys.stdin.read().split())

graph=[[] for _ in range(N)]
for a,b in zip(*[iter(abpx[:2*(N-1)])]*2):
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

f=[0]*N
for p,x in zip(*[iter(abpx[2*(N-1):])]*2):
    p-=1
    f[p]+=x

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)
### BUGGY CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(min(50,k)):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
print(*a)


### FIXED CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(k):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
    if all([i==n for i in a]):
        break
print(*a)
### BUGGY CODE ###

import math

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

N = int(input())
s = 0
for i in range(1, N):
  com = len(divisor(i))
  s += com
print(s)

### FIXED CODE ###

N = int(input())
s = 0
for i in range(1, N):
  b = (N - 1) // i
  s += b
print(s)
### BUGGY CODE ###

n, m = map(int, input().split())
aa = list(map(int, input().split()))
import numpy as np

for i in range(m):
    ag = np.argmax(aa)
    aa[ag] = aa[ag] // 2
print(sum(aa))

### FIXED CODE ###

n, m = map(int, input().split())
aa = list(map(int, input().split()))

from queue import PriorityQueue

q = PriorityQueue()
for a in aa:
    q.put(-a)
for i in range(m):
    g = q.get()
    q.put(-(-g // 2))
cost = 0
for a in aa:
    cost -=q.get()
print(cost)
### BUGGY CODE ###

N,M=map(int,input().split())
P=[[] for i in range(N+1)]
Y=[0 for i in range(M)]
id=[0 for i in range(M)]
for i in range(M):
    a,b=map(int,input().split())
    P[a].append(b)
    Y[i]=b
for i in range(N+1):
    P[i].sort()
for i in range(1,N+1):
    j=1
    for p in P[i]:
        id[Y.index(p)]=str(i*1000000+j)
        j+=1
for i in range(M):
    print(id[i].zfill(12))


### FIXED CODE ###

N,M=map(int,input().split())
P=[[] for i in range(M)]
Y=[1 for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    P[i].append(i)
    P[i].append(a)
    P[i].append(b)
P.sort(key=lambda x:x[2])
for i in range(M):
    P[i].append(str(P[i][1]*1000000+Y[P[i][1]]))
    Y[P[i][1]]+=1
P.sort(key=lambda x:x[0])
for i in range(M):
    print(P[i][3].zfill(12))
### BUGGY CODE ###

n,k = map(lambda x: int(x),input().split())
p = list(map(lambda x: int(x),input().split()))
max = 0

for i in range(n-k+1):
    ans = sum(list(map(lambda x: (1+x)/2,p[i:i+k])))
    if max < ans :
        max = ans

print(max)


### FIXED CODE ###

n,k = map(lambda x: int(x),input().split())
p = list(map(lambda x: (int(x) + 1)/2,input().split()))
ruiseki = [0]
max = 0
for i in range(n) :
    ruiseki.append(ruiseki[i]+p[i])

for j in range(n - k + 1):
    if max < (ruiseki[j+k] - ruiseki[j]) :
        max = (ruiseki[j+k] - ruiseki[j])


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

x , y ,z , k = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

e = [i + j for i in a for j in b]
e.sort(reverse=True)
e = e[:k]
ans = [i + j for i in e for j in c]
ans.sort(reverse=True)
ans = ans[:k]

for i in range(k):
    print(ans[i])


### FIXED CODE ###

x , y ,z , k = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

e = [i + j for i in a[:k] for j in b[:k]]
e.sort(reverse=True)
e = e[:k]
ans = [i + j for i in e for j in c[:k]]
ans.sort(reverse=True)

for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N = map(int, input().split())
A = list(map(int, input().split()))
ans = A[0]
if 0 in A:
    ans = 0
else:
    for a in A[1:]:
        ans *= a
    if ans > 10**18:
        ans = -1
print(ans)

### FIXED CODE ###

N = map(int, input().split())
A = list(reversed(sorted(list(map(int, input().split())))))
if A[-1] == 0:
    ans = 0
else:
    ans = A[0]
    for a in A[1:]:
        ans *= a
        if ans > 10**18:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

import heapq

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    for year in range(n):
        cost = min(total[year:])
        print(money - cost)

### FIXED CODE ###

import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])
### BUGGY CODE ###

N = int(input())

i = N
while True:
    if i % 2 == 0 and i % N == 0:
        print(i)
        break
    i += 1


### FIXED CODE ###

N = int(input())

i = N
while True:
    if i % 2 == 0 and i % N == 0:
        print(i)
        break
    i += N