Harryxun/stf_run huggingface dataset:
import pdb
import sys

def solve(a,N,K):
    dp = [10**9 for x in xrange(N)]
    dp[0] = 0
    for i in xrange(N-1):
        for j in xrange(1,K+1):
            if i+j < N:
                dp[i+j] = min(dp[i+j],abs(a[i]-a[i+j])+dp[i])
            else:
                break
    return dp[N-1]
    
if __name__=='__main__':
    N,K = map(int,raw_input().split())
    a = map(int,raw_input().split())
    print solve(a,N,K)


### FIXED CODE ###

import pdb
import sys

def solve(a,N):
    dp = [10**9 for x in xrange(N)]
    dp[0] = 0
    for i in xrange(N-1):
        if i+1 < N:
            dp[i+1] = min(dp[i+1],abs(a[i]-a[i+1])+dp[i])
        if i+2<N:
            dp[i+2] = min(dp[i+2],abs(a[i]-a[i+2])+dp[i])
        
    return dp[N-1]
    
if __name__=='__main__':
    N = int(raw_input())
    a = map(int,raw_input().split())
    print solve(a,N)
words = ''
w = []
flag = []
S = list(input())
for i in range(len(S)):
  if S[i] == 'A' or S[i] == 'T' or S[i] == 'G' or S[i] == 'C':
    flag.append('True')
  else:
    flag.append('False')

for j in range(len(S)):
  if flag[j] == 'True':
  	words += S[j]
  elif flag[j] == 'False':
    w.append(words)
    words = ''

print(len(max(w)))

### FIXED CODE ###

count = 0
MAX = 0
S = list(input())
for i in range(len(S)):
  if S[i] == 'A' or S[i] == 'T' or S[i] == 'G' or S[i] == 'C':
    count += 1
    if MAX < count:
        MAX = count
  else:
    count = 0

print(MAX)
a=input()
if a=A:
  print(T)
elif a=T:
  print(A)
elif a=C:
  print(G)
elif a=G:
  print(C)

### FIXED CODE ###

a=input()
if a=="A":
  print("T")
elif a=="T":
  print("A")
elif a=="C":
  print("G")
else:
  print("C")
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	print(A)
	if A [0] < 0:
		print(0)
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
	if t > M:
		print(0)
		flg2 = 1
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		while (A[t] == k):
			print(r)
			ans = ans*r
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
main()

### FIXED CODE ###

import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()
s = input()

start = s.index("A")

for i in range(len(s), start, -1):
    if s[i] == "Z":
        print(i - start + 1)
        break


### FIXED CODE ###

s = input()

start = s.index("A")

for i in range(len(s)-1, start, -1):
    if s[i] == "Z":
        print(i - start + 1)
        break
nput().split());a=[4,6,9,11];b=[1,3,5,7,8,10,12];print(['No','Yes'][(x in a and y in a)+x in b and y in b])

### FIXED CODE ###

x,y=map(int,input().split());a=[4,6,9,11];b=[1,3,5,7,8,10,12];print(['No','Yes'][int(x in a)*(y in a)+ int(x in b)*(y in b)])
from itertools import permutations
h,w=map(int,input().split())
d=[list(map(int,input().split())) for i in range(10)]

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
d=warshall_floyd(d)
cost=[d[i][1] for i in range(10)]

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)


### FIXED CODE ###

from itertools import permutations
h,w=map(int,input().split())
C=[list(map(int,input().split())) for i in range(10)]

cost=[C[i][1] for i in range(10)]
for i in range(10):
    if i!=1:
        keiyu=[x for x in range(10) if x!=1 and x!=i]
        for j in range(9):
            perm=permutations(keiyu,r=j)
            for k in perm:
                k=[i]+list(k)+[1]
                tmp=0
                for l in range(len(k)-1):
                    tmp+=C[k[l]][k[l+1]]
                cost[i]=min(tmp, cost[i])

from collections import defaultdict
count=defaultdict(int)
for i in range(h):
    A=list(map(int,input().split()))
    for a in A:
        count[a]+=1

