Harryxun/stf_run huggingface dataset:
class node:
    def __init__(self, num):
        self.number     = num
        self.distance   = -1
        self.link_node  = []
        self.is_serched = False

class queue:
    def __init__(self):
        self.top = 0
        self.bottom = 0
        self.que = [None] * 1000
    
    def dequeue(self):
        self.top = self.top + 1
        return self.que[self.top - 1]
    
    def enqueue(self, item):
        self.que[self.bottom] = item
        self.bottom = self.bottom + 1
    
    def is_empty(self):
        if self.top == self.bottom:
            return True
        else:
            return False

n = input()
node_list = [None] * (n + 1)

for i in xrange(1, n + 1):
    node_list[i] = node(i)

for i in xrange(1, n + 1):
    line = raw_input().split()
    for node_num in line[2 : ]:
        node_list[i].link_node.append(node_list[int(node_num)])

node_que = queue()

node_list[1].distance = 0
node_que.enqueue(node_list[1])
while node_que.is_empty() == False:
    top_item = node_que.que[node_que.top]
    top_item.is_serched = True
    for item in top_item.link_node:
        if item.is_serched == False:
            node_que.enqueue(item)
            if item.distance == -1:
                item.distance = top_item.distance + 1
            elif item.distance > top_item.distance + 1:
                item.distance = top_item.distance + 1
    node_que.dequeue()

for item in node_list[1 : ]:
    print '%s %s' % (str(item.number), str(item.distance))
    

### FIXED CODE ###

class node:
    def __init__(self, num):
        self.number     = num
        self.distance   = -1
        self.link_node  = []
        self.is_serched = False

class queue:
    def __init__(self):
        self.top = 0
        self.bottom = 0
        self.que = []
    
    def dequeue(self):
        self.top = self.top + 1
        return self.que[self.top - 1]
    
    def enqueue(self, item):
        self.que.append(item)
        self.bottom = self.bottom + 1
    
    def is_empty(self):
        if self.top == self.bottom:
            return True
        else:
            return False

n = input()
node_list = [None] * (n + 1)

for i in xrange(1, n + 1):
    node_list[i] = node(i)

for i in xrange(1, n + 1):
    line = raw_input().split()
    for node_num in line[2 : ]:
        node_list[i].link_node.append(node_list[int(node_num)])

node_que = queue()

node_list[1].distance = 0
node_que.enqueue(node_list[1])
while node_que.is_empty() == False:
    top_item = node_que.que[node_que.top]
    top_item.is_serched = True
    for item in top_item.link_node:
        if item.is_serched == False:
            node_que.enqueue(item)
            if item.distance == -1:
                item.distance = top_item.distance + 1
            elif item.distance > top_item.distance + 1:
                item.distance = top_item.distance + 1
    node_que.dequeue()

for item in node_list[1 : ]:
    print '%s %s' % (str(item.number), str(item.distance))
a,b = map(int,input().split())

if a > b:
  print("GREATER")
elif a == b:
  print("EQUAL")
else:
  print("LESS")

### FIXED CODE ###

a = int(input())
b = int(input())

if a > b:
  print("GREATER")
elif a == b:
  print("EQUAL")
else:
  print("LESS")
s = input()
k = int(input())

i = 0

while s[i] == '1' and i < k:
  i += 1

print(int(s[i]))

### FIXED CODE ###

s = list(map(int,list(input())))
k = int(input())

a = 0
i = 0

while a < k:
  a += min(s[i]**70, k)
  i +=1

print(s[i-1])
def dp(v):# 頂点nから始まる最長経路を返す.
  if memo[v] != -1: return memo[v]
  to_list = Graph[v]
  answ = 0

  for i in to_list:
    answ = max(answ, dp(i)+1)
  memo[v] = answ
  return answ


N, M = map(int, input().split())
Graph = {j+1:[] for j in range(N)}
memo = [-1] * (N+1) # 各頂点からの最長経路をメモ. -1で初期化.

for _ in range(M):
  x, y = map(int, input().split())
  Graph[x].append(y)

ans = 0
for n in range(1,N+1):
  ans = max(ans, dp(n))
print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
MEMO = [-1 for _ in range(N+1)]

