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

k = int(input().split(" ")[-1])

a_ = [int(i) for i in input().split(" ")]
b_ = [int(i) for i in input().split(" ")]
c_ = [int(i) for i in input().split(" ")]

res = []
for a in a_:
    for b in b_:
        for c in c_:
            res.append(a+b+c)

res.sort()

res = res[::-1]
for i in range(k):
    print(res[i])

### FIXED CODE ###

x,y,z,K = (int(i) for i in input().split(" "))

a_ = sorted([int(i) for i in input().split(" ")])[::-1]
b_ = sorted([int(i) for i in input().split(" ")])[::-1]
c_ = sorted([int(i) for i in input().split(" ")])[::-1]

res = []
for i in range(x):
    for j in range(y):
        for k in range(z):
            if (i+1)*(j+1)*(k+1) <= K:
                res.append(a_[i]+b_[j]+c_[k])
            else:
                break

res = sorted(res)[::-1]

for i in range(K):
    print(res[i])
### BUGGY CODE ###

import sys

maxnum = 50001
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False

for s in sys.stdin:
    d = int(s)
    if d == 0: break
    print sum( [ 1 for i in xrange(2,int(d/2+1)) if primes[i] and primes[d-i] ] )

### FIXED CODE ###

from itertools import *
import sys

maxnum = 50001
primes = [True]*maxnum
primes[0] = primes[1] = False
for i in xrange(maxnum):
    if i >= maxnum**0.5 : break
    if not primes[i]: continue
    for j in xrange(i*2,maxnum,i): primes[j] = False

p = [ i for i in xrange(maxnum) if primes[i] ]
c = [0]*maxnum*2
for i,j in combinations_with_replacement(p,2):
    c[i+j] += 1

for s in sys.stdin:
    d = int(s)
    if d == 0: break
    print c[d]
### BUGGY CODE ###

n=int(input())
nn=n
l=len(str(n))
k=0
for i in range(n):
    k+=n%10
    n=n//10
print(['No','Yes'][nn%k==0])

### FIXED CODE ###

n=int(input())
nn=n
l=len(str(n))
k=0
for i in range(n):
    k+=n%10
    n=n//10
    if(n == 0):
        break
print(['No','Yes'][nn%k==0])
### BUGGY CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  assert time() - start < 0.5

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = map(int,input().split())
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  assert time() - start < 1.0
    
  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))
  
  assert time() - start < 1.5

  # 平面走査
  bit = BIT(N)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

### FIXED CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  # 平面走査
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

import itertools
n=int(input());S=list(map(sorted,[input() for _ in [1]*n]))
re=[]
for s in S:
    tmp=[]
    for i in range(len(s)):
        li=list(itertools.combinations(s,i))
        for lii in li:tmp.append(lii)
    re.append(tmp)
re2=re[0]
for i in range(1,len(re)):
    re2=list(set(re2)&set(re[i]))
l=max([len(r) for r in re2])
for i in range(len(re2)):
    if len(re2[i])==l:
        print(''.join(re2[i]))
        break

### FIXED CODE ###

n=int(input());S=list(map(sorted,[input() for _ in [1]*n]))
dicList=[]
for s in S:
    dic={}
    for c in list(s):
        dic[c]=dic.get(c,0)+1 
    dicList.append(dic)
result=''
c=[chr(i) for i in range(97, 97+26)]
count=0
while count<26:
    m = min([dic.get(c[count],0) for dic in dicList])
    if m==0:count+=1
    else:
        for dic in dicList:
            dic[c[count]]-=1
        result+=c[count]
print(result)
### BUGGY CODE ###

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

list_xst = []
for _ in range(n):
    s,t,x = list(map(int, input().split()))
    list_xst.append([x, s-x, t-x])

list_xst.sort(key=lambda l:l[0])

list_d = [int(input()) for _ in range(q)]

