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

a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+2)*[0]for _ in range(c+2)]
dp[a][b]=1
for i in range(a,c+1):
    for j in range(b,d+1):
        dp[i][j]%=mod
        dp[i+1][j]+=dp[i][j]*j
        dp[i][j+1]+=dp[i][j]*i
        dp[i+1][j+1]-=dp[i][j]*i*j
print(dp[c][d])


### FIXED CODE ###

a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+1)*[0]for _ in range(c+1)]
for i in range(a,c+1):
  for j in range(b,d+1):
    if i==a and j==b:
      dp[i][j]=1
      continue
    if i==a:
      dp[i][j]=dp[i][j-1]*i%mod
      continue
    if j==b:
      dp[i][j]=dp[i-1][j]*j%mod
      continue
    dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1))%mod
print(dp[c][d])
### BUGGY CODE ###

import sys
import math
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))

def solve():

    return

def main():
    n, k = getList()
    cap = getList()
    foods = getList()
    cap.sort()
    foods.sort(reverse=True)
    h = []
    pairs = [(-a*b, a, b) for a, b in zip(cap, foods)]
    for pair in pairs:
        heapq.heappush(h, pair)
    for _ in range(k):
        tmp = heapq.heappop(h)
        if tmp[0] != 0:
            _,na,nb = tmp
            na -= 1
            heapq.heappush(h, (-na*nb, na, nb))

    ans = heapq.heappop(h)
    print(-ans[0])

if __name__ =="__main__":
    main()

### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(100000)
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))

def check(mid, k, pairs):
    tmp = 0
    for pair in pairs:
        a,b = pair
        kari_a = mid // b
        tmp += max(a - kari_a, 0)

    if tmp <= k:
        return True
    else:
        return False


def solve():
    n, k = getList()
    cap = getList()
    foods = getList()
    cap.sort()
    foods.sort(reverse=True)
    h = []
    pairs = [(a, b) for a, b in zip(cap, foods)]
    ansmn = 0
    ansmx = 10**13
    # print(foods)
    # print(cap)
    # print([2046//p for p in foods])
    while(ansmx - ansmn > 1):
        mid = (ansmn + ansmx) // 2
        res = check(mid, k, pairs)
        if res:
            ansmx = mid
        else:
            ansmn = mid


    if check(ansmn, k, pairs):
        print(ansmn)
    else:
        print(ansmx)

def main():
    solve()


if __name__ == "__main__":
    main()


"""
10 10
95 38 9 26 36 10 69 25 44 83
6 42 33 74 75 31 73 20 70 93
"""
### BUGGY CODE ###


def main():
    N, K = map(int, input().split(' '))
    
    # out = min(float('inf'), N)
    prev = N
    
    isFinish = False
    
    if N % K == 0:
        print(0)
        return
    
    while not isFinish:
        next = abs(prev - K)
        
        if next > prev:
            isFinish = True
        else:
            prev = next
            
    print(prev)
        
        
    
    
    
    
main()

### FIXED CODE ###


def main():
    N, K = map(int, input().split(' '))
    
    # out = min(float('inf'), N)
    prev = N % K
    
    isFinish = False
    
    if prev == 0:
        print(0)
        return
    
    while not isFinish:
        next = abs(prev - K)
        
        if next >= prev:
            isFinish = True
        else:
            prev = next
            
    print(prev)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i)
