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

import copy
def main():
    line = input().split(' ')
    N, M = int(line[0]), int(line[1])
    root = [list(map(int, input().split(' '))) for i in range(M)]
    signpost = [0 for i in range(N+1)]

    mem1 = [1]
    while True:
        mem2 = []
        for node1, node2 in root:
            if node1 in mem1:
                if signpost[node2] == 0 and node2 != 1:
                    signpost[node2] = node1
                    mem2.append(node2)
            if node2 in mem1:
                if signpost[node1] == 0 and node1 != 1:
                    signpost[node1] = node2 
                    mem2.append(node1)
        if len(mem2) == 0:
            break
        mem1.clear()
        list(set(mem2))
        mem1 = copy.copy(mem2)

    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def main():
    N, M = map(int, input().split(' '))
    edge = [[] for i in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split(' '))
        edge[a].append(b)
        edge[b].append(a)
    signpost = [None] * (N+1)
    signpost[0] = signpost[1] = 0
    q = deque([1])
    dist = [0 for i in range(N+1)]
    while q:
        node = q.popleft()
        for e in edge[node]:
            if signpost[e] is None:
                dist[e] = dist[node] + 1
                signpost[e] = node
                q.append(e)
    if 0 in signpost[2:]:
        print('No')
    else:
        print('Yes')
        for i in signpost[2:]:
            print(i)        

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

from collections import Counter
import math

n = int(input())
a = list(map(int, input().split()))
nn = len(a) - 1
ctr = Counter(a)

f = {}

for aa in a:
    x = 0
    for k, v in ctr.items():
        if k == aa:
            v -= 1
        if v >= 2:
            if v not in f:
                f[v] = math.factorial(v)
            if (v - 2) not in f:
                f[v - 2] = math.factorial(v - 2)
            c = f[v] // (2 * f[v - 2])
            x += c
    print(x)


### FIXED CODE ###

from collections import Counter
import math

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

ctr = Counter(aa)

cmb2 = [0] * 200001
for n in range(2, 200001):
    r = 2
    num = 1
    for i in range(1, r + 1):
        num = num * (n - i + 1) // i
    cmb2[n] = num

x = 0
for k, v in ctr.items():
    x += cmb2[v]

for a in aa:
    k = ctr[a] - 1
    print(x - k)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
S = 0
for i in range(N - 1):
  for j in range(N - i - 1):
    # print(As[i], As[i + 1 + j])
    S += As[i] * As[i + 1 + j]
print(S % 1000000007)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
S = 0
T = 0
for i in range(N):
  S += As[i]
  T += (As[i] * As[i]) % 1000000007
# print(S)
# print(T)
A = S*S % 1000000007
B = T % 1000000007
X = (A - B) % 1000000007

print((X * int((1000000007 + 1)/2)) % 1000000007)
### BUGGY CODE ###

import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

def ff(N):
#     print("call ff{0}".format(N))
    if N > 100:
        n = int(np.sqrt(20))+5
    else:
        n = N
    cnt = 0
    for x in range(1, n+1):
        x2 = x**2
        for y in range(1, n+1):
            y2 = y**2
            xy = x * y
            tt = x2 + y2 + xy
            if tt > N:
                break
            for z in range(1, n+1):
                num = tt + z**2 + x*z + y*z
                if N == num:
                    cnt += 1
                elif N < num:
                    break
    return(str(cnt))    
    
N = int(input())    
n = int(np.sqrt(20))+1
pr = []
for i in range(1, N+1):
#     ff(i)
     pr.append(ff(i))
print("\n".join(pr))            













### FIXED CODE ###

import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

N = int(input())
n_np = np.zeros(105**3)
for i in range(1, 105):
    for j in range(1, 105):
        for k in range(1, 105):
            idx = i**2 + j**2 + k **2 + i*j + i*k + j*k
            n_np[idx-1] += 1
for i in range(N):
    print(int(n_np[i]))
### BUGGY CODE ###

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

Sa = [0]*N
Sb = [0]*M
Sa[0] = A[0]
Sb[0] = B[0]
a = 0
b = 0
if Sa[0] > K:
    a = 0
else: 
    for i in range(1, N):
        Sa[i] = Sa[i-1] + A[i]
        if Sa[i] > K:
            a = i
            break
    else:
        a = N
