Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
num = [0] * m
for i in range(m):
    s, c = map(int, input().split())
    if num[s-1] != 0 and num[s-1] != c:
        print(-1)
        exit()
    num[s-1] = c

if 1 < n and num[0] == 0:
    print(-1)
    exit()

for i in range(1000):
    ok = True
    string = str(i)
    if len(string) == n:
        for j in range(n):
            if num[j] == 0:
                continue
            elif string[j] != str(num[j]):
                ok = False
                break
        if ok:
            print(i)
            exit()
print(-1)

### FIXED CODE ###

n, m = map(int,input().split())
sc = []
for i in range(m):
    sc.append(list(map(int,input().split())))

# 条件の整理
cnt = [0]*4
for i in range(m):
    cnt[sc[i][0]] += 1
    # 最上位桁が0
    # if sc[i][0] == 1 and sc[i][0] == 0 and n > 1:
    #     print(-1)
    #     exit()
    # 同じ桁に違う数字指定
    if cnt[sc[i][0]] > 1:
        
        val = []
        
        for j in range(m):
            if sc[j][0] == sc[i][0]:
                val.append(sc[j][1])
        
        if len(list(set(val))) > 1:
            print(-1)
            exit()


# 全探索
ans = []
for i in range(1000):
    if len(str(i)) == n:
        flg = True
        for j in range(m):
            digit = sc[j][0]
            val = sc[j][1]
            if int(str(i)[digit-1]) != val:
                flg = False
                break
        if flg == True:
            ans.append(i)

if len(ans) == 0:
    print(-1)
    exit()
print(min(ans))
n, z, w = map(int, input().split())
a = [int(x) for x in input().split()]
 
if n == 1:
    print(abs(a[0]) - w)
else:
    print(max(abs(a[n-2]-a[n-1]), abs(a[n-1]-w)))

### FIXED CODE ###

x, y = map(str, input().split())

if x<y:
    print("<")
elif x>y:
    print(">")
else:
    print("=")
from sys import stdin
from math import factorial

def permutations_count(n, r):
  return factorial(n) // factorial(r) // factorial(n - r)

N,K = map(int,stdin.readline().split())
mod = pow(10,9)+7

frame = N-K+1
for i in range(1,K+1):
  if K == N:
    if i == 1:
      print("1")
    else:
      print("0")
  else:
    select=permutations_count(frame, i) % mod
    pattern=permutations_count(K-1, i-1) % mod
    print((select * pattern) % mod )

### FIXED CODE ###

from sys import stdin
from math import factorial

def permutations_count(n, r):
  return factorial(n) // factorial(r) // factorial(n - r)

N,K = map(int,stdin.readline().split())
mod = pow(10,9)+7

frame = N-K+1
for i in range(1,K+1):
  if K == N:
    if i == 1:
      print("1")
    else:
      print("0")
  else:
    if i > frame:
      print("0")
    else:
      select=permutations_count(frame, i) % mod
      pattern=permutations_count(K-1, i-1) % mod
      print((select * pattern) % mod )
from decimal import Decimal
def solve():
    a,b,c = map(int, input().split())
    if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt()
        print('Yes')
    else:
        print('No')
    
if __name__ == '__main__':
    solve()

### FIXED CODE ###

import math
def solve():
    a,b,c = map(int, input().split())
    if 4 * a * b < (c-a-b)**2 and c-a-b>0:
        print('Yes')
    else:
        print('No')
    
if __name__ == '__main__':
    solve()
N = int(input())
a = map(int, input().split())

s = sum(a)

w = None
for i in a[:-1]:
  s -= 2 * a
  if w is None:
    w = s
  else:
    w = min(w, s)
print(w)


### FIXED CODE ###

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

s = sum(a)

w = None
for ai in a[:-1]:
  s -= 2 * ai
  if w is None:
    w = abs(s)
  else:
    w = min(w, abs(s))
print(w)
output = C -(A-B)
if output < 0:
    return 0
return output

### FIXED CODE ###

def main():
    A, B, C = map(int, input().split())
    output = C - A + B
    if output < 0:
        print(0)
    else:
        print(output)