ans=0
t=[x for x in range(10) if x!=1]
for i in t:
    ans+=cost[i]*count[i]
print(ans)
num = int(input())

vals = list(map(int,input().split()))

cnt = 0
while(True)
	for i in range(num):
    	if vals[i] % 2 == 1:
        	print(cnt)
        	break
        else:
    		vals[i] = vals[i] / 2
        cnt += 1

### FIXED CODE ###

num = int(input())
 
vals = list(map(int,input().split()))
 
cnt = 0
flag = True
while(flag):
	for i in range(num):
		if vals[i] % 2 == 1:
			print(cnt)
			flag = False
			break
		else:
			vals[i] = vals[i] / 2
	cnt += 1
N = int(input())

for i in range(10):
    for j in range(10):
        if N == i*j:
            print('Yes')
        if i*j == 81 and N!=81:
            print('No')
        if N == i*j:
            break
    if N== i*j:
        break


### FIXED CODE ###

A,B = map(int,input().split())
if A>9 or B>9:
    print(-1)
else:
    print(A*B)
N = input()
total = 0

for i in range(len(N)):
    if (N[i][1]=="BTC"):
        total += float(N[i][0])*380000
    else:
        total += float(N[i][0])
print(total)

### FIXED CODE ###

list = input().split("/")
y = int(list[0])
m = int(list[1])

if (y>=2019 and m>=5):
    print("TBD")
else:
    print("Heisei")
import math
# import sys
# import os
# f = open('input.txt', 'r')
# sys.stdin = f

n = int(input())
h = list(input().split())
h = [int(i) for i in h]
dp = [100000]*n
dp[0] = 0
dp[1] = h[1]-h[0]
for i in range(2, n):
    dp[i] = min(dp[i-1] + abs(h[i]-h[i-1], dp[i-2] + abs(h[i]-h[i-2]))

print(dp[n-1])


### FIXED CODE ###

import math
import sys
# import os
# f = open('input.txt', 'r')
# sys.stdin = f

n = int(input())
h = list(input().split())
h = [int(i) for i in h]
dp = [100000]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2, n):
    dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]))
print(dp[n-1])
s = input()
b = []
sho = 0
dai = 0
for i in range(len(s)):
	if(i == 0 and s[i+1] == ">"):continue
	if s[i] == "<":
		dai = 0
		sho += 1
		b.append(sho)
	else:
		sho = 0
		if(s[i-1] == "<" and i != 1):continue
		dai += 1
		b.append(dai)
#print(b)
print (sum(b))

### FIXED CODE ###

s = input()
a = [0]*(len(s)+1)

for i in range(len(s)):
  if s[i] == '<':
    a[i+1] = max(a[i+1],a[i]+1)

for i in range(len(s)-1,-1,-1):
  if s[i] == '>':
    a[i] = max(a[i],a[i+1]+1)
print (sum(a))
n = int(input())
if n==22:
  print(Christmas Eve Eve Eve)
elif n==23:
  print(Christmas Eve Eve)
elif n==24:
  print(Christmas Eve)
else:
  print(Christmas)

### FIXED CODE ###

d = int(input())
if d==25:
	print('Christmas')
elif d==24:
	print('Christmas Eve')
elif d==23:
	print('Christmas Eve Eve')
else:
	print('Christmas Eve Eve Eve')
from collections import deque
s=input()
length=len(s)

K=int(input())
#print(s,K)

left=0
right=0
#ss=s[left:right]
#print(ss)

ss=deque()
for left in range(length+1):
    for right in range(left+1,length+1):
        ss.append(s[left:right])

myset=set(ss)
for i in range(k):
    tmp=min(myset)
    myset.remove(tmp)
print(tmp)



### FIXED CODE ###

from collections import deque
s=input()
length=len(s)

K=int(input())
#print(s,K)

left=0
right=0
#ss=s[left:right]
#print(ss)

ss=deque()
for left in range(length+1):
    for right in range(left+1,length+1):
      if len(s[left:right]) <= K:
        ss.append(s[left:right])

