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

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if int(query[i][1]) == 1:
                s = query[i][2] + s
            else:
                s = s + query[i][2]
        else:
            if int(query[i][1]) == 2:
                s = query[i][2] + s
            else:
                s = s + query[i][2]
if rev == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
sa = []
sb = []
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
        else:
            if query[i][1] == '2':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
ssa = ''.join(sa)
ssa = ssa[::-1]
ssb = ''.join(sb)
ss = ssa + s + ssb
if rev == 1:
    ss = ss[::-1]
print(ss)
### BUGGY CODE ###

H,N = map(int,input().split())
A = []
for i in range(N):
    a,b = map(int,input().split())
    A.append((a,b))
MAXH = H+10000
DP = [float("inf")]*(MAXH)
DP[0] = 0
for i in range(0,MAXH):
    for a in A:
        if i-a[0]<0:continue
        DP[i] = min(DP[i],DP[i-a[0]]+a[1])
print(min(DP[H:]))

### FIXED CODE ###

H,N = map(int,input().split())
MAXH = H+10000
DP = [float("inf")]*MAXH
DP[0] = 0
for i in range(N):
    a,b = map(int,input().split())
    for j in range(MAXH-a):
        if j>H+a:break
        DP[j+a] = min(DP[j+a],DP[j]+b)
print(min(DP[H:]))
### BUGGY CODE ###

# 2019/04/29
# AtCoder Beginner Contest 085 - C

# Input
n, y = map(int,input().split())

cashl = [10000, 5000, 1000]
ansl = [-1, -1, -1]
eflg = False

# Search AC and make Accumed sum
for i in range(n+1):
    for j in range(n+1):
        if i + j > n:
            break
        
        subt = i * cashl[0] + j * cashl[1]
        k = int((y - subt) / 1000)

        total = i * cashl[0] + j * cashl[1] + k * cashl[2]
        bcnt = i + j + k

        if total == y and bcnt == n:
            ansl[0] = i
            ansl[1] = j
            ansl[2] = k
            eflg = True
            break

    if eflg == True:
        break

# Output
print(ansl[0], ansl[1], ansl[2])


### FIXED CODE ###

# 2019/04/29
# AtCoder Beginner Contest 085 - C

# Input
n, y = map(int,input().split())

cashl = [10000, 5000, 1000]
ansl = [-1, -1, -1]
eflg = False

# Search AC and make Accumed sum
for i in range(n+1):
    for j in range((n+1)-i):
        subt = i * cashl[0] + j * cashl[1]
        k = int((y - subt) / 1000)

        total = subt + k * cashl[2]
        bcnt = i + j + k

        if total == y and bcnt == n:
            ansl[0] = i
            ansl[1] = j
            ansl[2] = k
            eflg = True
            break

    if eflg == True:
        break

# Output
print(ansl[0], ansl[1], ansl[2])
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for _ in range(M)]
G1 = collections.defaultdict(lambda: collections.defaultdict(int))
G2 = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b in UVAB:
    u -= 1
    v -= 1
    G1[u][v] = G1[v][u] = a
    G2[u][v] = G2[v][u] = b


def dijkstra(V, G, i):
    INF = float('inf')

    H = []
    d = 0
    D = [INF] * V
    D[i] = 0
    used = [False] * V
    used[i] = True

    while True:
        for j in G[i].keys():
            heapq.heappush(H, (d + G[i][j], j))
        v = -1
        while H:
            d, j = heapq.heappop(H)
            if not used[j]:
                v = j
                break
        if v == -1:
            break
        else:
            used[v] = True
            D[v] = d
            i = v
    return D


D1 = dijkstra(N, G1, S - 1)
D2 = dijkstra(N, G2, T - 1)

D = [10**15 - sum(_) for _ in zip(D1, D2)]
for i in range(N - 1, 0, -1):
    D[i - 1] = max(D[i - 1], D[i])
print(*D, sep='\n')


### FIXED CODE ###

import math, string, itertools, fractions, collections, re, array, bisect, sys, random, time, copy, functools
from heapq import heappush, heappop, heappushpop, heapify, heapreplace
input = sys.stdin.readline

N, M, S, T = [int(_) for _ in input().split()]
UVAB = [[int(_) for _ in input().split()] for _ in range(M)]
G1 = collections.defaultdict(lambda: collections.defaultdict(int))
G2 = collections.defaultdict(lambda: collections.defaultdict(int))