if Sb[0] > K:
    b = 0
else:
    for i in range(1, M):
        Sb[i] = Sb[i-1] + B[i]
        if Sb[i] > K:
            b = i
            break
    else:
        b = M

ans = max(a, b)
for i in range(a):
    temp = K - Sa[i]
    for j in range(b):
        if Sb[j] > temp:
            ans = max(ans, i+1+j)
            break
    else:
        ans = max(ans, i+1+b)
print(ans)


### FIXED CODE ###

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

Sa = [0]*(N+1)
Sb = [0]*(M+1)
Sa[0] = 0
Sb[0] = 0
for i in range(N):
    Sa[i+1] = Sa[i] + A[i]
for i in range(M):
    Sb[i+1] = Sb[i] + B[i]
ans = 0
for i in range(N+1):
    if Sa[i] > K:
        break
    for j in range(M, -1, -1):
        if Sa[i]+Sb[j] <= K:
            ans = max(ans, i+j)
            M = j
            break
    else:
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())
ans = float('inf')

for i in range(L,R):
    for j in range(i+1,R+1):
        ans = min(ans,(i * j)%2019)
        if ans == 0:
            break
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
ans = float('inf')

for i in range(L,R):
    for j in range(i+1,R+1):
        ans = min(ans,(i * j)%2019)
        if ans == 0:
            break
    else:
        continue
    break
print(ans)
### BUGGY CODE ###

n = int(raw_input())

aa = []
for i in range(n):
    t = int(raw_input())
    aa.append(t)

cnt = 0
b = [1]
a = aa[0]
while 1:
    cnt += 1
    if a == 2:
        print cnt
        exit()
    a = aa[a-1]
    if a in b:
        print -1
        exit()
    b.append(a)
    if cnt == n:
        print -1

### FIXED CODE ###

n = int(raw_input())

aa = []
for i in range(n):
    t = int(raw_input())
    aa.append(t)

cnt = 0
b = dict({1: True})
a = aa[0]
while 1:
    cnt += 1
    if a == 2:
        print cnt
        exit()
    a = aa[a-1]
    if a in b:
        print -1
        exit()
    b[a] = True
    if cnt == n:
        print -1
        exit()
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

for i in range(M):
    A[A.index(max(A))] /= 2

ans = 0
for i in range(N):
    ans += A[i]//1
    
print(int(ans))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = [-int(i) for i in input().split()]
heapq.heapify(A)

for i in range(M):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-tmp_min//2)*(-1))
    

print(-sum(A))
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

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

ans = 0


for a in range(n):
    fl = 0
    A = l[a]
    for b in range(a+1,n):
        B = l[b]
        if A > B*2:
            break
        for c in range(b+1,n):

            C = l[c]

            if A >= B + C:
                break

            ans += 1

print(ans)

### FIXED CODE ###

import bisect

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)

ans = 0

for a in range(n):
    fl = 0
    A = l[a]
    for b in range(a+1,n):
        B = l[b]

        idx = bisect.bisect_left(l, A+B)
        ans += max(0,idx-b-1)

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

n=int(input())
l=[]
for i in range(n):
    l.append(input())

alp=[chr(_) for _ in range(97,97+26)]
res=[0]*n
ans=0

for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    tmp2=0
    for z in res:
        if aa==z:
            tmp2+=1
    ans+=tmp2
    res[j]=aa
 
print(int(ans))

### FIXED CODE ###

import sys

n=int(input())
l=["".join(sorted(sys.stdin.readline().strip())) for i in range(n)]


res={}
ans=0
 
for j in range(n):
    ll=list(l[j])
    ll.sort()
    aa="".join(ll)
    if aa in res:
        ans+=res[aa]
        res[aa]+=1
    else:
        res[aa]=1

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

N,K = map(int,input().split())
s = list(map(int,input()))
s.append(2)
start = s[0]
choku = [0]
saka = [0]
number = 1
for i in range(N):
    if s[i] == s[i+1]:
        number += 1
    else:
        if s[i] == 0:
            choku.append(number)
            number = 1
        else:
            saka.append(number)
            number = 1
