Harryxun/stf_run huggingface dataset:
import math
import sys
import collections


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

dp =[-1] * (N + 1)

def rec(v):
    if dp[v] != -1:
        return dp[v]


    res = 0
    for nv in di[v]:
        res = max(rec(nv) + 1 ,res)  # × dp[nv] ○ rec(nv) ∵ dp[nv]が未計算の場合があるから
    dp[v] = res
    return res

qs = [ list(map(int,input().split(" "))) for _ in range(M)]

# print(qs)
di = collections.defaultdict(lambda :[])
for q in qs:
    x,y = q
    di[x].append(y)
    #dp[y] → yを終点としたlongest path

for i in range(N + 1):
    rec(i)
print(max(dp))

### FIXED CODE ###

import math
import sys
import collections
import sys

sys.setrecursionlimit(200000)




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

dp =[-1] * (N + 1)

def rec(v):
    if dp[v] != -1:
        return dp[v]


    res = 0
    for nv in di[v]:
        res = max(rec(nv) + 1 ,res)  # × dp[nv] ○ rec(nv) ∵ dp[nv]が未計算の場合があるから
    dp[v] = res
    return res

qs = [ list(map(int,input().split(" "))) for _ in range(M)]

# print(qs)
di = collections.defaultdict(lambda :[])
for q in qs:
    x,y = q
    di[x].append(y)
    #dp[y] → yを終点としたlongest path

for i in range(N + 1):
    rec(i)
print(max(dp))
# Segment tree (Bitwise Or)
from operator import or_


class SegmentTree:
    _f = None
    _data = None
    _offset = None
    _size = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        f = self._f
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        f = self._f
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


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

st = SegmentTree(N, or_)
st.build(S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, c)
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))


### FIXED CODE ###

class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0 for _ in range(t * 2 - 1)]

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = [1 << (ord(c) - ord('a')) for c in iterable]
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = 1 << (ord(value) - ord('a'))
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = result | self._data[l]
            if r & 1 == 0:
                result = result | self._data[r - 1]
            l = l // 2
            r = (r - 1) // 2
        return result


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

st = SegmentTree(N)
st.update_all(S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, c)
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))
n=input()
a=[]
for i in range(n):
   a.append(int(raw_input()))
print '%d %d %d' % (min(a), max(a), sum(a))

### FIXED CODE ###

n=input()
a=map(int,raw_input().split())
print "%d %d %d" % (min(a), max(a), sum(a))
A, B = map(int, input().split())
print(A - 2*B if A - 2*B > 0 else: 0)

### FIXED CODE ###

A, B = map(int, input().split())
print(A - 2*B if A - 2*B > 0 else 0)
S = str(input())

if S == "SUN":
    cmd = 0
elif S == "MON":
    cmd = 1
elif S == "TUE":
    cmd = 2
elif S == "WED":
    cmd = 3
elif S == "THU":
    cmd = 4
elif S == "FRY":
    cmd = 5
elif S == "SAT":
    cmd = 6

if cmd == 0:
    print(7)
else:
    print(7-cmd)

### FIXED CODE ###

S = str(input())

if S == "SUN":
    cmd = 0
elif S == "MON":
    cmd = 1
elif S == "TUE":
    cmd = 2
elif S == "WED":
    cmd = 3
elif S == "THU":
    cmd = 4
elif S == "FRI":
    cmd = 5
elif S == "SAT":
    cmd = 6

print(7-cmd)
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def f():
    a,b = list(map(int, input().split()))
    if a * b == 0 or (a < 0 && b > 0):
        return 'Zero'
    if b < 0 and (a+b) % 2 == 0:
        return 'Negative'
    return 'Positive'

print(f())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def f():
    a,b = list(map(int, input().split()))
    if a * b == 0 or (a < 0 and b > 0):
        return 'Zero'
    if b < 0 and (a+b) % 2 == 0:
        return 'Negative'
    return 'Positive'

print(f())
import sys
input = sys.stdin.readline

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

for i in range(n):
    M[i][i] = 0

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

for k in range(n):
    for i in range(n):
        for j in range(n):
            M[i][j] = min(M[i][j], M[i][k] + M[k][j])

# M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