for u, v, a, b in UVAB:
    u -= 1
    v -= 1
    G1[u][v] = G1[v][u] = a
    G2[u][v] = G2[v][u] = b


def dijkstra(V, G, start):
    INF = float('inf')
    D = [INF for _ in range(V)]
    D[start] = 0
    H = [(0, start)]
    while H:
        du, u = heappop(H)
        if D[u] < du:
            continue
        for v, d in G[u].items():
            if D[v] > du + d:
                D[v] = du + d
                heappush(H, (D[v], v))
    return D


D1 = dijkstra(N, G1, S - 1)
D2 = dijkstra(N, G2, T - 1)

D = [10**15 - sum(_) for _ in zip(D1, D2)]
for i in range(N - 1, 0, -1):
    D[i - 1] = max(D[i - 1], D[i])
print(*D, sep='\n')
### BUGGY CODE ###

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

loc = 1
loclog=[1]
flag = 0

for i in range(K):
    loc = A[loc-1]
    if loc in loclog:
        roopstart = loclog.index(loc)
        roopend = len(loclog)
        flag = 1
        break
    loclog.append(loc)

if flag == 0:
    ans = loc
else:
    roopidx = (K+1-roopstart)%(roopend-roopstart)
    if roopidx == 0:
        ans = loclog[roopend-1]
    else:
        ans = loclog[roopstart+roopidx-1]
print(ans)

### FIXED CODE ###

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

loc = 1
loclog=[1]
flag = 0
hist = [0]*N

for i in range(K):
    hist[loc-1] = 1
    loc = A[loc-1]
    if hist[loc-1] != 0:
        roopstart = loclog.index(loc)
        roopend = len(loclog)
        flag = 1
        break
    loclog.append(loc)

if flag == 0:
    ans = loc
else:
    roopidx = (K+1-roopstart)%(roopend-roopstart)
    if roopidx == 0:
        ans = loclog[roopend-1]
    else:
        ans = loclog[roopstart+roopidx-1]
print(ans)
### BUGGY CODE ###


def main():
    import math
    from functools import reduce
    k = int(input())
    s = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for l in range(1,k+1):
                s += reduce(math.gcd,[i,j,l])
    print(s)        
            
if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    import math
    from functools import reduce
    k = int(input())
    ans = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772,10813692]
    print(ans[k-1])
     
            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np
N, M = map(int,input().split())
A = list(map(int,input().split()))
A = np.array(A)
A.sort()
for _ in range(M):
    B, C = map(int,input().split())
    if A[B - 1] <= C:
        A[:B] = [C] * B
        A.sort()
    else:
        A = np.maximum(A, C)