myset=set(ss)
for i in range(K):
    tmp=min(myset)
    myset.remove(tmp)
print(tmp)
N, K = map(int,input().split())
a = [0] + list(map(int,input().split()))

journey = [1]

for i in range(N):
    nxt = a[journey[-1]]
    journey.append(nxt)

if K < N:
    print(journey[K])
    exit()

loop_start = N-1
loop_end   = N

finished = False
for i in range(N):
    for j in range(i,N+1):
        if journey[i] == journey[j]:
            loop_start = i
            loop_end   = j
            finished = True
            break
    if finished:
        break

period = loop_end - loop_start

ans = (K - loop_start) % period
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
a = [0] + list(map(int,input().split()))

journey = [1]

for i in range(2*N+1000):
    nxt = a[journey[-1]]
    journey.append(nxt)

if K <= N:
    print(journey[K])
    exit()

loop_start = N-1
loop_end   = N
 
while(journey[loop_start] != journey[loop_end]):
    loop_start -= 1
    
period = loop_end - loop_start

K %= period
while K < N:
  K += period

print(journey[K])
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
d=[0]*(n-1)
for j in range(n-1):
  d[j+1]=d[j]+h[j+1]-h[j]
m=1000000001
for l in range(n-k):
  m=min(m,d[l+k-1]-d[l])
print(m)
  
  
  
  

### FIXED CODE ###

n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
d=[0]*n
for j in range(n-1):
  d[j+1]=d[j]+h[j+1]-h[j]
m=float('inf')
for l in range(n-k+1):
  m=min(m,d[l+k-1]-d[l])
print(m)
impot math
N = int(input())

array = []
for i in range(1,math.floor((N)**0.5)+1)
    if N // i == 0:
        num = N // i
        array.append(num)
l = len(array)
print(int(array[l]) + (N / int(array[l])))

### FIXED CODE ###

import math
n = int(input())

a,b = 1,n
for i in range(1,int(math.sqrt(n)+1)):
    if n%i == 0:
        q = n//i
        if abs(a-b) > abs(q-i):
            a,b = i,q

print((a-1) + (b-1))
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = 998244353 ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [tuple(map(int,input().split())) for i in range(n)]
XD.append((-10**10,inf))
XD.sort()

now = 0
visited1 = [] 
def dfs(node):
  visited1.append(node)

  global now
  pro = 1
  while now < n :
    if XD[now+1][0] < XD[node][0] + XD[node][1]:
      now += 1
      pro *= dfs(now)
      pro %= mod
    else:break
  return pro + 1
ans = dfs(0)
print((ans-1)%mod)




### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()
visited = [0] * (n+1)
def dfs(node):
  visited[node] = 1
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      if visited[i]:continue
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break
  # print(node,res+1)
  return res + 1 , i
print((dfs(0)[0]-1)%mod)
# print(visited)
# print(XD)
# dfs(1)
a = list(map(int, input().split()))
#print(a)
b=[0]*a[1]
c=[0]*(a[1]+1)
b[0]=int(input())
c[0]=b[0]-0
for x in range(a[1]-1):
    b[x+1]=int(input())
    c[x+1]=b[x+1]-b[x]-1
c[-1]=a[0]-b[-1]
max = 0
min = a[0]+100
for x in c:
    if x>max:
        max=x
    if x<min:
        min=x
        
#print(c)
#print(max," ",min)
if min==0:
    print(0)
else:
    num=[0]*(max)
    for x in range(max):
        if x==0:
            num[0]=1
        elif x==1:
            num[1]=1
        else:
            num[x]=num[x-1]+num[x-2]
        #print("num[",x,"]=",num[x])
        
    answer=1
    for x in c:
        answer *=num[x-1]
    print(answer%1000000007)

### FIXED CODE ###

n,m = list(map(int, input().split()))
a=[]
a.append(-1)
for x in range(m):
  tmp=int(input())
  a.append(tmp)