NUMIND=[0]*(N+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM[1:]:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

print(*ANS)

### FIXED CODE ###

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")
### BUGGY CODE ###

import sys
# A,B,C = [int(n) for n in input().split()]
N,K = [int(n) for n in input().split()]
# S = str(input())
# T = str(input())
bucket = [0]*(N+1)
A = [int(n) for n in input().split()]
dic = {}
for a in A:
    if not(a in dic):
        dic[a]=1
    else:
        dic[a]+=1
val = sorted(dic.values())
# print(val)
rc = len(val) - K
ans = 0
for r in range(rc):
    ans += val[0]
    val = val[1:]
print(ans if ans >=0 else 0)


### FIXED CODE ###

import sys
# A,B,C = [int(n) for n in input().split()]
N,K = [int(n) for n in input().split()]
# S = str(input())
# T = str(input())
bucket = [0]*(N+1)
A = [int(n) for n in input().split()]
dic = {}
for a in A:
    if not(a in dic):
        dic[a]=1
    else:
        dic[a]+=1
val = sorted(dic.values())
# print(val)
rc = len(val) - K
ans = 0
for r in range(rc):
    ans += val[r]
print(ans if ans >=0 else 0)
### BUGGY CODE ###

Q = int(input())

a = [[int(i) for i in input().split()] for j in range(Q)]

for i in range(Q):
    m = a[i][0]
    for j in range(a[i][2]-1):
        m *= (a[i][0]+(j+1)*a[i][1])%1000003
    print(m%1000003)

### FIXED CODE ###

MOD = 10**6+3

def main():
    # preprocess
    fac = [1, 1]
    f_inv = [1, 1]
    inv = [0, 1]

    for i in range(2, MOD+1):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        f_inv.append((f_inv[-1] * inv[-1]) % MOD)

    Q = int(input())
    for i in range(Q):
        x, d, n = map(int, input().split())

        if d == 0:
            print(pow(x, n, MOD))
            continue
        
        xd = (x * pow(d, MOD-2, MOD)) % MOD
        if xd == 0 or xd + (n-1) >= MOD:
            print(0)
            continue

        print(pow(d, n, MOD) * fac[xd+(n-1)] * f_inv[xd-1] % MOD)


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

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

s = 10**9
for i in range(n-k+1) :
  f = x[i:i+k] 
  m = min(abs(f[0]) +abs(f[-1] - f[0]) , abs(f[-1]) + abs(f[-1] - f[0]))
  if s >m :
    s = m
print(s)

### FIXED CODE ###

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

s = 10**9
for i in range(n-k+1) :
  f1 = x[i]
  f2 = x[i+k-1]
  m = min(abs(f1) +abs(f2 - f1) , abs(f2) + abs(f2 - f1))
  if s >m :
    s = m
print(s)
### BUGGY CODE ###

n = int(input())
aList = list(map(int, input().split()))
ansList = []
for a in range(1, n + 1):
    ansList.append(aList.index(a) + 1)
print(' '.join(map(str, ansList)))

### FIXED CODE ###

n = int(input())
aList = list(map(int, input().split()))
l = []
for i, a in enumerate(aList):
    l.append((a, i))
l = sorted(l, key=lambda x:x[0])
ansList = [a[1] + 1 for a in l]
print(' '.join(map(str, ansList)))
### BUGGY CODE ###

import sys
l = sys.stdin.readline().strip()
N, M = map(int, l.split())
link = []
for i in range(N+1):
    link.append([-1] * (N+1))

l = sys.stdin.readline().strip()
heights = [-1] + list(map(int, l.split()))

for i in range(M):
    l = sys.stdin.readline().strip()
    A, B = map(int, l.split())
    if A!= B:
        link[A][B] = 1
        link[B][A] = 1

count = 0
impossible = set()
for i in range(1, N+1):
    if i in impossible:
        continue
    hs = []
    his = []
    for j in range(1, N+1):
        if link[i][j] == 1:
            hs.append(heights[j])
            his.append(j)
    if hs ==[]:
        count += 1
        continue

    if heights[i] > max(hs):
        count += 1
        for one in his:
            impossible.add(one)
print(count)



### FIXED CODE ###

import sys
l = sys.stdin.readline().strip()
N, M = map(int, l.split())
impossible = set()

l = sys.stdin.readline().strip()
heights = [-1] + list(map(int, l.split()))

for i in range(M):
    l = sys.stdin.readline().strip()
    A, B = map(int, l.split())
    if A==B:
        continue
    if heights[A] == heights[B]:
        impossible.add(A)
        impossible.add(B)
    elif heights[A] < heights[B]:
        impossible.add(A)
    else:
        impossible.add(B)

print (N - len(impossible))
### BUGGY CODE ###

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(Ai, dictionary):
    num = 0
    for k,v in dictionary.items():
        if k == Ai:
            N_Ai = v -1 #1こ抜いた数. 
        else:
            N_Ai = v
        num += N_Ai*(N_Ai-1)/2
    return int(num)

for n in A_array:
    print(calc_comb(n, Ai_dict))


### FIXED CODE ###

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(dct):
    num = 0
    for k,v in dct.items():
        num += v*(v-1)/2
    return int(num)


res_dict = dict([])
TotalComb = calc_comb(Ai_dict)

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = TotalComb - Ai_dict[n]+1
    print(res_dict[n])
### BUGGY CODE ###

# input
n, m = map(int, input().split())
nums = [int(i) for i in input().split()]
data = []
for i in range(m):
  data.append([int(i) for i in input().split()])

# main  
nums.sort()
for i in range(m):
  for j in range(data[i][0]):
    if nums[j] < data[i][1]:
      nums[j] = data[i][1]
    else:
      break
  nums.sort()

# output  
print(sum(nums))

### FIXED CODE ###

# input
n, m = map(int, input().split())
data = [[int(i), 1] for i in input().split()]
for i in range(m):
  b, c = map(int, input().split())
  data.append([c, b])
data.sort(key=lambda x:x[0], reverse=True)

# main
ans = 0
cnt = n
for i in range(len(data)):
  if cnt >= data[i][1]:
    ans += data[i][0] * data[i][1]
    cnt -= data[i][1]
  else:
    ans += data[i][0] * cnt
    cnt -= data[i][1]
  if cnt <= 0:
    break
    
# output
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
A.sort()
C.sort()
for i in range(len(B)):
	a_cand = 0
	c_cand = 0
	for j in range(len(A)):
		if A[j] < B[i]:
			a_cand += 1
		if B[i] < C[j]:
			c_cand += 1
	ans += a_cand * c_cand
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
A.sort()
C.sort()
for b in B:
	a_cand = bisect_left(A, b)
	c_cand = N - bisect_right(C, b)
	ans += a_cand * c_cand
print(ans)
### BUGGY CODE ###

a, b = map(int, input().split())

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

ans = 0
for i in range(1, min(a, b)+1):
  if a % i == 0 and b % i == 0:
    if prime(i): ans += 1
print(ans)

### FIXED CODE ###

from fractions import gcd
A, B = map(int, input().split())
g = gcd(A, B)

from collections import Counter
#最大公約数を素因数分解する
def factorize(n):
  d = Counter()
  m = 2
  while m*m <= n:
    while n%m == 0:
      n //= m
      d[m] += 1
    m += 1
  if n > 1:
    d[n] += 1
  return d

fs = factorize(g) # "1"以外の公約数
print(len(fs) + 1) # 公約数"1"を足す
### BUGGY CODE ###

#input
S = input()
Q = int(input())
P = []
for i in range(Q):
    P.append(list(map(str, input().split())))

#output
for i in range(Q):
    if len(P[i]) == 1:
        S = S[-1::-1]
    else:
        v = P[i][2]
        if int(P[i][1]) == 1:
            S = v + S
        else:
            S = S + v
                        
print(S)

### FIXED CODE ###

#input
S = input()
Q = int(input())
P = [[]] * Q
for i in range(Q):
    P[i] = list(map(str, input().split()))

#output
flip = 0
cap = ""
tail = ""

for i in range(Q):
    if int(P[i][0]) == 1:
        flip += 1
    else:
        n = int(P[i][1])
        v = P[i][2]
        if flip % 2 == 0:
            if n == 1:
                cap = v + cap
            else:
                tail = tail + v
        else:
            if n == 1:
                tail = tail + v
            else:
                cap = v + cap

answer = ""
if flip % 2 == 0:
    answer = cap + S + tail
else:
    answer = tail[-1::-1] + S[-1::-1] + cap[-1::-1]

print(answer)
### BUGGY CODE ###

import math
n=int(input())
z=0
ans=0
for N in range(1,n+1):
    ans=0
    z=0
    for x in range(1,100):
        for y in range(1,100):
            if x**2+y**2>=N:
                break
            if (x+y)**2+4*N-4*(x**2+y**2)-4*x*y>=0:
                z=((-x-y)+math.sqrt((x+y)**2+4*N-4*(x**2+y**2)-4*x*y))/2
                #print(x,y,z)
                if z>=1 and z%1==0:
                    ans+=1
                    #print(x,y,z)
    print(ans)


### FIXED CODE ###

n=int(input())
z=0
N=[0]*10000
ans=0
ko=0
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            ko=x**2+y**2+z**2+x*y+y*z+z*x
            if ko<=n:
                N[ko-1]+=1
            else:
                break
for i in range(n):
    print(N[i])
### BUGGY CODE ###

#2分探索
#md/cで交点が定まらない時の対案
n,k = map(int, input().split( ))
m = [tuple(map(int, input().split( ))) for i in range(n)]
#そもそも設定はn枚すべて焼く必要はない
mx = 10**15
mn = 0
from math import sqrt
def solve(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    if max(r1,r2,sqrt(rr0))*2>r1+r2+sqrt(rr0):
        return (x1,y1),(x2,y2)
    sv = sqrt(4*rr0*rr1 - cv**2)
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

#flag で breakしてたのが煩雑すぎて追えていなかったらしい
while mx-mn>10**(-6):
    md = (mx+mn)/2
    cnt = 0
    for i in range(n):##中心選ぶケースが抜けてる
        pi0,pi1 = m[i][0],m[i][1]
        tmp = 0
        for l in range(n):#kはすでに使っている変数
            if m[l][2]*sqrt(((pi0-m[l][0])**2) + ((pi1-m[l][1])**2))<=md:
                tmp += 1
        if cnt<tmp:
            cnt = tmp

    for i in range(n):
        for j in range(i+1,n):##range(i)だとi=0で止まって何もしない

            p = solve(m[i][0],m[i][1],md/m[i][2], m[j][0],m[j][1],md/m[j][2])

            for pi in p:
                tmp = 0
                for l in range(n):#kはすでに使っている変数
                    if (((pi[0]-m[l][0])**2) + ((pi[1]-m[l][1])**2))**(1/2)<=md/m[l][2]+0.000000001:##ここで誤差認めなかったせいらしい
                        tmp += 1
                if cnt<tmp:
                    cnt = tmp

    if cnt>=k:
        mx = md
    else:
        mn = md
print(mx)


### FIXED CODE ###

#2分探索
#md/cで交点が定まらない時の対案
n,k = map(int, input().split( ))
m = [tuple(map(int, input().split( ))) for i in range(n)]
#そもそも設定はn枚すべて焼く必要はない
mx = 10**15
mn = 0
from math import sqrt
def solve(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    if max(r1,r2,sqrt(rr0))*2>r1+r2+sqrt(rr0):
        return (x1,y1),(x2,y2)
    sv = sqrt(4*rr0*rr1 - cv**2)
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

#flag で breakしてたのが煩雑すぎて追えていなかったらしい
while mx-mn>10**(-6) and mx-mn>10**(-7)*mx:#mx大きい時に安易に設定すると到達しない？
    md = (mx+mn)/2
    cnt = 0
    for i in range(n):##中心選ぶケースが抜けてる
        pi0,pi1 = m[i][0],m[i][1]
        tmp = 0
        for l in range(n):#kはすでに使っている変数
            if m[l][2]*sqrt(((pi0-m[l][0])**2) + ((pi1-m[l][1])**2))<=md+0.000000001:
                tmp += 1
        if cnt<tmp:
            cnt = tmp

    for i in range(n):
        for j in range(i+1,n):##range(i)だとi=0で止まって何もしない

            p = solve(m[i][0],m[i][1],md/m[i][2], m[j][0],m[j][1],md/m[j][2])

            for pi in p:
                tmp = 0
                for l in range(n):#kはすでに使っている変数
                    if (((pi[0]-m[l][0])**2) + ((pi[1]-m[l][1])**2))**(1/2)<=md/m[l][2]+0.000000001:##ここで誤差認めなかったせいらしい
                        tmp += 1
                if cnt<tmp:
                    cnt = tmp

    if cnt>=k:
        mx = md
    else:
        mn = md
print(mx)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=set()
for i in range(n):
     su=0
     for j in range(i,n):
          su+=a[j]
          s.add(su)
s=list(s)
x=0
for i in range(40):
     x_=x+2**(39-i)
     cnt=0
     for a in s:
          if x_&a==x_:
               cnt+=1
     if cnt>=k:
          x=x_
print(x)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=set()
for i in range(n):
     su=0
     for j in range(i,n):
          su+=a[j]
          s.add(su)
s=list(s)
x=0
for i in range(40):
     x_=x+2**(39-i)
     cnt=0
     for a in s:
          if x_&a==x_:
               cnt+=1
     if cnt>=k:
          x=x_
print(x)
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline

    n, m, s, t = map(int, input().split())
    uvab = [list(map(int, input().split())) for _ in [0]*m]

    import numpy as np
    import scipy.sparse as sp
    data = [a for u, v, a, b in uvab]
    row = [u-1 for u, v, a, b in uvab]
    col = [v-1 for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    yen = sp.csgraph.dijkstra(matrix, indices=s-1, directed=False)

    data = [b for u, v, a, b in uvab]
    matrix = sp.csr_matrix(
        (data, (row, col)), shape=(n, n), dtype=np.int64)
    snk = sp.csgraph.dijkstra(matrix, indices=t-1, directed=False)

    cost = yen+snk
    m = cost[-1]
    for i in range(n-1, -1, -1):
        cost[i] = np.min(cost[i:i+2])

    cost = 10**15-cost

    for i in cost:
        print(int(i))


main()

### FIXED CODE ###

n,m,s,t=map(int,input().split())
uvab=[list(map(int,input().split())) for _ in [0]*m]
g_yen=[[] for _ in [0]*n]
[g_yen[u-1].append([v-1,a]) for u,v,a,b in uvab]
[g_yen[v-1].append([u-1,a]) for u,v,a,b in uvab]

g_snk=[[] for _ in [0]*n]
[g_snk[u-1].append([v-1,b]) for u,v,a,b in uvab]
[g_snk[v-1].append([u-1,b]) for u,v,a,b in uvab]

import heapq
def dijkstra(g,start):
    inf=10**15
    dist=[inf for _ in [0]*n]
    h=[(0,start)]
    heapq.heapify(h)
    while h:
        d,i=heapq.heappop(h)
        if dist[i]==inf:
            dist[i]=d
            for x,y in g[i]:
                heapq.heappush(h,(d+y,x))
    return dist

yen=dijkstra(g_yen,s-1)
snk=dijkstra(g_snk,t-1)

cost=[yen[i]+snk[i] for i in range(n)]
m=cost[-1]
for i in range(n-1,-1,-1):
    m=min(m,cost[i])
    cost[i]=m
    
for i in cost:
    print(10**15-i)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 998244353
half = pow(2, mod - 2, mod)
maxA = max(A)

cnt = [0] * (maxA + 1)
for Ai in A:
    cnt[Ai] += 1

w = [0] * (maxA + 1)
for i in range(1, maxA + 1):
    w[i] += pow(i, mod - 2, mod)
    w[i] %= mod
    for j in range(i * 2, maxA + 1, i):
        w[j] -= w[i]
        w[j] %= mod


def sum_cross(arr):
    s = 0
    s2 = 0
    for a in arr:
        s += a
        s2 += a ** 2
        s %= mod
        s2 %= mod
    return ((((s ** 2) % mod - s2) % mod) * half) % mod


ans = 0
for i in range(1, maxA + 1):
    Ai = []
    for j in range(i, maxA + 1, i):
        for k in range(cnt[j]):
            Ai.append(j)
    ans += w[i] * sum_cross(Ai)
    ans %= mod

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 998244353
half = pow(2, mod - 2, mod)
maxA = max(A) + 1


def main():
    cnt = [0] * maxA
    for Ai in A:
        cnt[Ai] += 1

    w = [pow(i, mod-2, mod) for i in range(maxA)]
    for i in range(1, maxA):
        for j in range(i * 2, maxA, i):
            w[j] = (w[j] - w[i]) % mod

    ans = 0
    for i in range(1, maxA):
        s = s2 = 0
        for j in range(i, maxA, i):
            s = (s + (j * cnt[j])) % mod
            s2 = (s2 + (j * j * cnt[j])) % mod
        ans += w[i] * ((((s ** 2) % mod - s2) % mod) * half) % mod
        ans %= mod
    print(ans)


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

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 28 13:44:44 2020

@author: NEC-PCuser
"""
N = int(input())
ans = 0
for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        ans += j

print(ans)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 28 13:44:44 2020

@author: NEC-PCuser
"""
N = int(input())
ans = 0
for i in range(1, N + 1):
    n = N // i
    ans += i * n * (n + 1) // 2 

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

from heapq import heappush, heappop
from collections import defaultdict

N, M = map(int, input().split())
INF = 10**18

edges = defaultdict(list)
C = set()
for _ in range(M):
    fr, to, c = map(int, input().split())
    edges[(fr, c)].append((to, c, 0))
    edges[(to, c)].append((fr, c, 0))

    edges[(fr, c)].append((fr, -1, 0))
    edges[(to, c)].append((to, -1, 0))

    edges[(fr, -1)].append((fr, c, 1))
    edges[(to, -1)].append((to, c, 1))
    C.add(c)

minDist = defaultdict(lambda: INF)
minDist[(1, -1)] = 0
que = [(0, 1, -1)]

while que:
    dist, now, c = heappop(que)

    for to, c, d in edges[(now, c)]:
        if minDist[(to, c)] > dist + d:
            minDist[(to, c)] = dist + d
            heappush(que, (dist + d, to, c))

ans = INF
for c in C:
    ans = min(ans, minDist[(N, c)])
print(ans if ans < INF else -1)


### FIXED CODE ###

from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.buffer.readline

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

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, c = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append((to, c))
    edges[to].append((fr, c))
    C.add(c)

minDist = [10**18] * (N + 1)
minDistList = [set() for _ in range(N)]
minDistList[0] = C

que = [(1, 0, 0)]
while que:
    dist, f, now = heappop(que)

    for to, c in edges[now]:
        d = dist
        if not c in minDistList[now]:
            d += 1
        if minDist[to] > d:
            minDist[to] = d
            minDistList[to] = set()
            heappush(que, (d, f + 1, to))
        if minDist[to] == d:
            minDistList[to].add(c)

for _ in range(2):
    que = [(minDist[i], 0, i) for i in range(N)]
    heapify(que)
    while que:
        dist, f, now = heappop(que)

        for to, c in edges[now]:
            d = dist
            if not c in minDistList[now]:
                d += 1
            if minDist[to] > d:
                minDist[to] = d
                minDistList[to] = set()
                heappush(que, (d, f + 1, to))
            if minDist[to] == d:
                minDistList[to].add(c)

ans = minDist[N - 1]
print(ans if ans < 10**18 else -1)