print(np.sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
j = 0
for i in range(N):
    if A[i] >= BC[j][1]:
        break
    else:
        A[i] = BC[j][1]
        BC[j][0] -= 1
        if BC[j][0] == 0:
            j += 1
        if j >= M:
            break
print(sum(A))
### BUGGY CODE ###

import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [{} for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1][v - 1] = (a, b)
        AB[v - 1][u - 1] = (a, b)
        maxA = max(maxA, a)
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    while tc:
        t, u, s = heapq.heappop(cur)
        if T[u] == -1:
            T[u] = t
            tc -= 1
        c, d = CD[u]
        if s != maxS:
            heapq.heappush(cur, (t + d, u, min(s + c, maxS)))
        for v, (a, b) in AB[u].items():
            if s - a >= 0:
                heapq.heappush(cur, (t + b, v, s - a))
    print('\n'.join(map(str, T[1:])))

main()


### FIXED CODE ###

import heapq

def main():
    N, M, S = map(int, input().split())
    AB = [[] for _ in range(N)]
    maxA = 0
    for _ in range(M):
        u, v, a, b = map(int, input().split())
        AB[u - 1].append((a, b, v - 1))
        AB[v - 1].append((a, b, u - 1))
        maxA = max(maxA, a)
    for i in range(N):
        AB[i].sort()

    CD = [tuple(map(int, input().split())) for _ in range(N)]
    maxS = N * maxA
    cur = [(0, 0, S)]  # (time, station, silver)
    T = [-1] * N
    tc = N
    P = [-1] * N
    while tc:
        t, u, s = heapq.heappop(cur)
        if s <= P[u]:
            continue
        P[u] = s
        if T[u] == -1:
            T[u] = t
            tc -= 1
        for a, b, v in AB[u]:
            if s < a:
                break
            heapq.heappush(cur, (t + b, v, s - a))
        if s != maxS:
            c, d = CD[u]
            min_a = AB[u][0][0]
            k = max(1, (min_a - s + c  - 1) // c)
            heapq.heappush(cur, (t + k * d, u, min(s + k * c, maxS)))
    print('\n'.join(map(str, T[1:])))

main()
### BUGGY CODE ###

from time import *
from random import *
t=time()
T0,T1=2000,600
Tt=2000
D=int(input())
C=list(map(int,input().split()))
S=[list(map(int,input().split())) for i in range(D)]
X=[0]*26
XX=[0]*26
P=[]
for i in range(D):
  for j in range(26):
    X[j]+=C[j]
    XX[j]+=X[j]
  P.append([])
  for j in range(26):
    P[i].append(j)
  P[i].sort(reverse=True,key=lambda x:X[x]+S[i][x])
  XX[P[i][0]]-=X[P[i][0]]
  X[P[i][0]]=0
SC,SC2=0,0
for i in range(D):
  SC+=S[i][P[i][0]]
YY=[]
Y=[]
A,B=0,0
e=0
E=1
for i in range(50):
  e+=E
  E*=1/(i+1)
def f(x):
  global e,Tt
  if x>=0:
    return True
  else:
    return randrange(0,10000000)<=pow(e,x/Tt)
for l in range(12):
  for k in range(25):
    for i in range(D):
      SC2=SC
      YY=XX[:]
      Y=X[:]
      SC2-=S[i][P[i][0]]
      SC2+=S[i][P[i][k+1]]
      for j in range(26):
        Y[j]=0
      YY[P[i][0]],YY[P[i][k+1]]=0,0
      for j in range(D):
        if j==i:
          Z=P[j][k+1]
        else:
          Z=P[j][0]
        Y[P[i][0]]+=C[P[i][0]]
        Y[P[i][k+1]]+=C[P[i][k+1]]
        Y[Z]=0
        YY[P[i][0]]+=Y[P[i][0]]
        YY[P[i][k+1]]+=Y[P[i][k+1]]
      if f((SC2-sum(YY))-(SC-sum(XX))):
        P[i].insert(0,P[i][k+1])
        del P[i][k+2]
        XX=YY[:]
        SC=SC2
  for i in range(D*25):
    i%=D-1
    SC2=SC
    YY=XX[:]
    Y=X[:]
    A=i
    B=randrange(A+1,D)
    SC2-=S[A][P[A][0]]+S[B][P[B][0]]
    SC2+=S[A][P[B][0]]+S[B][P[A][0]]
    for j in range(26):
      Y[j]=0
    YY[P[A][0]],YY[P[B][0]]=0,0
    for j in range(D):
      if j==A:
        Z=P[B][0]
      elif j==B:
        Z=P[A][0]
      else:
        Z=P[j][0]
      Y[P[A][0]]+=C[P[A][0]]
      Y[P[B][0]]+=C[P[B][0]]
      Y[Z]=0
      YY[P[A][0]]+=Y[P[A][0]]
      YY[P[B][0]]+=Y[P[B][0]]
    if f((SC2-sum(YY))-(SC-sum(XX))):
      P[A],P[B]=P[B][:],P[A][:]
      XX=YY[:]
      SC=SC2
  Tt=pow(T0,1-(time()-t))*pow(T1,time()-t)
for i in range(D):
  print(P[i][0]+1)

### FIXED CODE ###

D=int(input())
for i in range(D):
  print(i%26+1)
### BUGGY CODE ###

import re

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

rex = r'([^_])\1{0,}'
pattern = re.compile(rex)

matchobj = pattern.search(S)
while matchobj:
    S = S.replace(matchobj.group(), "_", 1)
    matchobj = pattern.search(S)
print(len(S))


### FIXED CODE ###

import re

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

rex = r'(.)\1{0,}'
pattern = re.compile(rex)
ans = pattern.findall(S)

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

INF = 1000000000
class Edge:
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


def dijkstra(graph, start):
	V = len(graph)
	d = [INF for _ in xrange(V)]
	d[start] = 0

	done = [False for _ in xrange(V)]
	while True:
		mini = INF
		min_i = -1
		for i, node in enumerate(graph):
			if done[i] == False:
				if d[i] < mini:
					min_i = i
					mini = d[i]			
		if min_i == -1:
			return d
			
		done[min_i] = True
			
		node = graph[min_i]
		for edge in node:
			if d[min_i] + edge.cost < d[edge.to]:
				d[edge.to] = d[min_i] + edge.cost

def main():
	V, E, r = map(int, raw_input().split())

	graph = [[] for _ in xrange(V)]
	for i in xrange(E):
		_s, _t, _c = map(int, raw_input().split())
		graph[_s].append(Edge(_t, _c))


	distance = dijkstra(graph, r)
	for d in distance:
		if d == INF:
			print "INF"
		else:
			print d




if __name__ == '__main__':
	main()

### FIXED CODE ###

import heapq

INF = 1000000000
class Edge:
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


def dijkstra(graph, start):
	V = len(graph)
	d = [INF for _ in xrange(V)]
	d[start] = 0

	pq = []
	heapq.heappush(pq, (d[start], start))

	while len(pq) != 0:
		done = heapq.heappop(pq)
		node = graph[done[1]]
		for edge in node:
			if done[0] + edge.cost < d[edge.to]:
				d[edge.to] = done[0]+ edge.cost
				heapq.heappush(pq, (d[edge.to], edge.to))

	return d

def main():
	V, E, r = map(int, raw_input().split())

	graph = [[] for _ in xrange(V)]
	for i in xrange(E):
		_s, _t, _c = map(int, raw_input().split())
		graph[_s].append(Edge(_t, _c))


	distance = dijkstra(graph, r)
	for d in distance:
		if d == INF:
			print "INF"
		else:
			print d




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

n = int(input())
n_list = [int(i) for i in input().split()]
ans = 1
n_list.sort()
for i in n_list:
    ans *= i
    if ans > 10 ** 18:
        ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
n_list = [int(i) for i in input().split()]
ans = 1
n_list.sort()
n_list = list(reversed(n_list))
if 0 in n_list:
    print(0)
else:
    for i in n_list:
        ans *= i
        if ans > 10 ** 18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
import sys
import functools
#indexi番目にいるときの最小コスト
sys.setrecursionlimit(pow(10,6))


@functools.lru_cache(None)
def func(i):
    if i==0:
        return 0  

    h = H[i] 
    return min(func(i-k)+abs(h-H[i-k]) for k in range(1,min(i,K)+1))
        


print(func(N-1))

### FIXED CODE ###

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

dp = [0]*N
dp[1]= abs(H[1]-H[0])
#dp[i] インデックスiにいるときの最小値
inf = float("inf")

for i in range(1,N-1):
    tmp = inf
    oppai = min(K,i+1)
    for jump in range(1,oppai+1):
        tmp = min(tmp,dp[i+1-jump]+abs(H[i+1]-H[i+1-jump]))
    dp[i+1]=tmp
print(dp[N-1])
### BUGGY CODE ###

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

def main():
    s = input()
    q = int(input())

    r_flg = True

    for i in range(q):
        query = input().split()

        # query 1
        if query[0] == '1':
            r_flg = not r_flg
        
        # query 2 Fi = 1
        elif query[1] == '1':
            if r_flg:
                s = query[2] + s
            else:
                s = s + query[2]

        # query 2 Fi = 2
        else:
            if r_flg:
                s = s + query[2]
            else:
                s = query[2] + s

        # print('cont:{}, s:{}, r_flg:{}'.format(i, s, r_flg))

    if not r_flg:
        s = ''.join(reversed(s))

    print(s)

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
    s = input()
    q = int(input())
    q_list = list()

    for i in range(q):
        q_list.append(input())

    r_flg = True
    s_str = ''
    e_str = ''

    for query in q_list:
        # query 1
        if query[0] == '1':
            r_flg = not r_flg
        
        # query 2
        else:
            # Fi = 1
            if query[2] == '1':
                if r_flg:
                    s_str = query[4] + s_str
                else:
                    e_str = e_str + query[4]
            # Fi = 2
            else:
                if r_flg:
                    e_str = e_str + query[4]
                else:
                    s_str = query[4] + s_str

        # print('cont:{}, s:{}, r_flg:{}'.format(i, s, r_flg))

    s = s_str + s + e_str

    if not r_flg:
        s = ''.join(reversed(s))

    print(s)

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

def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    dp = [[0] * (n + 1) for _ in range(n+1)]

    for len in range(1, n + 1):
        for i in range(0, n - len + 1):
            j = i + len
            if (n - len) % 2 == 0:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])
    print(dp[0][n])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    dp = [[0] * (n + 1) for _ in range(n+1)]

    for len in range(1, n + 1):
        for i in range(0, n - len + 1):
            j = i + len
            if (n - len) % 2 == 0:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])
    print(dp[0][n])


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