a.append(n+1)
diff = []
for x in range(len(a)-1):
  diff.append(a[x+1]-a[x])
              
large = 0
small = 123456789012345
for x in diff:
  large=max(large,x)
  small=min(small,x)

num=[0,0,1]
for _ in range(large):
  num.append((num[-1]+num[-2])%1000000007)
    
answer=1
for x in diff:
  #print(x,num[x])
  answer *=num[x]
  answer%=1000000007
print(answer)
#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            factorial_ab = math.factorial(int(min(a, b)))
            ans = math.factorial(int(a+b)) / factorial_ab
    print(int(ans%MOD))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i) % MOD
        y = y * i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ( ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0) )  or ((a<0) or (b<0)):
        ans = 0
    else:
        ans = combi_count(a+b+1, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()
import itertools
n,m,q=map(int,input().split())
qs = [list(map(int,input().split())) for i in range(q)]
mids = [i for i in range(m)]
# print(nums)
max_ans= 0
for mid in itertools.combinations_with_replacement(nums, n-1):
    if sum(mid)>m-1:
        continue
    sum_ans=0
    for i in qs:
        sum_mid = 0
        for j in range(i[0]-1,i[1]-1):
            sum_mid += mid[j]
        if sum_mid == i[2]:
            sum_ans += i[3]
    if sum_ans > max_ans:
        max_ans = sum_ans
        
print(max_ans)

### FIXED CODE ###

import itertools
n,m,q=map(int,input().split())
qs = [list(map(int,input().split())) for i in range(q)]

max_ans = 0
for mid in itertools.combinations_with_replacement(range(1,m+1), n):
    sum_ans=0
    for q in qs:
        if mid[q[1]-1]-mid[q[0]-1] == q[2]:
            sum_ans += q[3]
    if sum_ans > max_ans:
        max_ans = sum_ans
        
print(max_ans)
na,nb,k = map(int, input().split())
ta = list(map(int, input().split()))
tb = list(map(int, input().split()))
 
def get_bcnt( usek,tb=tb ):
    t = 0
    cnt = 0
    try:
        while True:
            if t + tb[cnt] > usek:
                return cnt
            else:
                t += tb[cnt]
                cnt += 1
    except:
        return len(tb)
 
sumta = 0
readbook = [ i+1 + get_bcnt( k - sum( ta[:i] ) ) ) for i in range(na) if sum( ta[:i] ) <= k ]
readbook.append( get_bcnt(k) )

### FIXED CODE ###

na,nb,k = map(int, input().split())
ta = list(map(int, input().split()))
tb = list(map(int, input().split()))

a = [0]
for i in range(na):
  a.append( a[i] + ta[i] )
b = [0]
for i in range(nb):
  b.append( b[i] + tb[i] )

ans, j=0, nb
for i in range(na + 1):
  if a[i] > k:
    break
  while True:
    if a[i] + b[j] > k:
      j -= 1
    else:
      break
  ans = max(ans, i+j)
    
print(ans)
def Ics(X, Y):
    m = len(X)
    n = len(Y)
    maxl = 0
    for i in range(m + 1):
        c[i][0] = 0
    for j in range(1, n + 1):
        c[0][j] = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if(X[i] == Y[j]):
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i][j - 1], c[i - 1][j])
            maxl = max(maxl, c[i][j])
    return maxl

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(lcs(s1, s2))
print(*t, sep="\n")

### FIXED CODE ###

def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        c2 = c1[:]
        for j in range(n):
            if (d == Y[j]):
                c1[j + 1] = c2[j] + 1
            elif (c1[j + 1] < c1[j]):
                c1[j + 1] = c1[j]
    return (c1[-1])