for d in list_d:
    retn = -1
    for xst in list_xst:
        if ( (xst[1] <= d) and (xst[2] > d) ):
            retn = xst[0]
            break
    print(retn)

### FIXED CODE ###

import bisect

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

list_xst = []
for _ in range(n):
    s,t,x = list(map(int, input().split()))
    list_xst.append([x, s-x, t-x])

list_xst.sort(key=lambda l:l[0])

list_d = [int(input()) for _ in range(q)]

retn = [-1] * q
jmp = [-1] * q

for x,s,t in list_xst:
    i = bisect.bisect_left(list_d, s)
    tt = bisect.bisect_left(list_d, t)
    while i < tt:
        if (jmp[i] != -1):
            i = jmp[i]
        else:
            retn[i] = x
            jmp[i] = tt
            i += 1

print(*retn, sep="\n")
### BUGGY CODE ###

from sys import stdin
import fractions

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = 1
ans = 0

for i in range(N):
    d = fractions.gcd(A[i], g % A[i])
    g *= A[i]
    g //= d

for i in range(N):
    ans += (g * pow(A[i], mod - 2, mod)) % mod

print(ans % mod)


### FIXED CODE ###

from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    while tmp <= A[i] ** 0.5:
        cnt = 0
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            cnt += 1
        if cnt > 0:
            g[tmp] = max(g[tmp], cnt)
        tmp += 1
    if a > 1:
        if a not in g:
            g[a] = 1

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

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

import bisect
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
for _ in range(M):
    B, C = map(int, input().split())
    if C >= A[0]:
        if C >= A[B-1]:
            if C >= A[N-1]:
                A = A[B:] + [C]*B
            else:
                x = bisect.bisect(A[B:], C)
                A = A[B:B+x] + [C]*B + A[B+x:]
        else:
            x = bisect.bisect(A[:B], C)
            A = [C]*x + A[x:]
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(map(int, input().split()))
BC = sorted((tuple(map(int, input().split())) for _ in range(M)), key=lambda x:x[1])
D = []
x = 0
for i in range(M-1,-1,-1):
    if x + BC[i][0] >= N:
        D += [BC[i][1]]*(N-x)
        break
    D += [BC[i][1]]*BC[i][0]
    x += BC[i][0]
for i in range(len(D)):
    if A[i] >= D[i]:
        break
    A[i] = D[i]
print(sum(A))
### BUGGY CODE ###

h,w,d=map(int,input().split())
dict={}

for i in range(1,h+1):
  lst=list(map(int,input().split()))
  for j in range(w):
    dict.setdefault(lst[j],(i,j+1))

dist=[0]*(h*w-d)

for i in range(h*w-d):
  dist[i]+=abs(dict[i+d+1][0]-dict[i+1][0])+abs(dict[i+d+1][1]-dict[i+1][1])


ans=0

q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    for j in range(l,r,d):
      ans+=dist[j-1]

    
    print(ans)

### FIXED CODE ###

h,w,d=map(int,input().split())
dict={}

for i in range(1,h+1):
  lst=list(map(int,input().split()))
  for j in range(w):
    dict.setdefault(lst[j],(i,j+1))

cost=[0]*(h*w)

for i in range(d,h*w):
  cost[i]=cost[i-d]+abs(dict[i-d+1][0]-dict[i+1][0])+abs(dict[i-d+1][1]-dict[i+1][1])


ans=0