choku.append(0)
saka.append(0)
while(1):
    max_align = 0
    m = len(choku)
    n = len(saka)
    if m <= K:
        print(N)
        break
    if start == 0: #最初が直立の場合
        for i in range(m-K+1):
            if max_align <= sum(choku[i:i+K]) + sum(saka[i-1:i+K]):
                max_align = sum(choku[i:i+K]) + sum(saka[i-1:i+K])
    else:
        for i in range(m-K+1):
            if max_align <= sum(choku[i:i+K]) + sum(saka[i:i+K+1]):
                max_align = sum(choku[i:i+K]) + sum(saka[i:i+K+1])
    print(max_align)
    break

### FIXED CODE ###

N,K = map(int,input().split())
s = list(map(int,input()))
s.append(2)
start = s[0]
number = 1
choku = []
saka = [0]
for i in range(N):
    if s[i] == s[i+1]:
        number += 1
    else:
        if s[i] == 0:
            choku.append(number)
            number = 1
        else:
            saka.append(number)
            number = 1
choku.append(0)
saka.append(0)
while(1):
    max_align = 0
    m = len(choku)
    n = len(saka)
    if m <= K:
        print(N)
        break
    if start == 0: #最初が直立の場合
        aligns = [sum(choku[0:K]) + sum(saka[0:K+1])]
        for i in range(m-K-1):
            aligns.append(aligns[i] -choku[i]-saka[i] + choku[i+K] + saka[i+K+1])
        print(max(aligns))
    else:
        aligns = [sum(choku[0:K]) + sum(saka[1:K+2])]
        for i in range(m-K-1):
            aligns.append(aligns[i] -choku[i]-saka[i+1] + choku[i+K] + saka[i+K+2])
        print(max(aligns))
    break
### BUGGY CODE ###

def readinput():
    n,k=map(int,input().split())
    lr=[]
    for _ in range(k):
        l,r=map(int,input().split())
        lr.append((l,r))
    return n,k,lr