def pypri(p,y):print(str(p).zfill(6)+str(y).zfill(6))
n,m=map(int,input().split())
a=[[]for _ in range(n)]
b=[]
for i in range(m):
  p,y=map(int,input().split())
  b.append(p-1)
  a[p-1].append([y,len(a[p-1])+1])
for i in range(n):
  a[i].sort()
  for j in range(len(a[i])):
    a[i][j]=[a[i][j][1],j]
    a[i].sort()
for i in b:
  pypri(i+1,a[i][0][1]+1)
  del a[i][0]


### FIXED CODE ###

n,m = map(int,input().split())
py = []
for i in range(m):
    py.append(list(map(int,input().split())))
    py[i].append(i)
py.sort(key=lambda x:x[1])
py.sort(key=lambda x:x[0])
x = py[0][0]
j=0
for i in range(m):
    if x != py[i][0]:
        j = 1
        x = py[i][0]
    else:
        j+=1
    s = str(py[i][0]).zfill(6) + str(j).zfill(6)
    py[i].append(s)
py.sort(key=lambda x:x[2])
for i in range(m):
    print(py[i][3])
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D
#??????????????????

def cal(truck_num, cargos):
    p = 0
    
    for i in range(len(cargos) - truck_num + 1):
        if not i == 0 and p < sum(cargos[:i + 1]):
            continue
        if truck_num > 1:
            r = max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:]))
            if i == 0:
                p = r
            elif p > r:
                p = r
        else:
            return sum(cargos)
    return p

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = [int(input()) for i in range(line_num)]
    print(cal(truck_num,cargos))

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D
#??????????????????