main()
a,b=map(int,input().split())
i=1
while a//b>=b:
    a=a//b
    i+=1
if i != 1:
    i+=1
print(i)

### FIXED CODE ###

N,R=map(int,input().split())
if N>= 10:
  print(R)
else:
  print(R+(100*(10-N)))
n,m = map(int,input().split())
mod = 10 ** 9 + 7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    else:
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7 #出力の制限
N = n + 100
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#print(combo(2,1))


fac = [0] * (m+1)
mm = m
for i in range(2,m+1):
    while mm % i == 0:
        mm = mm // i
        fac[i] += 1
        #print(mm,fac)

count = 1

for i in range(2,m+1):
    if fac[i] >= 1:
        count = (count * cmb(fac[i]+n-1,fac[i],mod)) % mod
    #print(count)
    
print(count)

### FIXED CODE ###

n,m = map(int,input().split())
mod = 10 ** 9 + 7

def combo(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    else:
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod



N = n + 100
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#print(combo(2,1))

#print(m)
fac = {}
mm = m
#print(mm)
count = 0
while mm % 2 == 0:
    count += 1
    mm //= 2
if count > 0:
    fac[2] = count
f = 3
count = 0
while f ** 2 <= mm:
    while mm % f == 0:
        count += 1
        mm //= f
        #print(f,count)
    if count > 0:
        fac[f] = count
        count = 0
    f += 2
    #print(fac)
if mm != 1:
    if mm in fac:
        fac[mm] += 1
    else:
        fac[mm] = 1
#print(fac)

count = 1

for i in fac:
    if fac[i] >= 1:
        count = (count * combo(fac[i]+n-1,fac[i],mod)) % mod
    #print(count)
    
print(count)
from collections import deque

N = int(input())


vlist = [[]] * N

for i in range(N-1):
    a,b,w = map(int, input().split())
    a -= 1
    b -= 1
    vlist[a].append(b,w)
    vlist[b].append(a,w)

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)

### FIXED CODE ###

from collections import deque

N = int(input())


vlist = [[] for _ in range(N)]

for i in range(N-1):
    a,b,w = map(int, input().split())
    a -= 1
    b -= 1
    vlist[a].append((b,w))
    vlist[b].append((a,w))

ans = [-1] * N
q = deque()

ans[0] = 0
q.append(0)

while q:
    new = q.popleft()
    for node, weight in vlist[new]:
        if ans[node] != -1:
            continue
        ans[node] = (ans[new] + weight) % 2
        q.append(node)
    
for i in ans:
    print(i)
S=input()
T=input()

ans=10000

for i inrange(len(S)-len(T)+1):
  score=0
  U=S[i:i+len(T)]#Sのi文字目から{i+len(T)}文字目までがU->部分文字列を抜き出している
  for j in range(len(T)):
    if U[j] != T[J]:
      score += 1
  ans = min(ans, score)

print(ans)

### FIXED CODE ###

S=input()
T=input()

ans=10000

for i in range(len(S)-len(T)+1):
  score=0
  U=S[i:i+len(T)]#Sのi文字目から{i+len(T)}文字目までがU->部分文字列を抜き出している
  for j in range(len(T)):
    if U[j] != T[j]:
      score += 1
  ans = min(ans, score)

print(ans)
N = int(input())
A = []
ans = 0
for _ in range(N):
  B = input()
  if not B in A:
    ans += 1
    A.append(input())
print(ans)


### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
  A.append(input())
B = list(set(A))
print(len(B))
# -*- coding:utf-8 -*-
import sys
N = int(input())
lis = []
for i in range(N):
    s_raw = input().split()
    s = [int(j) for j in s_raw]
    lis.append(s)

def travel(t, x, y, count):
    if t > lis[N-1][0]:
        print("Yes")
        sys.exit()
    if t == lis[count][0]:
        if x == lis[count][1] and y == lis[count][2]:
            count += 1
        else:
            return
    travel(t+1, x+1, y, count)
    travel(t+1, x-1, y, count)
    travel(t+1, x, y+1, count)
    travel(t+1, x, y-1, count)