def main(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    dp[1]=1
    for i in range(1,n):
        #print(i)
        if dp[i]==0:
            continue
        skip=False
        for l,r in lrs:
            for j in range(l,r+1):
                #print('i+j: {}'.format(i+j))
                if i+j>n:
                    skip=True
                    break
                dp[i+j]=(dp[i+j]+dp[i])%MOD
                #print(dp)
            if skip:
                break
    return dp[n]

if __name__=='__main__':
    n,k,lr=readinput()
    ans=main(n,k,lr)
    print(ans)


### FIXED CODE ###

def readinput():
    n,k=map(int,input().split())
    lr=[]
    for _ in range(k):
        l,r=map(int,input().split())
        lr.append((l,r))
    return n,k,lr

def main(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    dp[1]=1
    for i in range(1,n):
        #print(i)
        if dp[i]==0:
            continue
        skip=False
        for l,r in lrs:
            for j in range(l,r+1):
                #print('i+j: {}'.format(i+j))
                if i+j>n:
                    skip=True
                    break
                dp[i+j]=(dp[i+j]+dp[i])%MOD
                #print(dp)
            if skip:
                break
    return dp[n]

def main2(n,k,lr):
    lrs=sorted(lr,key=lambda x:x[0])
    MOD=998244353
    dp=[0]*(n+1)
    ruiseki=[0]*(n+1)
    dp[1]=1
    ruiseki[1]=1
    for i in range(2,n+1):
        for l,r in lrs:
            if i-l<1:
                break
            dp[i]+=ruiseki[i-l]-ruiseki[max(1,i-r)-1]
        dp[i]=dp[i]%MOD
        ruiseki[i]=(ruiseki[i-1]+dp[i])%MOD
    return dp[n]

if __name__=='__main__':
    n,k,lr=readinput()
    ans=main2(n,k,lr)
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)
ans = 0
for i in range(N * (N-1) // 2):
    current = a_list[n_index, a_index]
    update = current[current] == n_index
    a_index[update] += 1

    if np.all(np.logical_not(update)):
        break
    else:
        ans += 1

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from sys import stdin
# import numpy as np
from collections import deque
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

move_in = [[[] for i in range(N)] for j in range(N)]
move_out = [[[] for i in range(N)] for j in range(N)]
cost = [[0] * N for _ in range(N)]
start_pair = []
for i in range(N):
    a_list = _li_()
    start_pair.append(a_list[0])
    for j in range(N-2):
        start = [min(i, a_list[j]), max(i, a_list[j])]
        end = [min(i, a_list[j+1]), max(i, a_list[j+1])]
        move_in[end[0]][end[1]].append((start[0], start[1]))
        move_out[start[0]][start[1]].append((end[0], end[1]))

count = 0
stack = deque([])
for i in range(N):
    pair = start_pair[i]
    if i < pair and i == start_pair[pair]:
        stack.append((i, start_pair[i]))
        cost[i][start_pair[i]] = 1
        count += 1


ans = 0
while stack:
    cand = stack.pop()
    for dest in move_out[cand[0]][cand[1]]:
        cost[dest[0]][dest[1]] = max(cost[dest[0]][dest[1]],
                                     cost[cand[0]][cand[1]] + 1)
        in_list = move_in[dest[0]][dest[1]]
        if in_list[0] == cand:
            del in_list[0]
        else:
            del in_list[1]
        if len(in_list) == 0:
            count += 1
            if len(move_out[dest[0]][dest[1]]) == 0:
                ans = max(ans, cost[dest[0]][dest[1]])
            else:
                stack.append(dest)

if count == (N * (N-1) // 2):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def ruiseki(mydata):
    res = [0]*(len(mydata)+1)
    for i in range(len(mydata)):
        res[i+1] = res[i] + mydata[i]
    return res

n, k , m = MI()
a = ruiseki(LI())
b = ruiseki(LI())
a = a
b = b

result = 0
for i, ii in enumerate(a):
    if ii > m:
        break
    for j, jj in enumerate(b):
        if ii + jj > m:
            break
        if result <= i+j:
            result = i+j

print(result)

### FIXED CODE ###

#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def ruiseki(mydata):
    res = [0]*(len(mydata)+1)
    for i in range(len(mydata)):
        res[i+1] = res[i] + mydata[i]
    return res

n, k , m = MI()
a = ruiseki(LI())
b = ruiseki(LI())
a = a
b = b

result = 0
index = k
for i, ii in enumerate(a):
    if ii > m:
        break
    while b[index] + ii > m:
        index -= 1
    result = max(result, i+index)
print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#グローバル変数
pn_list = [2,3]

def next_pn(pn):
    npn = pn + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list:
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list.append(npn)
    return npn

def check_a(n,a):
    res = "ok"
    for i in range(n):
        if a[i] > 1:
            res = "notyet"
    return res

# 整数の入力
n = int(input())
s = input()
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)

# a を素因数分解する
lcm = int(1)
for i in pn_list:
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(n):
            if a[j] % i == 0:
                a[j] = a[j] // i
                wareta = 1
        if wareta == 1:
            lcm = lcm * i
    if check_a(n,a) == "ok":
        break

pn_lcm = []
for i in a:
    if i > 1:
        if i not in pn_lcm:
            pn_lcm.append(i)

for j in pn_lcm:
    lcm = lcm * j

min_bsum = int(0)
for i in aa:
    min_bsum = min_bsum + lcm // i

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


### FIXED CODE ###

# -*- coding: utf-8 -*-
#グローバル変数
pn_list = [2,3]

def next_pn(pn):
    npn = pn + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list:
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list.append(npn)
    return npn

# 整数の入力
n = int(input())
s = input()
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)

# a を素因数分解する
lcm = int(1)
for i in pn_list:
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(n):
            if a[j] % i == 0:
                a[j] = a[j] // i
                wareta = 1
        if wareta == 1:
            lcm = lcm * i
pn_lcm = []
for i in a:
    if i > 1:
        if i not in pn_lcm:
            pn_lcm.append(i)
            lcm = lcm * i

min_bsum = int(0)
for i in aa:
    min_bsum = min_bsum + lcm // i

print(min_bsum % (10**9+7))
### BUGGY CODE ###

#EDPC L
import sys
sys.setrecursionlimit(10**8)

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

dp=[[-1]*N for _ in range(N)]


#for i in range(N-1):
#    for j in range()
def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))


### FIXED CODE ###

#EDPC L メモ化再帰じゃTLEで通らないのでやり直し

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

dp=[[-1]*N for _ in range(N)]

