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

def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for m  in range(M):
    P.append(list(map(int,input().split())))
    P_X[P[m][0]]+=1
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
m_count=0
for k in P:
    if  k[0] in max_X and k [1] in max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)

    



### FIXED CODE ###


def my_index(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

H,W,M=map(int,input().split())
P=list()
P_X=[0]*(H+1)
P_Y=[0]*(W+1)
for m  in range(M):
    P.append(list(map(int,input().split())))
    P_X[P[m][0]]+=1
    P_Y[P[m][1]]+=1
Max_X=max(P_X)
Max_Y=max(P_Y)
max_X=my_index(P_X,Max_X)
max_Y=my_index(P_Y,Max_Y)
m_count=0
for k in P:
    if  P_X[k[0]] == Max_X and P_Y[k [1]] == Max_Y:
        m_count += 1
if m_count==len(max_X)*len(max_Y):
    answer=Max_X+Max_Y-1
else:
     answer=Max_X+Max_Y
    
print(answer)
### BUGGY CODE ###

import math
N =int(input())
for i in range(N):
  count = 0
  M = int(math.sqrt(i+1))
  for j in range(M):
    for k in range(M):
      for l in range(M):
        if((j+1)**2 + (k+1)**2 + (l+1)**2 + (j+1)*(k+1) + (k+1)*(l+1) + (l+1)*(j+1) == i+1):
          count+=1
  print(count)

### FIXED CODE ###

import math
N = int(input())
ans_list = [0 for i in range(N)]
index = int(math.sqrt(N))

for x in range(1,index):
  for y in range(1,index):
    for z in range(1,index):
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x 
      if (n <= N):
        ans_list[n-1] += 1
for i in range(N):
  print(ans_list[i])
### BUGGY CODE ###

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

if N == 1:
    print(P)
    exit()

t = 1
pm = 2
while pm ** N <= P:
    e = 0
    while P % pm == 0:
        P //= pm
        e += 1 # 素数のカウント
    t *= pm ** (e // N)
    pm += 1

print(t)


### FIXED CODE ###

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

if N == 1:
    ans = P
else:
    ans = 1
    p = 2
    while p * p <= P:
        e = 0
        while P % p == 0:
            P //= p
            e += 1  # 素数のカウント
        if e // N > 0:
            ans *= p ** (e // N)
        p += 1

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

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')] * n
dp[0] = 0

for i in range(1, n):
    for j in range(max(i - k, 0), i):
        np = dp[j] + abs(h[i] - h[j])
        if np < dp[i]:
            dp[i] = np 

print(dp[n - 1])


### FIXED CODE ###

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

INF = 10 ** 18

h = H
dp = [0] * N

for n in range(1, N):
	l, r = max(0, n - K), n
	dp[n] = min([dpl + abs(hl - h[r]) for dpl, hl in zip(dp[l:r], h[l:r])])
	#print(dp)
print(dp[N - 1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split(' '))
count = 0
for i in range((N // R)+1):
    for j in range((N // G)+1):
        tmp = N - (R * i + G * j)
        if tmp < 0:
            break
        if tmp == 0:
            count += 1
        elif tmp % B == 0:
            count += 1
print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split(' '))
count = 0
for i in range((N // R)+1):
    for j in range((N // G)+1):
        tmp = N - (R * i + G * j)
        if tmp < 0:
            break
        if tmp == 0:
            count += 1
        elif tmp % B == 0:
            count += 1
print(count)
### BUGGY CODE ###

def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def make_divisors2(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    prime_list = prime(max(a))
    prime_count = dict()
    for value in prime_list:
        prime_count[value] = 0
    
    for i in range(n):
        value = a[i]
        divisors = make_divisors(value)
        for d in divisors:
            if d in prime_count:
                c, v = 0, value
                while v%d == 0:
                    c += 1
                    v //= d
                if prime_count[d] < c:
                    prime_count[d] = c
    
    ans = 0
    inf = pow(10, 9)+7
    
    for value in a:
        sub = 1
        for p in prime_list:
            k = prime_count[p]
            v = value
            while v%p == 0:
                v //= p
                k -= 1
            sub *= pow(p, k, inf)
            sub %= inf
        ans += sub
        ans %= inf
    
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import Counter

def prime_factorize(n):
    ans = []
    while not n%2:
        ans.append(2)
        n //= 2
    mod = 3
    while mod**2 <= n:
        if n%mod == 0:
            ans.append(mod)
            n //= mod
        else:
            mod += 2
    if n != 1:
        ans.append(n)
    counter = Counter(ans)
    return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    
    prime_list = dict()
    for i in range(n):
        primes = prime_factorize(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
    
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    
    print(ans)
            


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


n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
ans = 0
for i in range(n):
    x = a[i]
    a[i] = (x*(x+1))/2/x
for i in range(n-k+1):
    ans = max(ans,sum(a[i:i+k]))
print(ans)

### FIXED CODE ###


n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
r = [0 for _ in range(n+1)]
ans = 0
for i in range(1,n+1):
    x = a[i-1]
    r[i] = r[i-1] + (x*(x+1))/2/x #期待値
    if i+1 >=k:
        ans = max(ans,r[i]-r[i-k])
print(ans)
### BUGGY CODE ###

import glob
import numpy as np



# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\134\\D'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class D(Common):

    def resolve(self):

        box_num = int(self.input_data())
        remain = [int(i) for i in self.input_data().split()]

        boxes = np.zeros(box_num, dtype=np.int)
        for box in range(box_num, 0, -1):
            ball_num = np.sum(boxes[box-1::box])
            if ball_num % 2 != remain[box-1]:
                boxes[box-1] = 1

        print(str(np.sum(boxes)))
        for i in range(box_num):
            if boxes[i] == 1:
                print(str(i+1), end=" ")


solver = D(REL_PATH)
solver.exec_resolve()


### FIXED CODE ###

import glob
import numpy as np


# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\134\\D'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class D(Common):

    def resolve(self):

        box_num = int(self.input_data())
        remain = [int(i) for i in self.input_data().split()]

        boxes = [0 for i in range(box_num)]
        ball_num = 0

        for box in range(box_num, 0, -1):
            ball_num = 0
            for j in range(box-1, box_num, box):
                ball_num += boxes[j]
            if ball_num % 2 != remain[box-1]:
                boxes[box-1] = 1
                ball_num += 1

        print(str(ball_num))
        for i in range(box_num):
            if boxes[i] == 1:
                print(str(i+1), end=" ")


solver = D(REL_PATH)
solver.exec_resolve()
### BUGGY CODE ###

N= int(input())
A = list(map(int, input().split()))
C=0
for i in range(N):
    k=int(A.count(i+1))
    C += k * (k - 1) // 2
for i in range(N):
    print(int(C-(A.count(A[i]))+1))

### FIXED CODE ###

import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))
### BUGGY CODE ###

n = int(input())
d = {}

for _ in range(n):
  s = input()
  d[s] = d.get(s, 0) + 1 


max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()

for i in max_k_list:
  print(i)


### FIXED CODE ###

n = int(input())
d = {}

for _ in range(n):
  s = input()
  d[s] = d.get(s, 0) + 1 

n = max(d.values())
max_k_list = [kv[0] for kv in d.items() if kv[1] == n]
max_k_list.sort()

for i in max_k_list:
  print(i)
### BUGGY CODE ###

import heapq
N,Q=map(int,input().split())

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
hq=[]
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    heapq.heappush(hq,x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      while(True):
        if hq[0] in stop_set:
          answer_dic[t]=hq[0]
          break
        else:
          heapq.heappop(hq)
    else:
      answer_dic[t]=-1
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])


### FIXED CODE ###

import heapq
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
min_set=float("inf")
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    if x<min_set:
      min_set=x
  elif f==-1:
    stop_set.remove(x)
    if x==min_set:
      if len(stop_set)>0:
        min_set=min(stop_set)
      else:
        min_set=float("inf")
  else:
    if len(stop_set)>0:
      answer_dic[t]=min_set
    else:
      answer_dic[t]=-1
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])
### BUGGY CODE ###

import queue
H,W=map(int,input().split())

board=[list(input()) for _ in range(H)]
checked=[[-1 for _ in range(W)] for _ in range(H)]
dh=[1,0,-1,0]
dw=[0,-1,0,1]
ans=0

q=queue.Queue()

for i in range(H):
    for j in range(W):
        if board[i][j]=='#':
            checked[i][j]=0
            q.put([i,j])


while not q.empty():
    tmp=q.get()
    h,w=tmp[0],tmp[1]
    for i in range(4):
        th=h+dh[i]
        tw=w+dw[i]
        if 0<=th<H and 0<=tw<W and checked[th][tw]==-1:
            checked[th][tw]=checked[h][w]+1
            q.put([th,tw])
            ans=max(ans,checked[th][tw])
print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

q=[]
for h in range(1,H+1):
    for w in range(1,W+1):
        if board[h][w]:
            q.append((h,w))

cnt=0
while q:
    nq=[]
    for h,w in q:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append((h+1,w))
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append((h-1,w))
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append((h,w+1))
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append((h,w-1))

    q=nq
    cnt+=1

print(cnt-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n,k = map(int, input().split())
    A = list(map(int, input().split()))
    
    score = 1
    for a in A[:k]:
        score*=a
    
    for i in range(k,n):
        tmp_score = score//A[i-k] * A[i]
        if tmp_score > score:
            print("Yes")
        else:
            print('No')
        score = tmp_score
main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n,k = map(int, input().split())
    A = list(map(int, input().split()))
    
    for i in range(k,n):
        if A[i] > A[i-k]:
            print('Yes')
        else:
            print('No')
main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""

def cost(i,j):
    return abs(h[i]-h[j])

N,K=map(int,input().split())
h=[int(num) for num in input().split()]

dp=[0]*N
   
for i in range(1,N):
    mi=cost(i,i-1)+dp[i-1]
    for j in range(max(0, i-K), i-1):
        mi=min(cost(i,j)+dp[j],mi)
    dp[i]=mi
    
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""



N,K=map(int,input().split())
h=[int(num) for num in input().split()]

dp=[0]*N
dp[1]=abs(h[0]-h[1])
   
def cost(h,N,K,dp):
    for i in range(2,N):
        dp[i]=min([abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i)])
    return dp[-1]
    
print(cost(h,N,K,dp))
### BUGGY CODE ###

s = input()
t = input()

u = ""
while len(u) < len(s) + len(t):
    u = u + s

t_add = t + "."


def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = word[i] == word[j]

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table


table_tx = partial_match_table(t_add)

match = [0] * len(s)

i = j = 0
while i < len(u) and j < len(t_add):
    if u[i] == t_add[j]:
        i += 1
        j += 1
    elif j == 0:
        i += 1
    else:
        j = table_tx[j]
    if j == len(t_add) - 1:
        match[(i - j) % len(s)] = 1


# search
searched = [0] * len(s)
longest = 0
infinity = False
for i in range(len(s)):
    if searched[i]:
        continue
    searched[i] = 1
    p = i
    right = 0
    while match[p]:
        right += 1
        p = (p + len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    left = 0
    p = i
    while match[(p - len(t)) % len(s)]:
        left += 1
        p = (p - len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    if left + right > longest:
        longest = left + right

if infinity:
    print(-1)
else:
    print(longest)


### FIXED CODE ###

s = input()
t = input()

u = s * (len(t) // len(s) + 2)

t_add = t + "."


def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = word[i] == word[j]

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table


table_tx = partial_match_table(t_add)

match = [0] * len(s)

i = j = 0
while i < len(u) and j < len(t_add):
    if u[i] == t_add[j]:
        i += 1
        j += 1
    elif j == 0:
        i += 1
    else:
        j = table_tx[j]
    if j == len(t_add) - 1:
        match[(i - j) % len(s)] = 1


# search
searched = [0] * len(s)
longest = 0
infinity = False
for i in range(len(s)):
    if searched[i]:
        continue
    searched[i] = 1
    p = i
    right = 0
    while match[p]:
        right += 1
        p = (p + len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    left = 0
    p = i
    while match[(p - len(t)) % len(s)]:
        left += 1
        p = (p - len(t)) % len(s)
        searched[p] = 1
        if p == i:
            infinity = True
            break
    if left + right > longest:
        longest = left + right

if infinity:
    print(-1)
else:
    print(longest)
### BUGGY CODE ###

a = [str(i) for i in input()]

for bit in range(2 ** (len(a)+1)):
	s = a.copy()

	for i in range(0,len(a)+1):
		if (bit >> i) & 1:
			s.insert(i*2, "A")
			
	if "".join(s) == "AKIHABARA":
		print("YES")
		exit()

print("NO")

	

### FIXED CODE ###

a = [str(i) for i in input()]

if len(a) > 10:
	print("NO")
	exit()

for bit in range(2 ** (len(a)+1)):
	s = a.copy()

	for i in range(0,len(a)+1):
		if (bit >> i) & 1:
			s.insert(i*2, "A")
			
	if "".join(s) == "AKIHABARA":
		print("YES")
		exit()

print("NO")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N,M = [int(i) for i in readline().split()]
H = [int(i) for i in readline().split()]
AB = [[int(i) for i in readline().split()] for _ in range(M)]

ng = []

for a,b in AB:
  if a not in ng:
    if H[a-1] <= H[b-1]:
      ng.append(a)
  if b not in ng:
    if H[b-1] <= H[a-1]:
      ng.append(b)

print(N-len(ng))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N,M = [int(i) for i in readline().split()]
#H = [int(i) for i in readline().split()]
#AB = [[int(i) for i in readline().split()] for _ in range(M)]
H = {i+1:int(e) for i,e in enumerate(readline().split())}
AB = [[int(i) for i in readline().split()] for _ in range(M)]

ng = []

for a,b in AB:
  if H[a] < H[b]:
    ng += [a]
  elif H[a] > H[b]:
    ng += [b]
  else:
    ng += [a,b]
#print(ng)
print(N-len(set(ng)))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
for i in range(0, N):
    p_i = P[i]
    for j in range(0, i):
        if p_i > P[j]:
            break
    else:
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
leftmin = P[0]
for i in range(0, N):
    if leftmin >= P[i]:
        count += 1

    if leftmin > P[i]:
        leftmin= P[i]

print(count)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(sorted(A,key=lambda x: abs(x), reverse=True))

if K == N:
    ans = 1
    for a in A:
        ans *= a
        ans %= MOD
    print(ans % MOD)
    exit()
if K % 2 == 1 and len(list(filter(lambda x: x >= 0, A))) == 0:
    ans = 1
    for i in range(K):
        ans *= B[len(B) - 1 - i]
        ans %= MOD
    print(ans % MOD)
    exit()


ps = list(filter(lambda x: x >= 0, B))
ns = list(filter(lambda x: x < 0, B))

X = []
pi = 0
ni = 0
while len(X) < K:
    if pi + 1 < len(ps) and ni + 1 < len(ns):
        p = ps[pi] * ps[pi + 1]
        neg = ns[ni] * ns[ni + 1]
        if p > neg or K - 1 == len(X):
            X.append(ps[pi])
            pi += 1
        else:
            X.append(ns[ni])
            X.append(ns[ni + 1])
            ni += 2
    elif pi + 1 == len(ps):
        X.append(ps[pi])
        pi += 1
ans = 1
for x in X:
    ans *= x
    ans %= MOD
print(ans % MOD)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

S = []
T = []
for a in A:
    if a < 0:
        T.append(a)
    else:
        S.append(a)

ls = len(S)
lt = len(T)
ok = False

if ls > 0:
    if N == K:
        ok = lt % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    A = sorted(A, key=lambda x: abs(x))
    for a in A[:K]:
        ans *= a
        ans %= MOD
else:
    S = sorted(S)
    T = sorted(T, reverse=True)
    if K % 2 == 1: # if K is odd, the answer has at least one positive number.
        ans *= S.pop()
        ans %= MOD
    p = []
    # the num of negatives must be even, so positives must do the same
    # thus, we can pop 2 items at one time.
    while len(S) >= 2:
        x = S.pop()  
        y = S.pop()
        p.append(x * y)
    while len(T) >= 2:
        x = T.pop()  
        y = T.pop()
        p.append(x * y)
    p = sorted(p, reverse=True)
    for i in range(K // 2):
        ans *= p[i]
        ans %= MOD
print(ans % MOD)