q = int(input().rstrip())
t = []
for i in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep = "\n")
from fractions import gcd
a,b,c,d = map(int,input().split())
ls = [e for e in range(a,b+1)]
y = lambda x,z = c:x%z
ss = ls[:]
cmil = list(map(y,ss))
cmin = cmil.index(0) + a
bb = ls[::-1]
cmal = list(map(y,bb))
cmax = b - cmal.index(0) 
y = lambda x,z = d:x%z
dmil = list(map(y,ss))
dmin = dmil.index(0) + a
dmal = list(map(y,bb))
dmax = b - dmal.index(0)
y = lambda x,z = (c*d)/gcd(c,d):x%z
cdmil = list(map(y,ss))
cdmin = cdmil.index(0) + a
cdmal = list(map(y,bb))
cdmax = b - cdmal.index(0)
ca = (cmax - cmin)/c +1
da = (dmax - dmin)/d +1
cda = (cdmax - cdmin)/((c*d)/gcd(c,d)) +1
print(int(b-a+1-ca-da+cda))

### FIXED CODE ###

a,b,c,d = map(int,input().split())
cc = b//c -(a-1)//c
dd = b//d -(a-1)//d
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)
cd = lcm(c, d)
cdcd = b//cd -(a-1)//cd
print(b-a+1-cc-dd+cdcd)
N, Q = map(int, input().split())
edges = [input().split() for _ in range(N-1)]
operations = [input().split() for _ in range(Q)]

tree = {}
counter = [0]*N
result = [0]*N
numbers = []

for o in operations:
    counter[int(o[0])-1] += int(o[1])

result[0] = counter[0]

# print(counter)

for e in edges:
    parent = e[0]
    sun = e[1]
    if sun in numbers:
        sun = e[0]
        parent = e[1]
    else:
        numbers.append(sun)

    if sun in tree:
        tree[sun].append(parent)
    else:
        tree[sun] = [parent]

    if parent in tree:
        tree[sun].extend(tree[parent])


# print(tree)

for k in tree.keys():
    result[int(k)-1] += counter[int(k) - 1]
    for i in tree[k]:
        result[int(k)-1] += counter[int(i)-1]

print(' '.join(map(str, result)))

### FIXED CODE ###

a = int(input())
s = input()

if a >= 3200:
    print(s)
else:
    print("red")
N, K = map(int, input().split())
plus, minus = [], []
MOD = 10 ** 9 + 7
for a in map(int, input().split()):
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

plus.sort(reverse=True)
minus.sort()

if not plus:
    # 負値覚悟で取る
    ans = 1
    for x in minus[-K:]:
        ans = (ans * x) % MOD
    print(ans)
    exit()

idx = 0
for i in range(2, N, 2):
    if not len(plus) >= K - i + 2:
        idx += 2
        continue
    if len(minus) >= i:
        if minus[i - 2] * minus[i - 1] < plus[K - i + 1] * plus[K - i]:
            break
        else:
            idx += 2

ans = 1
for x in minus[:idx] + plus[:K - idx]:
    ans = (ans * x) % MOD
print(ans)


### FIXED CODE ###

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

if K == N:
    ans = 1
    for x in A:
        ans = (ans * x) % MOD
    print(ans)
    exit()

plus, minus = [], []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

plus.sort(reverse=True)
minus.sort()

if not plus:
    ans = 1
    if K % 2:
        # 答えは負値になるので絶対値小さいのを取る
        for x in minus[-K:]:
            ans = (ans * x) % MOD
    else:
        # 答えは非負値になるので絶対値大きいのを取る
        for x in minus[:K]:
            ans = (ans * x) % MOD
    print(ans)
    exit()

idx = 0
for i in range(2, N, 2):
    if K - i < 0:
        break
    if not len(plus) >= K - i + 2:
        idx += 2
        continue
    if len(minus) >= i:
        if minus[i - 2] * minus[i - 1] < plus[K - i + 1] * plus[K - i]:
            break
        else:
            idx += 2

ans = 1
for x in minus[:idx] + plus[:K - idx]:
    ans = (ans * x) % MOD