for k in range(N):
    dp[k][k]=a[k]

for r in range(1,N):
    for l in reversed(range(r)):
        dp[l][r]=max(a[l]-dp[l+1][r],a[r]-dp[l][r-1])

print(dp[0][N-1])
### BUGGY CODE ###

N, Y = map(int, input().split())
Y /= 1000
x = 10
y = 5
z = 1
res = [-1, -1, -1]
for i in reversed(range(int(Y/x)+1)):
    for j in range(int(Y/y)+1):
        if x*i+y*j <= Y:
            if Y-x*i-y*j+i+j == N:
                res = [i, j, int(N-i-j)]
                print(res[0], res[1], res[2])
                exit(0)
print(-1, -1, -1)


### FIXED CODE ###

N, Y = map(int, input().split())
Y /= 1000
x = 10
y = 5
z = 1
for i in range(N+1):
    for j in range(N+1):
        if x*i+y*j+(N-i-j) == Y and i+j <= N:
            print(i, j, N-i-j)
            exit()
print(-1, -1, -1)
### BUGGY CODE ###

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


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

dic = {}
for a in A:
    divs = make_divisors(a)
    for i in divs:
        if dic.get(i) is None:
            dic[i] = 1
        else:
            dic[i] += 1

ans = 0
for k in dic:
    if dic[k] >= N - 1:
        ans = max(ans, k)
print(ans)

### FIXED CODE ###

import fractions

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

# correct
L = [0] * N
R = [0] * N

for i in range(1, N):
    L[i] = fractions.gcd(L[i - 1], A[i - 1])
for j in range(0, N-1)[::-1]:
    R[j] = fractions.gcd(R[j + 1], A[j + 1])
ans = 0
for k in range(N):
    ans = max(ans, fractions.gcd(L[k], R[k]))
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        S = S[::-1]
    else:
        if query[1] == '1':
            S = query[2]+S
        else:
            S = S+query[2]

print(S)

### FIXED CODE ###

#import time
S = input()
Q = int(input())
f = True
head = []
tail = []
for i in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        f = not f
    else:
        if (query[1] == '1' and f) or (query[1] == '2' and not f):
            head.append(query[2])
        else:
            tail.append(query[2])

S = ''.join(head)[::-1]+S+''.join(tail)
if not f:
    S = S[::-1]
print(S)

# start = time.time()
# elapsed_time = time.time() - start
# print("elapsed_time:{0}".format(elapsed_time) + "[sec]")
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [float("inf")] * (H + 1 + max(A) - 1)
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            dp[h+a] = min(dp[h+a], dp[h]+b)
    ans = min(dp[H:])
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

INF = float("inf")


def main():
    H, N = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    dp = [INF] * (H + max(A))
    dp[0] = 0
    for h in range(H):
        for a, b in zip(A, B):
            if dp[h]+b < dp[h+a]:
                dp[h+a] = dp[h]+b
    ans = min(dp[H:])
    print(ans)


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

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

Dices = list(map(lambda n:(n+1)/2,Dices))

total=0
for i in range(N-K+1):
    j=i+K
    total = max(total,sum(Dices[i:j]))

print(total)



### FIXED CODE ###

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

Dices = list(map(lambda n:(n+1)/2,Dices))
import numpy as np 
Dices = np.cumsum(Dices)
# from collections import deque

# d=deque([])
# total= 0
# for i in range(N):
#     d.append((Dices[i]+1)/2)
#     if len(d)==K:
#         total = max(total,sum(d))
#         d.popleft()

# print(total)

#累積和
S=np.append(0,Dices)
total = 0
# for i in range(N+1):
#     S[i] = sum(Dices[:i])

for j in range(N-K+1):
    total = max(total,S[j+K]-S[j])

print(total)
### BUGGY CODE ###

l=int(input())
k=list(map(int,input().split()))
s=0
mod=10**9+7
for i in range(l-1):
    for j in range(i+1,l):
        
        s=(s+(k[i]*k[j]))%mod
        
        
print(s)     

### FIXED CODE ###

l=int(input())
k=list(map(int,input().split()))
s=0
mod=10**9+7
o=sum(k)
p=o**2

s=0
for i in k:
    s=(s+i**2)
    
print((p-s)//2%mod)