for _ in range(M):
  x, y = map(int, input().split())
  G[x].append(y)


def dp_LP(v):# 頂点nから始まる最長経路を返す.
  if MEMO[v] != -1:
    return MEMO[v]
  else:
    ans = 0
    for i in G[v]:
      ans = max(ans, dp_LP(i)+1)
    MEMO[v] = ans

    return ans



answer = 0
for n in range(1,N+1):
  answer = max(answer, dp_LP(n))
print(answer)
from itertools import product

h, w, k = map(int, input().split())
c = [list(input().split()) for _ in range(h)]

print(c)
ans = 0

for row_bit in product(range(2), repeat=h):
    for col_bit in product(range(2), repeat=w):
        cnt = 0
        for row in range(h):
            for col in range(w):
                if (c[row][col] == '#') and ((row_bit[row] == 0) and (col_bit[col] == 0)):
                    cnt += 1   
        if cnt == k:
            print(row_bit, col_bit)
            ans += 1
print(ans)

### FIXED CODE ###

from itertools import product

h, w, k = map(int, input().split())
c = [input() for _ in range(h)]

ans = 0

for row_bit in product(range(2), repeat=h):
    for col_bit in product(range(2), repeat=w):
        cnt = 0
        for row in range(h):
            for col in range(w):
                if (c[row][col] == '#') and ((row_bit[row] == 0) and (col_bit[col] == 0)):
                    cnt += 1   
        if cnt == k:
            ans += 1
print(ans)
rint('vowel') if input() in 'aeiouAEIOU' else print('consonant')

### FIXED CODE ###

print('vowel') if input() in 'aeiou' else print('consonant')
def dfs(i):
    if all([v != -1 for v in visited]):
        return
    color = visited[i]
    for nextIdx, wgt in graph[i]:
        if visited[nextIdx] == -1:
            if wgt % 2 == 0:
                visited[nextIdx] = color
            else:
                visited[nextIdx] = int(not color)
            dfs(nextIdx)

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

visited = [-1] * n
visited[0] = 0
dfs(0)
for v in visited:
    print(v)


### FIXED CODE ###

import sys
sys.setrecursionlimit(20000000)

def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance + edge_size) % 2)
            dfs(next_node, distance + edge_size)

N = int(input())

G = [[] for i in range(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])

ans = [-1] * N
dfs(0, 0)
print(*ans, sep='\n')
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

a, b = input().split()
n = int(a+b)
ans = "No"
i = 0
while i*i <= n:
    if n % (i*i) == 0:
        ans = "Yes"
print(ans)


### FIXED CODE ###

from math import sqrt
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

a, b = input().split()
n = int(a+b)
if int(sqrt(n)) == sqrt(n):
    print("Yes")
else:
    print("No")
# 入力
n = int(input())
loc_list = []
for _ in range(n):
  loc_list.append(list(map(int, input().split())))

# 処理
ans = True
prev_loc = [0, 0, 0]
for loc in loc_list:
  # 現在の位置から次の位置へ移動可能かどうかを判定
  if not movable(prev_loc, loc):
    ans = False
    break
  prev_loc = loc

if ans:
  print("Yes")
else:
  print("No")
  
# 動けるかどうかの判定
def movable(prev_loc, loc):
  dt = loc[0] - prev_loc[0]
  dx = abs(loc[1] - prev_loc[1])
  dy = abs(loc[2] - prev_loc[2])
  # 時間内に届かない
  if dx + dy > dt:
    return False
  if dx + dy % 2 == dt % 2:
    return True
  else:
    return False
  
  

### FIXED CODE ###

# 動けるかどうかの判定
def movable(prev_loc, loc):
  dt = loc[0] - prev_loc[0]
  dx = abs(loc[1] - prev_loc[1])
  dy = abs(loc[2] - prev_loc[2])
  # 時間内に届かない
  if dx + dy > dt:
    return False
  if (dx + dy) % 2 == dt % 2:
    return True
  else:
    return False

# 入力
n = int(input())
loc_list = []
for _ in range(n):
  loc_list.append(list(map(int, input().split())))

