Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
n = int(input())

def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

def weight(x):
    find(x)
    return wei[x]

#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

def diff(x,y):
    return weight(y)-weight(x)

par = [-1]*n
wei = [0]*n
chk = []
for i in range(n-1):
  u,v,w = [int(i) for i in input().split()]
  chk_append = chk.append
  chk_append((u,v,w))
  
from operator import itemgetter
chk = sorted(chk,key=itemgetter(0))

for i in chk:
  unite(i[0]-1,i[1]-1,i[2])    

m = find(6)
for i in range(n):
  #print(diff(m,i),i+1)
  if diff(m,i)%2 == 0:
    print(0)
  else:
    print(1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(1000000)
n = int(input())

g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append((v, w))
    g[v].append((u, w))

chk = [0]*n
chk[0] = 1

def dfs(now, prev):
    global chk
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next[0] != prev:
          if next[1]%2 == 0:
            chk[next[0]] = chk[now]
          elif next[1]%2 == 1:
            chk[next[0]] = (chk[now]*-1)
          
          dfs(next[0], now)
        
dfs(0,-1)
chk = tuple(chk)
for i in chk:
  if i == 1:
    print(1)
  else:
    print(0)
population = int(input())
a2b = int(input())
b2c = int(input())
c2d = int(input())
d2e = int(input())
e2f = int(input())
vehicle_min = min(vehicle)
vehicle = [a2b,b2c,c2d,d2e,e2f]

print(int(population/vehicle_min) + 5)

### FIXED CODE ###

import math
population = int(input())
a2b = int(input())
b2c = int(input())
c2d = int(input())
d2e = int(input())
e2f = int(input())
city = [population,0,0,0,0,0]
vehicle = [a2b,b2c,c2d,d2e,e2f]
print(math.ceil(population/min(vehicle)) + 4)
def bs_left(list, target):
    low = 0
    high = len(list)

    while low < high:
        mid = (low + high) // 2
        if target > list[mid]:
            low = mid + 1
        else:
            high = mid
    return low

def bs_right(list, target):
    low = 0
    high = len(list)
    while low < high:
        mid = (low + high) // 2
        if target < list[mid]:
            high = mid
        else:
            low = mid + 1
    return low

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    ans += (bs_left(A, b) * (n - bs_right(C, b)))
print(ans)



### FIXED CODE ###

a=input()
b=input()
print('YES' if a[0]==b[2] and a[1]==b[1] and a[2]==b[0] else 'NO')
def main():
    from collections import defaultdict
    h, w = map(int, input().split())
    m = []
    o = []
    for _ in range(h):
        s = input()
        m.append(s)
        o.append(list(s))

    t = []
    for u in zip(*o):
        t.append(''.join(u))

    mr = [[0] * w for _ in range(h)]
    ml = [[0] * h for _ in range(w)]
    ans = 0
    for i in range(h):
        row = m[i]
        for j in range(w):
            col = t[j]
            if col[i] == '#':
                continue

            if mr[i][j]:
                c_row = mr[i][j]
            else:
                a, b = row[:j].rfind('#'), row[j + 1:].find('#')
                crl = j if a == -1 else j - 1 - a
                crr = w - j - 1 if b == -1 else b
                c_row = crl + crr
                # [j - crl, j + crr + 1)
                for k in range(j - crl, j + crr + 1):
                    mr[i][k] = c_row

            if ml[j][i]:
                c_col = ml[j][i]
            else:
                a, b = col[:i].rfind('#'), col[i + 1:].find('#')
                cll = i if a == -1 else i - 1 - a
                clr = h - i - 1 if b == -1 else b
                c_col = cll + clr
                # [i - cll, i + clr + 1)
                for k in range(i - cll, i + clr + 1):
                    ml[j][k] = c_col

            cnt = c_row + c_col + 1
            ans = max(ans, cnt)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

p,q,r=map(int,input().split())
print(sum([p,q,r])-max([p,q,r]))
import numpy as np

def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

def main():
    H, W = map(int, input().split())
    # 黒0，白1，padding2
    S = [[2] * (W+2)]
    for _ in range(H):
        S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
    S.append([2] * (W+2))
    S = np.array(S, dtype=np.int8)
    num_comb = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == 0:
                num_color = [0, 0]
                num_comb += trace(i, j, S, 0, num_color)
    print(num_comb)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def trace(i, j, S, col, num_color):
    next_col = 1 - col
    num_color[col] += 1
    S[i][j] = 2
    if S[i-1][j] == next_col:
        trace(i-1, j, S, next_col, num_color)
    if S[i][j-1] == next_col:
        trace(i, j-1, S, next_col, num_color)
    if S[i+1][j] == next_col:
        trace(i+1, j, S, next_col, num_color)
    if S[i][j+1] == next_col:
        trace(i, j+1, S, next_col, num_color)
    return num_color[0] * num_color[1]

def main():
    H, W = map(int, input().split())
    # 黒0，白1，padding2
    S = [[2] * (W+2)]
    for _ in range(H):
        S.append([2] + [0 if s == '#' else 1 for s in input()] + [2])
    S.append([2] * (W+2))
    num_comb = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == 0:
                num_color = [0, 0]
                num_comb += trace(i, j, S, 0, num_color)
    print(num_comb)

main()
input = input()
hour = input / 3600
minute = hour / 60
second = hour / 60
print("%1:%2:%3") % (hour,minute,second)

### FIXED CODE ###

input = int(input())
if 0 <= input < 86400:
    hour = input / 3600
    minute = (input / 60) % 60
    second = input % 60
    print("%d:%d:%d" % (hour,minute,second))
# 解けなかった...orz
from math import gcd

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

def gcd(i, j):
    if i <= 0:
        return j
    elif j <= 0:
        return i

    while i != j:
        if i < j:
            j %= i
            if j == 0: return i
        else:
            i %= j
            if i == 0: return j
    return i

# M = [0] * N
L = [0] * (N+1)
R = [0] * (N+1)
# L[0] = 0
# R[N] = 0

for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

res = max(gcd(L[i], R[i+1]) for i in range(N))
print(res)

### FIXED CODE ###

# 解けなかった...orz

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

def gcd(i, j):
    if i <= 0:
        return j
    elif j <= 0:
        return i

    while i != j:
        if i < j:
            j %= i
            if j == 0: return i
        else:
            i %= j
            if i == 0: return j
    return i

# M = [0] * N
L = [0] * (N+1)
R = [0] * (N+1)
# L[0] = 0
# R[N] = 0

for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

res = max(gcd(L[i], R[i+1]) for i in range(N))
print(res)
def prime(n):
    limit = math.floor(math.sqrt(n))
    for i in range(2,limit+1):
        if n % i == 0:
            return prime(n+1)
    return n

X = int(input())

print(prime(X))


### FIXED CODE ###

import math
def prime(n):
    limit = math.floor(math.sqrt(n))
    for i in range(2,limit+1):
        if n % i == 0:
            return prime(n+1)
    return n

X = int(input())

print(prime(X))
s = input()
s_s = list(set(s))

if len(s_s) >= 3:
  print("No")
else:
  if s.count(s_s[0]) == s.count(s_s[1]):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

s = input()
s_s = list(set(s))

if len(s_s) == 2:
  if s.count(s_s[0]) == s.count(s_s[1]):
    print("Yes")
else:
    print('No')
a = [[[0 for i in range(10)]for i in range(3)]for i in range(4)]
for i in range(4):
    a.append(np.zeros((3,10), dtype = int))
border = '#'*20
n = int(input())
for i in range(n):
    b,f,r,v = map(int,input().split())
    a[b-1][f-1][r-1] += v
    
for i in range(4):
    for k in a[i]:
        for l in k:
                print(' {}'.format(l), end ='')
        print()
    if i != 3:
        print(border)


### FIXED CODE ###

a = [[[0 for i in range(10)]for i in range(3)]for i in range(4)]
border = '#'*20
n = int(input())
for i in range(n):
    b,f,r,v = map(int,input().split())
    a[b-1][f-1][r-1] += v
    
for i in range(4):
    for k in a[i]:
        for l in k:
                print(' {}'.format(l), end ='')
        print()
    if i != 3:
        print(border)
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
res=[-1]*N
res[0]=0
def dfs(v,p,c):
    res[v]=c
    for nv,w in G[v]:
        if res[nv]>=0:
            continue
        if w&1:
            dfs(nv,v,1-c)
        else:
            dfs(nv,v,c)
dfs(0,-1,0)
for i in res:
    print(i)


### FIXED CODE ###

N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=map(int,input().split())
    u,v=u-1,v-1
    G[u].append((v,w))
    G[v].append((u,w))
reached=[0]*N
stack=[0]
reached[0]=[1]
res=[-1]*N
res[0]=0
while(stack):
    v=stack.pop()
    for nv,w in G[v]:
        if reached[nv]:
            continue
        if w & 1:
            res[nv]=1-res[v]
        else:
            res[nv]=res[v]
        stack.append(nv)
        reached[nv]=1
for i in res:
    print(i)
N = int(input())
h = []
for i in range(N):
    h.append(int(input()))
max = 0
for i in range(n):
    if max <= h[i]:
        max = h[i]
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
count = 0
max = 0
for i in range(N):
    if max <= h[i]:
        max = h[i]
        count += 1
print(count)
def combination(n, r):
    r = min(r, n-r)
    nume = 1
    denomi = 1
    for i in range(1, r+1):
        denomi *= i
    for i in range(n-r+1, n+1):
        nume *= i
    return nume // denomi

N, M = map(int, input().split())

sl = []
cnt = -1
ng = 0
for i in range(M):
    a = int(input())
    b = (a - 1) - (cnt + 1)
    if b == -1:
        ng = 1
    sl.append(max(b, 1))
    cnt = a

if ng:
    print(0)
else:
    sl.append(max(N - (a + 1), 1))
    ans = 1
    for s in sl:
        p = 0
        for i in range(s):
            j = s - i
            if (i <= j):
                p += combination(j, i)
            else:
                break
        ans *= p
    print(ans % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
a = [0]*N
for _ in range(M):
    idx = int(input()) - 1
    a[idx] = 1
    
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
for i in range(N-1):
    if a[i] == 0:
        dp[i+1] += dp[i]
        dp[i+2] += dp[i]
print(dp[N-1] % 1000000007)
s = list(input())
i=0
li = []
num = 0
while i<=len(s)-1:
    
    s1 = ["A","C","G","T"]
    
    if s[i] in s1 :
        num += 1
        i += 1
        li.append(num)
    elif s[i] not in s1 :
        num = 0
        i += 1
        
print(max(li))

### FIXED CODE ###

s = list(input())
i=0
li = [0]
num = 0
while i<=len(s)-1:
    
    s1 = ["A","C","G","T"]
    
    if s[i] in s1 :
        num += 1
        i += 1
        li.append(num)
    elif s[i] not in s1 :
        num = 0
        i += 1
        
print(max(li))
a = input()
if a = 'ABC':
  print('ARC')
else:
  print('ABC')

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def inp():
    return int(input())
def inps():
    return input().rstrip()
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

# ---------------------------------------

s = inps()
print("ARC" if s == "ABC" else "ABC")
N,M=map(int,input().split())
list1=list(map(int,input().split()))
list2=[]
for _ in range(M):
  B,C=map(int,input().split())
  if len(list2)<N and C>min(list1):
    list2+=[C]*B  
  if C>min(list2) and len(list2)>N:
    list2+=[C]*B  
list3=list1+list2
list3.sort(reverse=True)
list5=list3[:N]
SUM=sum(list5)
print(SUM)

### FIXED CODE ###

N,M = map(int, input().split())
listA = list(map(int, input().split()))
listA.sort()
 
listBC = [list(map(int, input().split())) for i in range(M)]
listBC = sorted(listBC, key=lambda x: x[1], reverse=True)
countB = 0
 
for i in range(M):
  B, C = listBC[i][0], listBC[i][1]
  listA += [C]*B
  countB += B
  if countB >= N:
    break

listA.sort(reverse=True)
print(sum(listA[:N]))
N = int(input())
X = input()
S = []
for a in range(N):
    S.append(X[a])

for i in range(N-1):
  if S[i] != S[i+1]:
    continue
  else:
    j = i+1
    while S[i] == S[j]:
      j += 1
    for l in range(i+1,j):
        S[l] = X
lista = [k for k in S if k != X]
print(''.join(lista))

### FIXED CODE ###

N = int(input())
X = input()
S = []
for a in range(N):
    S.append(X[a])

if N == 1:
    print(1)
else:
    for i in range(1,N):
        if S[i] != S[i-1]:
            continue
        else:
            S[i-1] = 'X'
    lista = [k for k in S if k != 'X']
    print(len(lista))
import math
a, b = map(int, input().split())
A = math.floor(a/0.08)
B = math.floor((a/0.8)/0.1)


c = math.gcd(A, B)
if c == 1:
    print(-1)
else:
    print(c)

### FIXED CODE ###


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

c =0 
for n in range(0,10000):
    taxa = int(n*8/100)
    taxb = int(n*10/100)
    if a == taxa and b == taxb:
        print(n)
        break
    else:
        c += 1
if c > 9999:
    print(-1)
n, h, w = map(int, input().split())
a_b = [list(map(int, input().split())) for _ range(n)]
cnt = 0
for i in range(n):
  if a_b[i][0] >= h and a_b[i][1] >= w:
    cnt += 1
print(cnt)

### FIXED CODE ###

n, h, w = map(int, input().split())
a_b = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
for i in range(n):
  if a_b[i][0] >= h and a_b[i][1] >= w:
    cnt += 1
print(cnt)
N,M,X = map(int,input().split())
print(N)
num = list(map(int, input().split()))
print(str_)
s = [i for i in num if i > X]
p = len(s)
q = M-p
if p >q:
    print(q)
else:
    print(p)

### FIXED CODE ###

N,M,X = map(int,input().split())
#print(N)
num = list(map(int, input().split()))
#print(str_)
s = [i for i in num if i > X]
p = len(s)
q = M-p
if p >q:
    print(q)
else:
    print(p)
from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import copy

# 入力 =stdin.readline().rstrip()
# 分割 = stdin.readline().rstrip().split()

'''
条件に合うものを絞り込む
data = [1, 2, 3]
s = [x for x in data if x % 3 == 0]
'''

'''
文字配列を数値に
l_si = ['-10', '0', '100']

l_si_i = [int(s) for s in l_si]
'''

'''
a = [2, 4, 6, 8]
b = [3, 6, 9]

print(list(set(a) | set(b)))  # 和集合
print(list(set(a) & set(b)))  # 積集合
'''

'''
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
while len([x for x in A if x % 2 == 0]) == N:
    A = list(map(lambda y: y / 2, A))
    count += 1
print(count)
'''

'''
.append(要素)
.insert(場所,要素)
-1で末尾で末尾から一つ前
'''
'''
間に空白追加
' '.join(lis)
'''
T = stdin.readline().rstrip()
num = int(stdin.readline().rstrip())
midcount = 1
res = []
ch = ''
for t in range(len(T)):
    if (ch == T[t] and t != 0):
        midcount += 1
    elif (ch != T[t] and t != 0):
        res.append(midcount)
        midcount = 1
    if (ch == T[t] and t == len(T) - 1):
        res.append(midcount)
    ch = T[t]

print(res)
if (len(res) == 1):
    print(str(int(num * len(T) / 2)))
elif (T[0] == T[len(T) - 1]):
    counter = 0
    tes = []
    tes.append(res[0] + res[len(res) - 1])
    tes += res[1: len(res) - 1]
    for x in tes:
        counter += int(x / 2)
    counter *= num - 1
    for x in res:
        counter += int(x / 2)
    print(counter)
else:
    counter = 0
    for x in res:
        counter += int(x / 2)
    counter *= num
    print(counter)


### FIXED CODE ###

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import copy

# 入力 =stdin.readline().rstrip()
# 分割 = stdin.readline().rstrip().split()

'''
条件に合うものを絞り込む
data = [1, 2, 3]
s = [x for x in data if x % 3 == 0]
'''

'''
文字配列を数値に
l_si = ['-10', '0', '100']

l_si_i = [int(s) for s in l_si]
'''

'''
a = [2, 4, 6, 8]
b = [3, 6, 9]

print(list(set(a) | set(b)))  # 和集合
print(list(set(a) & set(b)))  # 積集合
'''

'''
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
while len([x for x in A if x % 2 == 0]) == N:
    A = list(map(lambda y: y / 2, A))
    count += 1
print(count)
'''

'''
.append(要素)
.insert(場所,要素)
-1で末尾で末尾から一つ前
'''
'''
間に空白追加
' '.join(lis)
'''
T = stdin.readline().rstrip()
num = int(stdin.readline().rstrip())
midcount = 1
res = []
ch = ''
for t in range(len(T)):
    if (ch == T[t] and t != 0):
        midcount += 1
    elif (ch != T[t] and t != 0):
        res.append(midcount)
        midcount = 1
    if (ch == T[t] and t == len(T) - 1):
        res.append(midcount)
    ch = T[t]
if (len(T) == 1):
    res = [1]
if (len(res) == 1):
    print(str(int(num * len(T) / 2)))
elif (T[0] == T[len(T) - 1]):
    counter = 0
    tes = []
    tes.append(res[0] + res[len(res) - 1])
    tes += res[1: len(res) - 1]
    for x in tes:
        counter += int(x / 2)
    counter *= num - 1
    for x in res:
        counter += int(x / 2)
    print(counter)
else:
    counter = 0
    for x in res:
        counter += int(x / 2)
    counter *= num
    print(counter)
n=int(input())
a=list(map(int,input().split()))
m=int(input())
s=sum(a)
for i in range(m):
    p,x=map(int,input().split())
    print(s+x-a[p+1])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=int(input())
s=sum(a)
for i in range(m):
    p,x=map(int,input().split())
    print(s+x-a[p-1])
a = int(input())

if a == a.upper():
  return "A"
elif a == a.lower():
  return "a"

### FIXED CODE ###

α = input()
 
if α == α.upper():
  print('A')
elif α == α.lower():
  print('a')
def abc086_b():
    inpt = sum(map(str, input().split()))

    for i in range(100101):
        if inpt / i == i:
            return "Yes"

    return "No"


if __name__ == '__main__':
    print(abc086_b())

### FIXED CODE ###

def abc086_b():
    a, b = map(str, input().split())

    inpt = a + b

    for i in range(1, 100101):
        if int(inpt) / i == i:
            return "Yes"

    return "No"


if __name__ == '__main__':
    print(abc086_b())
# -*- coding: utf-8 -*-
n,m,l = [int(i)for i in input().split(' ')]
A = []
B = []
C = [[0for _ in range(n)]for _ in range(l)]
for i in range(n):
    A.append([int(a)for a in input().split(' ')])
for i in range(m):
    B.append([int(a)for a in input().split(' ')])

for i in range(n):
    for j in range(l):
        s = 0
        for k in range(m):
            s += A[i][k]*B[k][j]
        C[i][j] = s

for x in range(l):
    print(' '.join([str(a)for a in C[x]]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m,l = [int(i)for i in input().split(' ')]
A = []
B = []
C = [[0for _ in range(l)]for _ in range(n)]
for i in range(n):
    A.append([int(a)for a in input().split(' ')])
for i in range(m):
    B.append([int(a)for a in input().split(' ')])

for i in range(n):
    for j in range(l):
        s = 0
        for k in range(m):
            s += A[i][k]*B[k][j]
        C[i][j] = s

for x in range(n):
    print(' '.join([str(a)for a in C[x]]))
import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

def fun(A,N,dp,pos= 0):
    if pos == N-1:
        return 0
    elif pos == N-2:
        return abs(A[N-1] - A[N-2])
    if dp.get(pos,-1) != -1:
        return dp[pos]
    else:
        dp[pos]= min(abs(A[pos] - A[pos+1]) + fun(A,N,dp,pos+1), abs(A[pos] - A[pos+2]) + fun(A,N,dp,pos+2))
        return dp[pos]
    
dp = {}
N = int(input())
A = alele()
print(fun(A,N,dp))

### FIXED CODE ###

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

def fun(A,N):
    dp = [0]*N
    for pos in range(N):
        if pos == 0:
            dp[pos] = 0
        elif pos == 1:
            dp[pos]  = abs(A[pos-1] - A[pos])
        else:
            dp[pos]= min(abs(A[pos] - A[pos-1]) + dp[pos-1], abs(A[pos] - A[pos-2]) + dp[pos-2])
    return dp[-1]

N = int(input())
A = alele()
print(fun(A,N))
#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())

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

A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if len(A_pos) == 0:
    if K % 2 == 1:
        A_neg.sort(reverse=True)
    else:
        A_neg.sort()
    ans = 1
    for a in A_neg[:K]:
        ans = ans * a % MOD
    print(ans)
    sys.exit()

A_pos.sort()
A_neg.sort(reverse=True)
ans = 1
r = K
if r % 2 == 1:
    ans = ans * A_pos[0] % MOD
    A_pos = A_pos[1:]
    r -= 1

while r > 0:
    if len(A_pos) <= 1:
        ans = ans * A_neg[0] * A_neg[1] % MOD
    elif len(A_neg) <= 1:
        ans = ans * A_pos[0] * A_pos[1] % MOD

    else:
        acc_pos = A_pos[0] * A_pos[1]
        acc_neg = A_neg[0] * A_neg[1]

    if acc_pos > acc_neg:
        ans = ans * acc_pos % MOD
    else:
        ans = ans * acc_neg % MOD
    r -= 2
print(ans % MOD)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)
MOD = pow(10, 9) + 7

N, K, *A = map(int, read().split())

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

A_pos = [a for a in A if a >= 0]
A_neg = [a for a in A if a < 0]

if len(A_pos) == 0:
    if K % 2 == 1:
        A_neg.sort(reverse=True)
    else:
        A_neg.sort()
    ans = 1
    for a in A_neg[:K]:
        ans = ans * a % MOD
    print(ans)
    sys.exit()

A_pos.sort()
A_neg.sort(reverse=True)
ans = 1
r = K
if r % 2 == 1:
    ans = ans * A_pos.pop() % MOD
    r -= 1

while r > 0:
    if len(A_pos) <= 1:
        ans = ans * A_neg.pop() * A_neg.pop() % MOD
    elif len(A_neg) <= 1:
        ans = ans * A_pos.pop() * A_pos.pop() % MOD

    else:
        acc_pos = A_pos[-1] * A_pos[-2]
        acc_neg = A_neg[-1] * A_neg[-2]

        if acc_pos > acc_neg:
            ans = ans * A_pos.pop() * A_pos.pop() % MOD
        else:
            ans = ans * A_neg.pop() * A_neg.pop() % MOD
    r -= 2
print(ans % MOD)