print(ans)
n,m=map(int,input().split())
L=sorted(list(map(int,input().split())))
print('Yes' if all([L[i]*m*4>=sum(L) for i in range(m)] else 'No')

### FIXED CODE ###

n,m=map(int,input().split())
L=sorted(list(map(int,input().split())),reverse=True)
print('Yes' if all([L[i]*m*4>=sum(L) for i in range(m)]) else 'No')
n = int(input())
list_c = list(map(int,input().split()))
list_d = []

for i in range(n):
  list_d.append(list(map(int,input().split())))

now = [0]*26

max_happy = 0
index_max = -1

for day in range(1,n+1):
  max_happy = 0
  index_max = -1
  for i in range(n):
    score = list_d[day-1][i] - (day - now[i]) * list_c[i]
    if score > max_happy:
      index_max = i
      max_happy = score
  
  print(index_max+1)
    
    


### FIXED CODE ###

from random import randint

n = int(input())

for i in range(n):
  print(randint(1,26))
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
for i in range(101):
    for j in range(101):
        hi=[]
        flg=True
        B=[]
        for a in A:
            if a[2]!=0:
                hi_=a[2]+abs(a[1]-j)+abs(a[0]-i)
                hi.append(hi_)
            else:
                B.append(a)
            if len(hi)>=2:
                if hi[-1]!=hi[-2]:
                    flg=False
        for b in B:
            if hi[0]-abs(a[1]-j)-abs(a[0]-i)>0:
                flg=False
        #print(i,j,hi)
        if flg:
            ans=[i,j,hi[0]]
print(*ans)


### FIXED CODE ###

N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
cnt=0
for a in A:
    if a[2]!=0:
        cnt+=1
        ans=a
if cnt==1:
    print(*ans)
    exit()
for i in range(101):
    for j in range(101):
        hi=[]
        flg=True

        for a in A:
            if a[2]!=0:
                hi_=a[2]+abs(a[1]-j)+abs(a[0]-i)
                hi.append(hi_)

            if len(hi)>=2:
                if hi[-1]!=hi[-2]:
                    flg=False
        #print(i,j,hi)
        if flg:
            ans=[i,j,hi[0]]

print(*ans)
K = int(input())
cand = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for _ in range(4):
    tmp = []
    for v in cand[-1]:
        if v%10 != 0:
            tmp.append(v*10 + (v%10-1))
        tmp.append(v*10 + (v%10))
        if v%10 != 9:
            tmp.append(v*10 + (v%10+1))
    cand.append(tmp)
ans = []
for i in range(len(cand)):
    for v in cand[i]:
        ans.append(v)
ans = sorted(ans)
print(ans[K-1])

### FIXED CODE ###

K = int(input())
cand = [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
for _ in range(9):
    tmp = []
    for v in cand[-1]:
        if v%10 != 0:
            tmp.append(v*10 + (v%10-1))
        tmp.append(v*10 + (v%10))
        if v%10 != 9:
            tmp.append(v*10 + (v%10+1))
    cand.append(tmp)
ans = []
for i in range(len(cand)):
    for v in cand[i]:
        ans.append(v)
ans = sorted(ans)
print(ans[K-1])
h,w=map(int,input().split())
print(-(-h*w//2) if h*w>=h+w else 1)


### FIXED CODE ###

a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n=int(input())
print(a[n-1])
#A*n = B*m + C
#Ax-By = Cを満たすx,yを求めよ
import fraction
a, b, c = map(int, input().split())
gcd = fraction.gcd(a, b)
if c % gcd == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a, b, c = map(int, input().split())
def gcd(x,y):
    p = max(x,y)
    q = min(x,y)
    while p % q != 0:
        r = p % q
        p = q
        q = r
    c = q
    return q
if c % gcd(a,b) == 0:
    print("YES")
else:
    print("NO")
n=int(input())
x=list(map(int, input().split()))

x.sort()

ans = 0

for i range(n):
  ans = ans + x[i*2]
    
print(ans)


### FIXED CODE ###

N = int(input())

L = list(map(int, input().split()))

L.sort()

ans = 0

for i in range(N):
    ans = ans + L[i*2]
    
print(ans)
k,x =map(int,input())
if x<=500*k:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

k,x=map(int,input().split())
if 500*k>=x:
    print("Yes")
else:
    print("No")