# 処理
ans = True
prev_loc = [0, 0, 0]
for loc in loc_list:
  # 現在の位置から次の位置へ移動可能かどうかを判定
  if not movable(prev_loc, loc):
    ans = False
    break
  prev_loc = loc

if ans:
  print("Yes")
else:
  print("No")
k, a, b = map(int, input().split())
if b-a <= 1:
    ans = k+1
else:
    if k-1 >= a:
        r = k-a+1
        if r%2 == 0:
            ans = a+(b-a)*(r//2)
        else:
            ans = a+(b-a)*((r-1)//2)+1
print(ans)

### FIXED CODE ###

k, a, b = map(int, input().split())
if b-a <= 1:
    ans = k+1
else:
    if k-1 >= a:
        r = k-a+1
        if r%2 == 0:
            ans = a+(b-a)*(r//2)
        else:
            ans = a+(b-a)*((r-1)//2)+1
    else:
        ans = k+1
print(ans)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = input()
for i in range(N):
	S = raw_input()
	if S[:1] == "M":
		m += 1
	elif S[:1] == "A":
		a += 1
	elif S[:1] == "R":
		r += 1
	elif S[:1] == "C":
		c += 1
	elif S[:1] == "H":
		h += 1
print m*a*r+m*a*c+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h	

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = input()
m = 0
a = 0
r = 0
c = 0
h = 0
for i in range(N):
	S = raw_input()
	if S[:1] == "M":
		m += 1
	elif S[:1] == "A":
		a += 1
	elif S[:1] == "R":
		r += 1
	elif S[:1] == "C":
		c += 1
	elif S[:1] == "H":
		h += 1
print m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h
n,m=map(int,input().split())
li = [list(map(int, input().split())) for i in range(m)]

a=li[0][0]
b=li[0][1]
for i in range(m-1):
  if li[i+1][0]>a:
    a=li[i+1][0]
  if li[i+1][1]<b:
    b=li[i+1][1]

if b<a:
  print(int(0))
  break
  
if b-a+1<n:
  print(b-a+1)
else:
  print(n)

### FIXED CODE ###

n,m=map(int,input().split())
li = [list(map(int, input().split())) for i in range(m)]
 
a=li[0][0]
b=li[0][1]
for i in range(m-1):
  if li[i+1][0]>a:
    a=li[i+1][0]
  if li[i+1][1]<b:
    b=li[i+1][1]
 
if b<a:
  print(int(0))
  exit()
  
if b-a+1<n:
  print(b-a+1)
else:
  print(n)
nums = [n for n in input()]
ope = ["+", "-"]
for b in range(2 ** 3):
    temp = nums[0]
    for i in range(3):
        temp += f"{ope[b & (1 << i)]}{nums[i + 1]}"
    if eval(temp) == 7:
        print(temp+"=7")
        break

### FIXED CODE ###

target = input()
length = len(target)
binary = length - 1
target_list = []
for i in range(length):
    if i:
        target_list.append("")
    target_list.append(target[i])
for bit in range(binary ** 2):
    temp = target_list.copy()
    for i in range(binary):
        if bit & (1 << i):
            temp[1 + 2 * i] = "+"
        else:
            temp[1 + 2 * i] = "-"
    temp = "".join(temp)
    if eval(temp) == 7:
        print(temp + "=7")
        break
N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
MOD = 10**9+7

es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def npr(n,r):
    if n<r: return 0
    return fac[n] * finv[n-r]


ans = K
stack = [(0,0)]
visited = [0]*N
while stack:
    v,d = stack.pop()
    visited[v] = 1
    c = 0
    for to in es[v]:
        if visited[to]: continue
        c += 1
        stack.append((to,d+1))
    if c==0: continue
    m = npr(K-1,c) if d==0 else npr(K-2,c)
    ans *= m
    ans %= MOD
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7

fac = [1,1] + [0]*K
finv = [1,1] + [0]*K
inv = [0,1] + [0]*K
for i in range(2,K+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def npr(n,r):
    if n<r: return 0
    return fac[n] * finv[n-r]

ans = K * npr(K-1,len(es[0]))
ans %= MOD

visited = [0]*N
visited[0] = 1
stack = []
for v in es[0]:
    stack.append(v)

while stack:
    v = stack.pop()
    visited[v] = 1
    ans *= npr(K-2, len(es[v])-1)
    ans %= MOD
    for to in es[v]:
        if visited[to]: continue
        stack.append(to)
print(ans%MOD)
s, t = map(input().split())
a, b = map(int, input().split())
u = input()
print(a-1,b if s==u else a,b-1)

### FIXED CODE ###

s, t = input().split()
a, b = map(int, input().split())
u = input()
if s==u:
    print(a-1,b)
else:
    print(a,b-1)
l=list(map(int,input().split()) 
dd=[]                                                                  
for i in l: 
	if i % 2==0: 
		dd.append(i)       
cnt_lst=[]                                                             
for i in dd: 
	cnt1=0 
	while(i % 2==0): 
		i//= 2 
		cnt1+=1 
		if i %2==1: 
			cnt=cnt1 
			cnt_lst.append(cnt)             
			break 
print(sum(cnt_lst)) 

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
dd=[]                                                                  
for i in l: 
	if i % 2==0:
		dd.append(i)       
cnt_lst=[]                                                             
for i in dd: 
	cnt1=0 
	while(i % 2==0): 
		i//= 2 
		cnt1+=1 
		if i %2==1: 
			cnt=cnt1 
			cnt_lst.append(cnt)             
			break 
print(sum(cnt_lst))
"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

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

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))


### FIXED CODE ###


"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

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

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))
A,B,C = [int(x) for x in input().split()]

if ( a < c <b or b< c A):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

if a < c < b or b < c < a:
    print("Yes")
else:
    print("No")
n=int(input())

zahyo=[]

for _ in range(n):
    zahyo.append(tuple(map(int,input().split())))

zahyo.sort(key=lamda x:x[2])

for x in range(101):
    for y in range(101):


        H=zahyo[0][2]+abs(zahyo[0][0]-x)+abs(zahyo[0][1]-y)
        flag=0
        saisho=10**9+1
        H=0
        for item in zahyo[1:]:
                if item[2]==0:
                    if H>abs(item[0]-x)+abs(item[1]-y):
                        flag=1
                        break
                else:
                    if H!=item[2]+abs(item[0]-x)+abs(item[1]-y):
                        flag=1
                        break
        if flag==0:
            print(x,y,H)


            




### FIXED CODE ###

n=int(input())

hxy=[]
for _ in range(n):
    x,y,h=map(int,input().split())
    hxy.append([h,x,y])

hxy.sort()

for cx in range(101):
    for cy in range(101):
        flag=0
        temp=hxy[-1]
        H=temp[0]+abs(temp[1]-cx)+abs(temp[2]-cy)

        for item in hxy:
            h=item[0]
            x=item[1]
            y=item[2]
            if h!=max(H-abs(x-cx)-abs(y-cy),0):
                flag=1
                break
        
        if flag==0:
            print(cx,cy,H)
            exit()
N = int(input())
K = int(input())
X = [int(x) for x in input().split()]

total = sum([min(2*x, (K-x)*2) for x in X]
print(total)

### FIXED CODE ###

N = int(input())
K = int(input())
X = [int(x) for x in input().split()]
 
total = sum([min(2*x, (K-x)*2) for x in X])
print(total)
n,m=map(int,input().split())
num=0
array=[99999 for i in range(n)]
for _ in range(m):
  s,c = map(int,input().split())
  if array[s-1]==99999 or array[s-1]==c:
    array[s-1]=c
  else:
    array=[-1 for i in range(n)]
    break

if not n==1:
  for i in range(n):
    if not i==0:
      if array[i]==99999:
        array[i]=0
    else:
      array[i]=1
  if array[0]==0 or array[0]==-1:
    num=-1
  else:
    num=int(''.join(list(map(str,array))))
else:
  if array[0]==99999:
    num=-1
  else:
    num=array[0]
print(num)
    
    


### FIXED CODE ###

n,m=map(int,input().split())
num=0
array=[99999 for i in range(n)]
for _ in range(m):
  s,c = map(int,input().split())
  if array[s-1]==99999 or array[s-1]==c:
    array[s-1]=c
  else:
    array=[-1 for i in range(n)]
    break

if not n==1:
  for i in range(n):
    if not i==0:
      if array[i]==99999:
        array[i]=0
    else:
      if array[i]==99999:
        array[i]=1
  if array[0]==-1 or array[0]==0:
    num=-1
  else:
    num=int(''.join(list(map(str,array))))
else:
  if array[0]==99999:
    num=0
  else:
    num=array[0]
print(num)
use std::io::stdin;
use std::collections::HashMap;

fn main() {
    let mut st = String::new();
    stdin().read_line(&mut st).unwrap();
    let n = st.trim().parse::<usize>().unwrap();
    let mut st = String::new();
    stdin().read_line(&mut st).unwrap();
    let s:Vec<char> = st.trim().chars().collect();
    let mut map:HashMap<&char, i64> = HashMap::new();
    for i in &s {
        let count = map.entry(i).or_insert(1);
        *count += 1;
    };
    let mo = 100000007;
    let mut result:i64 = 1;
    for (_i, j) in map.iter() {
        result = (result*j)%mo;
    };
    println!("{}", result-1);
}


fn bisec(v:&Vec<i64>, num:&i64) -> usize {
    let mut l:usize = 0;
    let mut r = v.len() as usize;
    let mut m = (l+r)/2 as usize;
    while l < r {
        if num <= &v[m] {
            r = m;
        } else {
            l = m+1;
        };
        m = (l+r)/2;
    };
    l
}

fn max (a:&i64, b:&i64) -> i64 {
    if a < b {
        *b
    } else {
        *a
    }
}

fn min (a:&i64, b:&i64) -> i64 {
    if a > b {
        *b
    } else {
        *a
    }
}

### FIXED CODE ###

mod = 10**9+7
n = int(input())
s = input()
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
result = 1
for i, j in d.items():
    result = (result*(j+1))%mod

print((result-1)%mod)
n, k, m = map(int, input().split())
a = list(map(int, input().split()))
count = 0
total_score = 0
while count <= n - 2:
  total_score += a[count]
  count += 1 
last_score = n * m - total_score
if last_score < 0:
  print(0) 
else:
  print(last_score)

### FIXED CODE ###

c = input()
alp = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
count1 = 0
count2 = 0
while count2 <= 26:
  if alp[count1] == c:
     count1 += 1
     count2 += 27
  else:
    count1 += 1
    count2 += 1
print(alp[count1])
a = input()
b = input()
print(int(a-1)*int(b-1))

### FIXED CODE ###

a, b = (int(i) for i in input().split()) 
print((a-1)*(b-1))
a = int(input());b = int(input())
ans = [1, 2, 3].delete(a).delete(b)
print(ans[0])

### FIXED CODE ###

a = int(input()); b=int(input())
ans = [1, 2, 3]
ans.remove(a)
ans.remove(b)
print(ans[0])
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = list( map(int, input().split()))
p = 10**9+7

a.sort()

from bisect import bisect_left, bisect_right
zerostart = bisect_left(a, 0)
posstart = bisect_right(a, 0)

aneg = a[:zerostart]
cntzero = posstart - zerostart
apos = a[posstart:]

cntneg = len(aneg)
cntpos = len(apos)

# 答えが0になる時
if k > n-cntzero:
    print(0)
    exit()

# 答えが正になる時
if k <= cntpos or (k%2==0 and  k <= (cntneg//2)*2 + cntpos) or (k%2==1 and cntpos%2==1 and k <= (cntneg//2)*2 + cntpos-1):
    pos_pair_mix=[]

    apos.sort(reverse=True)
    for i in range(cntpos//2):
        pos_pair_mix.append((apos[2*i]*apos[2*i+1],+1,2*i))

    for i in range(cntneg//2):
        pos_pair_mix.append((aneg[2*i]*aneg[2*i+1],-1,2*i))

    pos_pair_mix.sort(key=lambda x:x[0],reverse=True)

    ans = 1
    last_apos=0

    for i in range(k//2):
        ans*=pos_pair_mix[i][0]%p
        ans%=p
        if pos_pair_mix[i][1]==1:
            i_last_apos = pos_pair_mix[i][2]+2

    if k%2==0:
        print(ans%p)
        exit()
    else:
        print((ans*apos[i_last_apos])%p)
        exit()

# 答えが負になる時
a.sort(key=lambda x:abs(x) )

ans = 1
for i in range(k):
    ans*=a[i]
    ans%=p

print(ans%p)


### FIXED CODE ###


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

n, k = map(int, input().split())
a = list( map(int, input().split()))
p = 10**9+7

a.sort()

from bisect import bisect_left, bisect_right
zerostart = bisect_left(a, 0)
posstart = bisect_right(a, 0)

aneg = a[:zerostart]
cntzero = posstart - zerostart
apos = a[posstart:]

cntneg = len(aneg)
cntpos = len(apos)

# 答えが0になる時
if k > n-cntzero:
    print(0)
    exit()

# 答えが正になる時
if k <= cntpos or (k%2==0 and  k <= (cntneg//2)*2 + cntpos) or (k%2==1 and cntpos%2==1 and k <= (cntneg//2)*2 + cntpos-1):
    pos_pair_mix=[]

    apos.sort(reverse=True)
    for i in range(cntpos//2):
        pos_pair_mix.append((apos[2*i]*apos[2*i+1],+1,2*i))

    for i in range(cntneg//2):
        pos_pair_mix.append((aneg[2*i]*aneg[2*i+1],-1,2*i))

    pos_pair_mix.sort(key=lambda x:x[0],reverse=True)

    ans = 1
    i_last_apos=0

    for i in range(k//2):
        ans*=pos_pair_mix[i][0]%p
        ans%=p
        if pos_pair_mix[i][1]==1:
            i_last_apos = pos_pair_mix[i][2]+2

    if k%2==0:
        print(ans%p)
        exit()
    else:
        print((ans*apos[i_last_apos])%p)
        exit()

# 答えが負になる時
a.sort(key=lambda x:abs(x) )

ans = 1
for i in range(k):
    ans*=a[i]
    ans%=p

print(ans%p)
from bisect import bisect_left
n, l, t = map(int, input().split())
ants = [list(map(int, input().split())) for _ in range(n)]
bnts = []
diff = []

for i in range(n):
	x, w = ants[i][0], 3 - 2*ants[i][1]
	bnts.append((x + t*w) % l)
	if i == 0:
		zero = bnts[-1]
	if ants[i][1] != ants[0][1]:
		if ants[0][1] == 1:
			diff.append(x - ants[0][0])
		else:
			diff.append(l - (x - ants[0][0]))

bnts.sort()
num = 0
quo, mod = t//l, t%l
num += quo * len(diff) * 2
diff.sort()
diff += [d+l for d in diff]
num += bisect_left(diff, mod*2)
num %= n
for i in range(n):
	if bnts[i] == zero:
		if ants[0][1] == 1:
			true_zero = (i-num) % n
		else:
			if bnts[i+1] == zero:
				num += 1
			true_zero = (i+num) % n

ans = bnts[true_zero:] + bnts[:true_zero]
print(*ans, sep="\n")

### FIXED CODE ###

from bisect import bisect_left, bisect
n, l, t = map(int, input().split())
ants = [list(map(int, input().split())) for _ in range(n)]
bnts = []
diff = []

for i in range(n):
	x, w = ants[i][0], 3 - 2*ants[i][1]
	bnts.append((x + t*w) % l)
	if i == 0:
		zero = bnts[-1]
	if ants[i][1] != ants[0][1]:
		if ants[0][1] == 1:
			diff.append(x - ants[0][0])
		else:
			diff.append(l - (x - ants[0][0]))

bnts.sort()
num = 0
quo, mod = t//l, t%l
num += quo * len(diff) * 2
diff.sort()
diff += [d+l for d in diff]
#num += bisect_left(diff, mod*2)
num += bisect(diff, mod*2)
num %= n
for i in range(n):
	if bnts[i] == zero:
		if ants[0][1] == 1:
			true_zero = (i-num) % n
		else:
			if i < n-1:
				if bnts[i+1] == zero:
					#pass
					num -= 1
			true_zero = (i+num) % n

ans = bnts[true_zero:] + bnts[:true_zero]
print(*ans, sep="\n")