travel(0, 0, 0, 0)
print("No")


### FIXED CODE ###

# -*- coding:utf-8 -*-
N = int(input())

for i in range(N):
    t, x, y = map(int, input().split())
    if (x+y) > t or (x+y+t) % 2 == 1:
        print("No")
        exit()
print("Yes")
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
flag = 1
cur0 = 0
cur1 = 0
cur2 = 0
cnt = 0
for i in range(1,N):
    if A[i]>A[i-1]:
        flag += 1
        if flag==1:
            cur1 = i
        elif flag==2:
            cur2 = i
        elif flag==3:
            cnt = max(cnt,i-cur0)
            cur0 = cur1
            cur1 = cur2
            flag -= 1
            cur2 = i
#     print("cnt({})={}".format(i,cnt))
cnt = max(cnt,n-cur0)
print(cnt)

### FIXED CODE ###

from bisect import bisect_left,bisect_right
N = int(input())
A = sorted(list(map(int,input().split())))
G = {i:0 for i in range(10**5)}
cntmax = 0
for i in range(10**5):
    ind0 = bisect_left(A,i-1)
    ind1 = bisect_right(A,i+1)
    cntmax = max(cntmax,ind1-ind0)
print(cntmax)
a=int(input('a'))
b=int(input('b'))
if (a*b)%2 ==1
print ('Odd')
else:
  print ('Even')

### FIXED CODE ###

a,b=map(int,input().split())
if (a*b)%2 ==0:
  print('Even')
else:
  print('Odd')
A, B, C, X, Y=map(int, input().split())
if (A+B)>2*c:
  ans=2*C*min(X, Y)
  if X>Y:
    if A>2*C:
      ans+=2*C*(X-Y)
    else:
      ans+=A*(X-Y)
  else:
    if B>2*C:
      ans+=2*C*(Y-X)
    else:
      ans+=B*(Y-X)
else:
  ans=A*X+B*Y

print(ans)

### FIXED CODE ###

A, B, C, X, Y=map(int, input().split())
if (A+B)>2*C:
  ans=2*C*min(X, Y)
  if X>Y:
    if A>2*C:
      ans+=2*C*(X-Y)
    else:
      ans+=A*(X-Y)
  else:
    if B>2*C:
      ans+=2*C*(Y-X)
    else:
      ans+=B*(Y-X)
else:
  ans=A*X+B*Y

print(ans)
N = int(input())
A = int(input())

B = N % 500