for i in range(n):
    M[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            M[i][j] = min(M[i][j], M[i][k] + M[k][j])

# M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))

### FIXED CODE ###

n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

from scipy.sparse.csgraph import floyd_warshall

for i in range(m):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        A[i][j] -= 1

for i in range(q):  # ノード番号が1始まりで与えられている場合
    for j in range(2):
        S[i][j] -= 1

M = [[float("inf")] * n for i in range(n)]

for i in range(n):
    M[i][i] = 0

for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(n):
    for j in range(n):
        M[i][j] = 1 if M[i][j] <= l else float("inf")

for i in range(n):
    M[i][i] = 0

# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

M = floyd_warshall(M)

for i in range(q):
    ans = M[S[i][0]][S[i][1]]-1
    if ans == float("inf"):
        ans = -1
    print(int(ans))
x,y,z,k = (int(i) for i in input().split())
a = sorted([int(i) for i in input().split()],reverse=True)
b = sorted([int(i) for i in input().split()],reverse=True)
c = sorted([int(i) for i in input().split()],reverse=True)

sa = 1
sb = 1
sc = 1

al = [a[0]]
bl = [b[0]]
cl = [c[0]]

inf = 10**20

while True:

    a_ = a[0] - a[sa] if sa < x else inf
    b_ = b[0] - b[sb] if sb < y else inf
    c_ = c[0] - c[sc] if sc < z else inf
    m = min([a_,b_,c_])
    if a_ == m:
        al.append(a[sa])
        sa += 1
    if b_ == m:
        bl.append(b[sb])
        sb += 1
    if c_ == m:
        cl.append(c[sc])
        sc += 1

    if len(al) * len(bl) * len(cl) > k:
        break


da = list(map(lambda x:a[0]-x, a))
db = list(map(lambda x:b[0]-x, b))
dc = list(map(lambda x:c[0]-x, c))
d_ = al[-1] + bl[-1] + cl[-1]
for i in range(sa,x):
    if da[i] < d_:
        al.append(a[i])

for i in range(sb,y):
    if db[i] < d_:
        bl.append(b[i])

for i in range(sc,z):
    if dc[i] < d_:
        cl.append(c[i])

res = []
for a_ in al:
    for b_ in bl:
        for c_ in cl:
            res.append(a_+b_+c_)


for x in sorted(res, reverse=True)[:k]:
    print(x)

### FIXED CODE ###

x,y,z,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

ab = []
for a_ in a:
    for b_ in b:
        ab.append(a_+b_)

res = []
for ab_ in sorted(ab, reverse=True)[:k]:
    for c_ in sorted(c, reverse=True)[:k]:
        res.append(ab_+c_)

for x in sorted(res, reverse=True)[:k]:
    print(x)
n = int(input())
b=[0]*10**9
for i in range(n):
  j=int(input())-1
  if b[j]:
    b[j]=0
  else:
    b[j]=1
print(sum(b))

### FIXED CODE ###

from collections import Counter 
n=int(input())
a=Counter([int(input()) for _ in range(n)])
ans=0
for i in a.values():
  ans+=i%2
print(ans)
import math
n = input()
n = int(n)
spl_list = [1]
for i in range(1,round(math.sqrt(n)) + 1):
  if n % i == 0:
    spl_list.append(i)

max_i = max(spl_list)
max_j = n / max_i
print(round(max_i + maxj -2))
  

### FIXED CODE ###

import math
n = input()
n = int(n)
spl_list = [1]
for i in range(1,round(math.sqrt(n)) + 1):
  if n % i == 0:
    spl_list.append(i)

max_i = max(spl_list)
max_j = n / max_i
print(round(max_i + max_j -2))
N, Q = map(int, input().split())
S = " " + input()
l = []
r = []
for _ in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
dp = [0] * (N + 2) #i文字目から何個ACがあるか
for i in range(1, N + 1):
    dp[i] = S[i:].count("AC")
#print(dp)
ans = 0
for q in range(Q):
    ans = dp[l[q]] - dp[r[q] + 1]
    if S[r[q]] == "A" and S[r[q] + 1] == "C":
        ans -= 1
    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = " " + input()
l = []
r = []
for _ in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
dp = [0] * (N + 2) #i文字目から何個ACがあるか
cnt = 0
for i in range(1, N):
    if S[-i] == "C" and S[-i-1] == "A":
            cnt += 1
    dp[N-i] = cnt
#print(dp)
ans = 0
for q in range(Q):
    ans = dp[l[q]] - dp[r[q] + 1]
    if r[q] < N:
        if S[r[q]] == "A" and S[r[q] + 1] == "C":
            ans -= 1
    print(ans)
a,b,c,d=map(int ,input().split())
if a==b==c or b==c==d or a==b==c==d:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a=list(input())
if a[0]==a[1]==a[2] or a[1]==a[2]==a[3]:
  print("Yes")
else:
  print("No")
x = []
for i in range(5):
	x.append(int(input()))

if max(x)-min(x) <= int(input()):
	print('Yay!')
else:

### FIXED CODE ###


x = []
for i in range(5):
	x.append(int(input()))
k = int(input())
if max(x)-min(x) <= k:
	print('Yay!')
else:
	print(':(')
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
 
int main(void){
    int n;
    cin >> n;
    vector<pair<pair<string,int>,int>> rest(n);
    for(int i = 0;i < n;i++){
        cin >> rest[i].first.first >> rest[i].first.second;
        rest[i].first.second *= -1;
        rest[i].second = i+1;
    }
 
    sort(rest.begin(),rest.end());
 
    for(int i = 0;i < n;i++){
        cout << rest[i].second << endl;
    }
 
    return 0;
}

### FIXED CODE ###

def main():
    N = int(input())
    A = []
    for i in range(N):
        S, P = input().split()
        A.append((S,int(P),i+1))
 
    sort_A = sorted(A, key=lambda x:(x[0], -x[1])) 
    for i in range(N):
        print(sort_A[i][2])
 
main()
n=int(input())
s=input()
if len(s)%2==1:
  print('No')
else:
  i=len(s)/2
  j=i//1
  if s[:j]+s[:j]==s:
    print('Yes')

### FIXED CODE ###

n=int(input())
s=input()
if len(s)%2==1:
  print('No')
else:
  i=len(s)//2
  if s[:i]+s[:i]==s:
    print('Yes')
  else :
    print('No')
want = input().int()
due = input().int()
start = input().int()
over = input().int()
e = want - due
yen = 0
if e <= 0:
    for i in range(want):
        yen += start

if e > 0:
    for i in range(due):
        yen += start
    for j in range(e):
        yen += over
print(yen)

### FIXED CODE ###

want = int(input())
due = int(input())
start = int(input())
over = int(input())
e = want - due
yen = 0
if e <= 0:
    for i in range(want):
        yen += start

if e > 0:
    for i in range(due):
        yen += start
    for j in range(e):
        yen += over
print(yen)
a, b, c, d, e, k = (int(i) for i in int(input()))
city = (d, c, b, a)
result = 'Yay!'
for i, c in enumerate(city):
    for cC in city.index(i + 1, city.count()):
        if (c - cC) > k:
            result = ':('
            break;
print(result)


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

city = [e,d, c, b, a]
result = 'Yay!'
for i, c in enumerate(city):
    for cC in city[i + 1:len(city)]:
        if (c - cC) > k:
            result = ':('
            break;
print(result)
a,b,c,d,e,d=map(int,input().split())
ans=[100*a,0]
for i in range(f//(100*a)+1):
  for j in range((f-100*a*i)//(100*b)+1):
    for k in range(f//c+1):
      if i==0 and j==0:
        break
      for l in range((f-c*k)//d+1):
        if 100*a*i+100*b*j+c*k+d*l>f:
          break
        elif c*k+d*l>(a*i+b*j)*e:
          break
        else:
          if (c*k+d*l)/(100*a*i+100*b*j+c*k+d*l)>ans[1]/ans[0]:
            ans=[100*a*i+100*b*j+c*k+d*l,c*k+d*l]
print(ans[0],ans[1])

### FIXED CODE ###

a,b,c,d,e,f=map(int,input().split())
ans=[100*min(a,b),0]
for i in range(31):
  for j in range(31):
    if i==0 and j==0:
      break
    l1=f-(100*a*i+100*b*j)
    l2=(a*i+b*j)*e
    l=min(l1,l2)
    cc,dc=0,0
    for k in range(l//c+1):
      tc=k
      td=(l-c*tc)//d
      if l-(c*tc+d*td)<l-(c*cc+d*dc):
        cc,dc=tc,td
    wa=100*a*i+100*b*j
    sa=c*cc+d*dc
    tmp=[wa+sa,sa]
    if wa+sa>f or sa>e*(a*i+b*j):
      break
    if tmp[1]/tmp[0]>ans[1]/ans[0]:
      ans=tmp
print(ans[0],ans[1])
N, K = map(int, input().split())
A = list(map(int, input().split()))

def f(X):
    return sum([X ^ a for a in A])

bin_K = '{:040b}'.format(K)
bin_A = ['{:040b}'.format(a) for a in A]
counter = [{'0': 0, '1': 0} for i in range(40)]
for ba in bin_A:
    for i in range(40):
        counter[i][ba[i]] += 1

cand = []
for i in range(40):
    if counter[i]['0'] <= counter[i]['1']:
        cand.append('0')
    else:
        cand.append('1')

i = 0
while bin_K[i] == '0':
    cand[i] = '0'
    i += 1

if int(''.join(cand), 2) >= K:
    print(f(K))
else:
    print(f(int(''.join(cand), 2)))

### FIXED CODE ###

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

def f(X):
    return sum([X ^ a for a in A])

bin_K = '{:040b}'.format(K)
bin_A = ['{:040b}'.format(a) for a in A]
counter = [{'0': 0, '1': 0} for i in range(40)]
for ba in bin_A:
    for i in range(40):
        counter[i][ba[i]] += 1

cand = []
for i in range(40):
    if counter[i]['0'] < counter[i]['1']:
        cand.append('0')
    else:
        cand.append('1')

i = 0
for i in range(40):
    if bin_K[i] == '1':
        break

bin_K = bin_K[i:]
cand = cand[i:]
counter = counter[i:]

candidate = [f(0), f(K)]
for i in range(len(cand)):
    if bin_K[i] == '1':
        tmp = cand[i:]
        tmp[0] = '0'
        candidate.append(f(int(bin_K[:i]+''.join(tmp), 2)))

print(max(candidate))
a,b,h=map(int, input().split())

N = int((a+b)*h/2)

print(N)


### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print((a+b)*h//2)
N, M, K = [int(x) for x in input().split()]

A_BOOK = list([int(x) for x in input().split()])
B_BOOK = list([int(x) for x in input().split()])


def read_book(read_time, book_count, a_remain, b_remain):

    if a_remain:
        a = a_remain[0]
    else:
        a = 10**9

    if b_remain:
        b = b_remain[0]
    else:
        b = 10*9

    a_count = book_count
    b_count = book_count

    if read_time + a < K:
        a_count = read_book(read_time + a, book_count +
                            1, a_remain[1:], b_remain)

    if read_time + b < K:
        b_count = read_book(read_time + b, book_count +
                            1, a_remain, b_remain[1:])

    if a_count > b_count:
        return a_count

    return b_count


count = read_book(0, 0, A_BOOK, B_BOOK)

print(count)


### FIXED CODE ###

from bisect import bisect_right
from time import time

N, M, K = [int(x) for x in input().split()]

a_book = [0]
for index, i in enumerate(input().split(), 1):
    if a_book[index-1] + int(i) <= K:
        a_book.append(a_book[index-1] + int(i))
    else:
        N = index - 1
        break

b_book = [0]
for index, i in enumerate(input().split(), 1):
    if b_book[index-1] + int(i) <= K:
        b_book.append(b_book[index-1] + int(i))
    else:
        M = index - 1
        break

check = {}

max_books = 0

for i, a in enumerate(a_book):
    b_pos = bisect_right(b_book, K - a)

    if max_books < b_pos - 1 + i:
        max_books = b_pos - 1 + i

print(max_books)
# coding: utf-8
import collections


def main():
    n = int(input())
    inputs = [input().split() for i in range(n)]
    inputs_list = []
    for i in inputs:
        if int(i[0]) - int(i[1]) < 0:
            inputs_list += (range(0, int(i[0]) + int(i[1])))
        else:
            inputs_list += (range(int(i[0]) - int(i[1]), int(i[0]) + int(i[1])))
    c = collections.Counter(inputs_list)
    print(n - (c.most_common()[0][1] - 1))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8
def main():
    n = int(input())
    inputs = [input().split() for i in range(n)]
    inputs_list = []
    for i in inputs:
        if int(i[0]) - int(i[1]) < 0:
            inputs_list.append([0, int(i[0]) + int(i[1])])
        else:
            inputs_list.append([int(i[0]) - int(i[1]), int(i[0]) + int(i[1])])
    sorted_data = sorted(inputs_list, key=lambda x: (x[1]))

    ans = [sorted_data[0]]
    cur = ans[0][1]
    for i in range(len(sorted_data) - 1):
        if cur <= sorted_data[i + 1][0]:
                ans.append(sorted_data[i + 1])
                cur = sorted_data[i + 1][1]
    print(len(ans))


if __name__ == '__main__':
    main()
n,m,*a=map(int,open(0).read().split())
b=[-1]*(n+1)
if m!=0:
    for i in a:
        b[i]=0
    if a[0]==1 and a[1]==2:
        continue
    elif a[0]==1:
        b[2]=1
    elif a[0]==2:
        b[1]=1
    else:    
        b[1],b[2]=1,2
else:    
        b[1],b[2]=1,2        
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])

### FIXED CODE ###

n,m,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
b=[-1]*(n+1)
a+=[0,0]
for i in a:
    b[i]=0
if a[0]==1 and a[1]==2:
    b[1],b[2]=0,0
elif a[0]==1:
    b[2]=1
elif a[0]==2:
    b[1]=1
else:    
    b[1],b[2]=1,2
for i in range(3,n+1):
    if b[i]==-1:
        b[i]=(b[i-1]+b[i-2])%1000000007
print(b[-1])
import sys

X, N = map(int, input().split())
if N == 0:
    print(X)
    sys.exit()
p = list(map(int, input().split()))

comp = 101
for i in range(100):
    i += 1    
    x = abs(X - i)
    if comp > x and i not in p:
        comp = x
        result = i

print(result)

### FIXED CODE ###

import sys

X, N = map(int, input().split())
p = list(map(int, input().split()))

if N == 0:
    print(X)
    sys.exit()

comp = 101
for i in range(102):
    x = abs(X - i)
    if comp > x and i not in p:
        comp = x
        result = i

print(result)
import bisect
import copy
import heapq
import sys
import itertools
import math
from functools import lru_cache
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, K = read_values()
    A = read_list()
    A.sort()
    res = 1    
    if N == K:
        for a in A:
            res *= a
            res %= mod
    elif A[-1] < 0:
        for a in A[:-(K + 1):-1]:
            res *= a
            res %= mod
    else:
        k = bisect.bisect_left(A, 0)
        neg = A[:k]
        pos = A[k:][::-1]
        
        n = 0
        p = 0
        while n + p < K:
            if -neg[n] <= pos[p]:
                p += 1
            else:
                n += 1
        if n % 2 == 1:
            if p == 0 or n == len(neg):
                n -= 1
                p += 1
            elif p == len(pos):
                n += 1
                p -= 1
            elif pos[p] * pos[p - 1]  <= neg[n] * neg[n - 1]:
                n += 1
                p -= 1
            else:
                n -= 1
                p += 1

        for a in pos[:p]:
            res *= a
            res %= mod
        
        for a in neg[:n]:
            res *= a
            res %= mod

    print(res % mod)

    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
import random
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


N, K = read_values()
def main():
    A = read_list()
    # A = [random.randint(-10 ** 9, 10 ** 9) for _ in range(N)]

    A.sort(reverse=True)
    if N == K or (A[0] < 0 and K % 2 == 1):
        res = 1
        for a in A[:K]:
            res *= a
            res %= mod
        print(res)
        return

    A.sort(key=lambda a: abs(a), reverse=True)

    P1 = list(filter(lambda a: a >= 0, A[:K]))
    P2 = list(filter(lambda a: a >= 0, A[K:]))
    N1 = list(filter(lambda a: a < 0, A[:K]))
    N2 = list(filter(lambda a: a < 0, A[K:]))

    if len(N1) % 2 == 1:
        # if N1[-1] * N2[0] : P1[-1] * P2[0]
        if len(P1) == 0 or len(N2) == 0:
            N1[-1] = P2[0]
        elif len(P2) == 0:
            P1[-1] = N2[0]
        else:
            if P1[-1] * P2[0] >= N1[-1] * N2[0]:
                N1[-1] = P2[0]
            else:
                P1[-1] = N2[0]
    
    res = 1
    for p in P1:
        res *= p
        res %= mod

    for n in N1:
        res *= n
        res %= mod
    
    print(res % mod)
        

if __name__ == "__main__":
    main()
A, B = map(long, raw_input().split())
ans = A
for i in range(A + 1, B + 1):
    ans = ans ^ i

print(ans)

### FIXED CODE ###

def xor(_x) :
    if _x % 4 == 0:
        return _x
    elif _x % 4 == 1:
        return 1
    elif _x % 4 == 2:
        return 1 ^ _x
    else:
        return 0


A, B = map(long, raw_input().split())
print(xor(A - 1) ^ xor(B))