def cal(truck_num, cargos):
    p = 0
    
    for i in range(len(cargos) - truck_num + 1):
        if not i == 0 and p < sum(cargos[:i + 1]):
            continue
        if truck_num > 1:
            r = max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:]))
            if i == 0:
                p = r
            elif p > r:
                p = r
        else:
            return sum(cargos)
    return p

def check(truck_num, carogs, target_load):
    
    cur_truck = 1
    cur_weight = 0
    for weight in cargos:
        cur_weight += weight
        if cur_weight > target_load:
            cur_weight = weight
            cur_truck += 1
            if cur_truck > truck_num:
                return False
    return True

def solve(truck_num, cargs):

    max_load = sum(cargos)
    min_load = max(cargos)
    #print(min_load, max_load)
    while min_load < max_load:
        target_load = int((min_load + max_load)/2)
        if check(truck_num, cargos, target_load):
            max_load = target_load
        else:
            min_load = target_load + 1
        #print(min_load, max_load)
        
    return max_load

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = [int(input()) for i in range(line_num)]
    print(solve(truck_num,cargos))
### BUGGY CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcd(r, b)
    
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

l = 1
for a in A:
    l = lcm(l, a)

ans = 0
for a in A:
    ans += l // a

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

### FIXED CODE ###

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

###C - Monsters Battle Royale
N = int(input())
A = list(map(int, input().split()))

while(len(set(A)) != 1):
    for i in range(N):
        minA  = min(A)
        if A[i] > minA:
            time = A[i] // minA
            if time == 1:
                A[i] =A[i] -  time * minA
            else:
                A[i] =A[i] -  (time - 1) * minA
                
print(min(A))

### FIXED CODE ###

###C - Monsters Battle Royale
N = int(input())
A = list(map(int, input().split()))

while(len(set(A)) != 1):
    minA  = min(A)
    for i in range(N):
        if A[i] > minA:
            time = A[i] // minA
            if time == 1:
                A[i] =A[i] -  time * minA
            else:
                A[i] =A[i] -  (time - 1) * minA
                
print(min(A))