q=int(input())
for i in range(q):
    ans=0
    l,r=map(int,input().split())
    print(cost[r-1]-cost[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
a = list(map(int, input().split()))
import fractions
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
import numpy as np
aa = np.array(a)
print(sum(ans//aa)%(10**9+7))


### FIXED CODE ###

from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in a:
    lcm = lcm * i // gcd(lcm, i)
ans = 0
for i in a:
    ans += (lcm//i)#%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=[0,0,0,0]
    count2=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count[i]=1
          count2+=1
    if count2<3 or (count==[1,0,0,1] or count==[1,1,0,0] or count==[0,1,1,0] or count==[0,0,1,1]):
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
  




### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
### BUGGY CODE ###

from random import shuffle
N = int(input())
S = input()

def check(l):
    r = list(range(N - 2 * l + 1))
    shuffle(r)
    for i in r:
        if S[i : i + l] in S[i + l :]:
            return True

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if check(m):
        ok = m
    else:
        ng = m

print(ok)

### FIXED CODE ###

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

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

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            tmp = 1
            if i > 0:
                tmp += dp[i - 1][j - 1]
            if j - i < tmp:
                continue
            dp[i][j] = tmp
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

import itertools
N, K = map(int, input().split())
# mod = 1000000007
Ns = []
for n in range(N+1):
    Ns.append(n)

# print(Ns)

count = 0
# Kこ以上とる組み合わせを作る
for k in range(K, N+2):
    ans = set()
    nums = itertools.combinations(Ns, k)
    # 重複を避けてカウント
    for num in nums:
        ans.add(sum(list(num)))
    count += len(ans)

print(count)


### FIXED CODE ###

N, K = map(int, input().split())
mod = 10 ** 9 + 7

ans = 0
for k in range(K, N+2):
    upper = k * ((N-k+1)+N) // 2
    lower = k * (k-1) // 2
    ans += upper - lower + 1
    ans %= mod
print(ans)
### BUGGY CODE ###

H,W = list(map(int,input().split()))

A = [list(str(input())) for i in range(H)]

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])

while (length > 0):
    gray = []
    if len(black) > length:
       
        for l in white:
            if [l[0],l[1]-1] in black or [l[0],l[1]+1] in black or [l[0]-1,l[1]] in black or [l[0]+1,l[1]] in black:
                gray.append(l)
    
    else:       
        for l in black:
            c1 = [l[0],l[1]-1]
            if c1 in white and c1 not in gray:
                gray.append(c1)
            c2 = [l[0],l[1]+1]
            if c2 in white and c2 not in gray:
                gray.append(c2)
            c3 = [l[0]-1,l[1]]
            if c3 in white and c3 not in gray:
                gray.append(c3)
            c4 = [l[0]+1,l[1]]
            if c4 in white and c4 not in gray:
                gray.append(c4)
    
    for l in gray:
        black.append(l)
        white.remove(l)
        
    cnt += 1
    length = len(white)
    
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

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

#output
import math
from functools import reduce

common_diviser = []
for i in range(1, min(A, B)+1):
    if A % i == 0 and B % i == 0:
        common_diviser.append(i)

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

ans = []
for c in common_diviser:
    if is_prime(c):
        ans.append(c)

print(len(ans)+1)    

### FIXED CODE ###

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

#output
import math

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
A1 = prime_factors(A)
B1 = prime_factors(B)        
C = set(A1) & set(B1)

print(len(C)+1)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    L, R = LI()
    diff = R - L
    L %= 2019
    R = min(L + diff, R % 2019 + 2019)
    ans = inf
    for i in range(L, R):
        for j in range(L + 1, R + 1):
            ans = min(ans, (i * j) % 2019)
    print(ans)

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    L, R = LI()
    diff = R - L
    L %= 2019
    R = min(L + diff, R % 2019 + 2019)
    ans = inf
    for i in range(L, R):
        for j in range(L + 1, R + 1):
            ans = min(ans, (i * j) % 2019)
    print(ans)

main()
### BUGGY CODE ###

s = input()

count = 1

for i in range(1, len(s)):
    ss = s[0:i]
    # print(ss, s[i])

    n = len(ss) - ss.count(s[i])
    count += n
    # print(n, count)
print(count)


### FIXED CODE ###

s = input()

count = 1

alphabets = {}

alphabets[s[0]] = 1

for i in range(1, len(s)):
    for char, char_count in alphabets.items():
        if char != s[i]:
            count += char_count

    if s[i] in alphabets:
        alphabets[s[i]] += 1
    else:
        alphabets[s[i]] = 1

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

def main():
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag[0][0][0]=True
  
  def sushi(c1,c2,c3):    
    if flag[c1][c2][c3]:
      return dp[c1][c2][c3]
    else:
      flag[c1][c2][c3]=True
      tmp=c1+c2+c3
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      dp[c1][c2][c3]=ans  
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  a=c1+c2+c3+1
  b=c2+c3+1
  c=c3+1
  
  dp=[[[0]*a for _ in range(b)] for _ in  range(c)]
  
  for i in range(c):
    for j in range(b-i):
      for k in range(a-i-j):
        tmp=i+j+k
        if tmp==0:
          continue
        else:
          dp[i][j][k]=n/tmp
          if i>0:
            dp[i][j][k]+=i*dp[i-1][j+1][k]/tmp
          if j>0:
            dp[i][j][k]+=j*dp[i][j-1][k+1]/tmp
          if k>0:
            dp[i][j][k]+=k*dp[i][j][k-1]/tmp
  print(dp[c3][c2][c1])
             
if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
tail = []
head = []
cost = []
for _ in range(m):
  l, r, c = map(int, input().split())
  tail.append(l - 1)
  head.append(r - 1)
  cost.append(c)
tail += list(range(1, n))
head += list(range(n - 1))
cost += [0] * (n - 1)

tail = np.array(tail, dtype=np.int)
head = np.array(head, dtype=np.int)
cost = np.array(cost, dtype=np.int)

inf = cost.sum() + 1
dp = np.ones(n, dtype=np.int) * inf
dp[0] = 0
act = 0
unexplr = np.ones(n, dtype=np.bool)
unexplr[0] = False
while unexplr[-1]:
  edge = (tail == act)
  dp[head[edge]] = np.minimum(dp[head[edge]], dp[act] + cost[edge])
  tmp = np.ones(n, dtype=np.int) * inf
  tmp[unexplr] = dp[unexplr]
  act = tmp.argmin()
  if not unexplr[act]:
    break
  unexplr[act] = False
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
edge = [[]] + [[(0, i)] for i in range(n-1)]
for _ in range(m):
  l, r, c = map(int, input().split())
  edge[l-1].append((c, r-1))

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and not check[-1]:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > d:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)
### BUGGY CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k*=10
  ans+=dp[s]
  dp[s]+=1
print(ans)

### FIXED CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
for i in range(N):
  if i==0:
    print(max(A[i+1:]))
  if i!=0 and i!=N-1:
    li1=max(A[:i])
    li2=max(A[i+1:])
    print(max(li1,li2))
  if i==N-1:
    print(max(A[:i]))
  

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
AA=sorted(A,reverse=True)
for i in range(N):
  if AA[0]!=A[i]:
    print(AA[0])
  else:
    print(AA[1])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
cost=[0]
for i in range(1, n):
  cost+=[min([cost[-j] + abs(a[i-j] - a[i]) for j in range(1,min(i,k)+1)])]
print(cost[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
cost=[0]
for i in range(1, n):
  cost+=[min([cost[-j] + abs(a[i-j] - a[i]) for j in range(1,min(i,k)+1)])]
print(cost[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = sorted([a_list.count(i) for i in range(n+1)],reverse = True)[:k]
print(n-sum(b_list))

### FIXED CODE ###

import collections
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b = collections.Counter(a_list)
d = b.most_common()[k:]
sum = 0
for i in d:
    sum += i[1]
print(sum)
### BUGGY CODE ###

n = int(input())

s = 0
t = 0
sum1 = 0

for i in range(n):
    s = n // (i+1)
    t = n % (i+1)
    if s == t:
        sum1 += i+1
        
print(sum1)
        

### FIXED CODE ###

n = int(input())

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

s = make_divisors(n)
sum = 0

for i in s:
    if i > 1:
        if n // (i - 1) == n % (i - 1):
            sum += i - 1

print(sum)