if B > A:
  print("No')
        
else:
        print("Yes")
        
        

### FIXED CODE ###

N = int(input())
A = int(input())

B = N % 500

if B > A:
  print("No")
        
else:
        print("Yes")
# coding: utf-8
# Here your code !

Dice = [1,2,3] # top,front,right

def North(d):
    d = [d[1]] + [7 -d[0]] + [d[2]]
    return d
    
def East(d):
    d = [7-d[2]] + [d[1]] + [d[0]]
    return d
    
def South(d):
    d = [7-d[1]] + [d[0]] + [d[2]]
    return d

def West(d):
    d = [d[2]] + [d[1]] + [7-d[0]]
    return d

def Right(d):
    d = [d[0]] + [d[2]] + [7-d[1]]
    return d

def Left(d):
    d = [d[0]] + [7-d[2]] + [d[1]]
    return d



while True:
    n = int(input())
    if n == 0:
        break
    
    dice = [1,2,3]
    result = 1
    
    for _ in range(n):
        direction = input()
        # if direction == 'North':
        #     dice = North(dice)
        # if direction == 'East':
        #     dice = East(dice)
        # if direction == 'South':
        #     dice = South(dice)
        # if direction == 'West':
        #     dice = West(dice)
        dice = eval(direction+"(dice)")
        #print(dice)
        
        result += dice[0]
    
    print(result)
        

### FIXED CODE ###

# coding: utf-8
# Here your code !
import sys
f = sys.stdin

def North(d):
    d = [d[1]] + [7 -d[0]] + [d[2]]
    return d
      
def East(d):
    d = [7-d[2]] + [d[1]] + [d[0]]
    return d
      
def South(d):
    d = [7-d[1]] + [d[0]] + [d[2]]
    return d
  
def West(d):
    d = [d[2]] + [d[1]] + [7-d[0]]
    return d
  
def Right(d):
    d = [d[0]] + [d[2]] + [7-d[1]]
    return d
  
def Left(d):
    d = [d[0]] + [7-d[2]] + [d[1]]
    return d
  
  
  
while True:
    n = int(f.readline())
    if n == 0:
        break
      
    dice = [1,2,3]
    result = 1
      
    for _ in range(n):
        direction = f.readline().rstrip()
   
        dice = eval(direction+"(dice)")
     
          
        result += dice[0]
      
    print(result)
x,a,b = list(map(int,input().split()))
if b >= c:
  print("delicious")
elif a+b < c:
  print("dangerous")
else:
  print("safe")

### FIXED CODE ###

a,b,c = list(map(int,input().split()))
if b >= c:
  print("delicious")
elif a+b < c:
  print("dangerous")
else:
  print("safe")
n=int(input())
a=list(map(int,input()))
t=1
p=a[0]
m=0
for i in a:
  if(p==i):
    continue
  if(m>0):
    if(i<p):
      t+=1
      m=0
  elif(m<0):
    if(i>p):
      t+=1
      m=0
  else:
    if(i>p):
      m=1
    elif(i<p):
      m=-1
  p=i
print(t)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
t=1
p=a[0]
m=0
for i in a:
  if(p==i):
    continue
  if(m>0):
    if(i<p):
      t+=1
      m=0
  elif(m<0):
    if(i>p):
      t+=1
      m=0
  else:
    if(i>p):
      m=1
    elif(i<p):
      m=-1
  p=i
print(t)
from collections import Counter

def solve(n, v):
    # すべて同じ値
    if len(set(v)) == 1:
        return len(v) / 2

    odd = []
    even = []

    for i, k in enumerate(v):
        if i % 2 == 0:
            even.append(k)
        else:
            odd.append(k)

    odd_dic = Counter(odd).most_common()
    even_dic = Counter(even).most_common()

    ans = 0

    if odd_dic[0][0] == even_dic[0][0]:
        if odd_dic[0][1] > even_dic[0][1]:
            odd_v = odd_dic[0][0]
            even_v = even_dic[1][0]
        elif odd_dic[0][1] < even_dic[0][1]:
            odd_v = odd_dic[1][0]
            even_v = even_dic[0][0]
        else:
            if odd_dic[1][1] >= even_dic[1][1]:
                odd_v = odd_dic[1][0]
                even_v = even_dic[0][0]
            else
                odd_v = odd_dic[0][0]
                even_v = even_dic[1][0]
    else:
        odd_v = odd_dic[0][0]
        even_v = even_dic[0][0]

    for i in range(len(even)):
        if even_v != even[i]:
           ans += 1

        if odd_v != odd[i]:
            ans += 1

    return ans

def test():
    assert solve(4, [3, 1, 3, 2]) == 1
    assert solve(6, [105, 119, 105, 119, 105, 119]) == 0
    assert solve(4, [1, 1, 1, 1]) == 2

def main():
    n = int(input())
    v = list(map(int, input().split()))
    ans = solve(n, v)
    print(ans)

if __name__ == '__main__':
    # test()
    main()

### FIXED CODE ###

from collections import Counter

def solve(n, v):
    # すべて同じ値
    if len(set(v)) == 1:
        return len(v) / 2

    odd = []
    even = []

    for i, k in enumerate(v):
        if i % 2 == 0:
            even.append(k)
        else:
            odd.append(k)

    odd_dic = Counter(odd).most_common()
    even_dic = Counter(even).most_common()

    ans = 0

    if odd_dic[0][0] == even_dic[0][0]:
        if odd_dic[0][1] > even_dic[0][1]:
            odd_v = odd_dic[0][0]
            even_v = even_dic[1][0]
        elif odd_dic[0][1] < even_dic[0][1]:
            odd_v = odd_dic[1][0]
            even_v = even_dic[0][0]
        else:
            if odd_dic[1][1] >= even_dic[1][1]:
                odd_v = odd_dic[1][0]
                even_v = even_dic[0][0]
            else:
                odd_v = odd_dic[0][0]
                even_v = even_dic[1][0]
    else:
        odd_v = odd_dic[0][0]
        even_v = even_dic[0][0]

    for i in range(len(even)):
        if even_v != even[i]:
           ans += 1

        if odd_v != odd[i]:
            ans += 1

    return ans

def test():
    assert solve(4, [3, 1, 3, 2]) == 1
    assert solve(6, [105, 119, 105, 119, 105, 119]) == 0
    assert solve(4, [1, 1, 1, 1]) == 2

def main():
    n = int(input())
    v = list(map(int, input().split()))
    ans = solve(n, v)
    print(int(ans))

if __name__ == '__main__':
    # test()
    main()
N=int(input())
G=[[] for _ in range(N)]
ans=[-1]*N

for i in range(N-1):
    u,v,w=map(int,input().split())
    d=w%2
    G[u-1].append([v-1,d])
    G[v-1].append([u-1,d])

def dfs(x):
    if ans[x]!=-1:
        return ans[x]
    for y,w in G[x]:
        if seen[y]:continue
        seen[y]=True
        if ans[y]!=-1:
            seen[y]=False
            return (ans[y]+1)%2
        temp=dfs(y)
        if temp==None:
            seen[y]=False
        else:
            seen[y]=False
            return (temp+w)%2

ans[0]=0
seen=[False]*N
for g,e in G[0]:
    ans[g]=e%2


for i in range(N):
    ans[i]=dfs(i)

for a in ans:
    print(a)

### FIXED CODE ###


from copy import copy
N=int(input())
G=[[] for _ in range(N)]
di=[-1]*N
for i in range(N-1):
    u,v,w=map(int,input().split())
    G[u-1].append([v-1,w])
    G[v-1].append([u-1,w])

di[0]=0
for g,w in G[0]:
    di[g]=w

for i in range(1,N):
    if di[i]!=-1:continue
    seen=[0]*N
    stack=copy(G[0])
    seen[0]=1
    dis=0
    while stack:
        y,d=stack.pop()
        if seen[y]==1:continue
        seen[y]=1
        if y==i:
            di[i]=dis+d
            break
        else:
            for z,dist in G[y]:
                if seen[z]==0:
                    di[z]=dis+d+dist
                    stack.append([z,dis+d+dist])

for i in range(N):
    if di[i]%2==0:
        print(0)
    else:
        print(1)
a,b=map(int,input().split())

print(-~((a+b)/2))

### FIXED CODE ###

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

print(-(-(a+b)//2))
l = map(int, raw_input().split())

if l.count(5) == 2:
    if l.count(7) ==1:
        print('YES')
else:
    print('NO')

### FIXED CODE ###

a = list(map(int,input().split()))
b = a.count(5)
c = a.count(7)
if b == 2 and c == 1:
    print('YES')
else:
    print('NO')
# -*- coding: utf-8 -*-
"""
Created on Mon Feb 25 00:39:05 2019

@author: yuta
"""

def dic(n,m):
    x = ''.join(sorted(n))
    y = ''.join(sorted(m,reverse = True))
    if x < y:
        print("Yes")
    else:
        print("No")
dic(input(),input())

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 24 22:23:09 2019

@author: yuta
"""
import math

def pmean(a,b):
    x = math.ceil((a + b)/2)
    print(x)

c = input().split()
pmean(int(c[0]),int(c[1]))
#!/usr/bin/env python3
n, m = list(map(int, input().split()))

graph = [[] for i in range(n)]
for i in range(m):
    l, r, d = list(map(int, input().split()))

    graph[l-1].append([r-1, d])
    graph[r-1].append([l-1, -d])
# print(graph)


def dfs(s):
    for t, d in graph[s]:
        if x[t] is None:
            x[t] = x[s]+d
            if not dfs(t):
                return False
        else:
            if x[t]-x[s] != d:
                return False
    return True


x = [None]*n
ans = True
for i in range(n):
    if x[i] is None:
        x[i] = 0
        if not dfs(i):
            ans = False

print(('No', 'Yes')[ans])


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200002)

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

graph = [[] for i in range(n)]
for i in range(m):
    l, r, d = list(map(int, input().split()))

    graph[l-1].append([r-1, d])
    graph[r-1].append([l-1, -d])
# print(graph)


def dfs(s):
    for t, d in graph[s]:
        if x[t] is None:
            x[t] = x[s]+d
            if not dfs(t):
                return False
        else:
            if x[t]-x[s] != d:
                return False
    return True


x = [None]*n
ans = True
for i in range(n):
    if x[i] is None:
        x[i] = 0
        if not dfs(i):
            ans = False

print(('No', 'Yes')[ans])
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans = []
for i in set(range(x)):
    for j in set(range(y)):
        for l in set(range(z)):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i]+b[j]+c[l])
            else:
                break
ans.sort(reverse=True)
for ans in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        ans.append(a[i]+b[j]+c[k])
      else:
        break
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
n, m = map(int, input().split())
a = 0
for _ in range(m):
  a += int(input())
if a > n: print(-1)
else: print(n-a)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
print(max(n-sum(a), -1))
N = int(input())
A = list(map(int, input().split()))

Cost = lambda a, Sum:0 if (Sum > 0) ^ (Sum + a > 0) else abs(Sum + a) + 1
Sum = lambda a, preSum:preSum+a if (preSum > 0) ^ (preSum + a > 0) else -preSum//abs(preSum)

pSum = Sum(A[0],0)
nSum = Sum(A[0],0)
pCost = 0
nCost = 0
for a in A[1:]:
    pCost += Cost(a, pSum)
    pSum = Sum(a, pSum)
    nCost += Cost(a, nSum)
    nSum = Sum(a, nSum)
print(min(pCost, nCost))


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

def odd_positive(List):
    sum_a = 0
    cost = 0
    i = 0
    for a in List:
        i += 1
        sum_a += a
        if i & 1 and sum_a <= 0:
            cost += - sum_a + 1
            sum_a = 1
        elif (not i & 1) and sum_a >= 0:
            cost += sum_a + 1
            sum_a = -1
    return cost


def odd_negative(List):
    sum_a = 0
    cost = 0
    i = 0
    for a in List:
        i += 1
        sum_a += a
        if i & 1 and sum_a >= 0:
            cost += sum_a + 1
            sum_a = -1
        elif (not i & 1) and sum_a <= 0:
            cost += - sum_a + 1
            sum_a = 1
    return cost
    
ans = min(odd_positive(a), odd_negative(a)) 
print(ans)
n,k = map(int, input().split())
a =list(map(int, input().split()))
ans =1

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[-10**8]
    ap =[10**8]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:

            if min(amin)/min(ap) > max(amin)/max(am):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

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


### FIXED CODE ###

n,k = map(int, input().split())
a =list(map(int, input().split()))
ans =1

if n == k:
   for i in a:
       ans *= i
       if abs(ans) >10**9+7:
           ans = ans%(10**9+7)

elif all(i <= 0 for i in a) and k%2 ==1:
    a.sort(reverse = True)
    for i in range(k):
        ans *= a[i]
        if abs(ans) > 10 ** 9 + 7:
            ans = ans % (10 ** 9 + 7)

else:
    am =[]
    ap =[]

    a.sort(key = abs,reverse = True)
    amax = a[:k]
    amin = a[k:]
    c=1
    if 0 in amax:
        ans = 0
    else:
        for i in amax:
            if i<0:
                am.append(i)
                c *=-1
            elif i>0:
                ap.append(i)
        if c ==1:
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)
        else:
            if ap == []:
                amax.remove(max(am))
                amax.append(max(amin))

            elif max(am)*min(amin) < min(ap)*max(amin):
                amax.remove(max(am))
                amax.append(max(amin))
            else:
                amax.remove(min(ap))
                amax.append(min(amin))
            for i in amax:
                ans *= i
                if abs(ans) > 10 ** 9 + 7:
                    ans = ans % (10 ** 9 + 7)

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