Harryxun/stf_run huggingface dataset:
from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")

### FIXED CODE ###

from math import gcd
import numpy as np

def setwise_coprime_check_fun(A_list, N):
    gcd_all = A_list[0]
    for i in range(N - 1):
        gcd_all = gcd(gcd_all, A_list[i + 1])
        if gcd_all == 1:
            break
    return gcd_all

def preprocess_fun(A_max):
    p_flg = [True] * (A_max + 1)
    D = [0] * (A_max + 1)
    p_flg[0] = False
    p_flg[1] = False
    for i in range(2, A_max + 1, 1):
        if p_flg[i]:
            for j in range(i, A_max + 1, i):
                p_flg[j] = False
                D[j] = i
    return D

def pairwise_coprime_check(A_list, D):
    p_count = [0] * (max(A_list) + 1)
    for A in A_list:
        temp = A
        d = 0
        while temp != 1:
            if p_count[D[temp]] == 1 and d != D[temp]:
                return 0
            p_count[D[temp]] = 1
            d = D[temp]
            temp = temp // D[temp]
    return 1

## 標準入力
N = int(input())
A_list = list(map(int, input().split(" ")))

# 整数の最大値を取得
A_max = max(A_list)

# 本体
if(setwise_coprime_check_fun(A_list, N) != 1):
    print("not coprime")
else:
    D = preprocess_fun(A_max)
    if pairwise_coprime_check(A_list, D) == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
N, M = map(int, input().split())
ABs = [input().split() for i in range(M)]
 
 
MPs = {}
for a, b in ABs:
	a = int(a)
    b = int(b)
    if a not in MPs:
        MPs[a] = 1
    else:
        MPs[a] += 1
    if b not in MPs:
        MPs[b] = 1
    else:
        MPs[b] += 1
 
for mp in range(1, N+1):
    if mp not in MPs:
        MPs[mp] = '0'
 
for _, y in sorted(MPs.items()):
    print(y)

### FIXED CODE ###

from collections import defaultdict
N, M = map(int, input().split())
city_road_nums = defaultdict(int)

for _ in range(M):
    a, b = map(int, input().split())
    city_road_nums[a] += 1
    city_road_nums[b] += 1

for i in range(1, N+1):
    print(city_road_nums[i])
N = int(input())
a = list(map(int, input.split()))
b = list(map(int, input.split()))

ba = 0, bb = 0
for i in range(N):
    if a[i] > b[i]:
        ba += a[i] - b[i]
    if b[i] > a[i]:
        bb += (b[i] - a[i])//2

if bb >= ba:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

ba = 0
bb = 0
for i in range(N):
    if a[i] > b[i]:
        ba += a[i] - b[i]
    if b[i] > a[i]:
        bb += (b[i] - a[i])//2

if bb >= ba:
    print("Yes")
else:
    print("No")
n=int(input())
k=int(input())
a = [int(input()) for i in range(n)]
a.sort()
print(sum(a[:k]))

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
print(sum(a[:k]))
n = int(input())
h_list = list(map(int,input().split()))
cost_min_list = [0] * n
cost_min_list[0] = 0
cost_min_list[1] = abs(h_list[1] - h_list[0])
for i in range(2, n):
    cost_min_list[i] = min(cost_min_list[i - 1] + abs(h_list[i] - h_list[i - 1]),
                           cost_min_list[i - 2] + abs(h_list[i] - h_list[i - 2]))
print(cost_min_list[n])

### FIXED CODE ###

n = int(input())
h_list = list(map(int,input().split()))
cost_min_list = [0] * n
cost_min_list[0] = 0
cost_min_list[1] = abs(h_list[1] - h_list[0])
for i in range(2, n):
    cost_min_list[i] = min(cost_min_list[i - 1] + abs(h_list[i] - h_list[i - 1]),
                           cost_min_list[i - 2] + abs(h_list[i] - h_list[i - 2]))
print(cost_min_list[n - 1])
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range (m):
  b,c=map(int,input().split())
  d=0
  while b!=0 orc<=a[d] :
    a[d]=c
    d+=1
    
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
changer=[]
cl=0
flag=0
for i in range(m):
  b=list(map(int,input().split()))
  changer.append(b)
changer.sort(key=lambda x:x[1],reverse=True)
for i in range(m):
  if flag==1:
    break
  for j in range(cl,min(cl+changer[i][0],n)):
    if a[j]<changer[i][1]:
      a[j]=changer[i][1]
    else:
      flag=1
      break
  cl+=changer[i][0]
print(sum(a))
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X, t = MAP()
print(X-t)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

X, t = MAP()

print(X-t if X > t else 0)
a, b, c = map(int, input().split())
if a, b, c < 10**5:
  if 4*a*b < (c-a-b)**2 and c-a-b >0:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

a, b, c = map(int, input().split())
if c > a+b and 4*a*b < (c-a-b)**2:
  print("Yes")
else:
  print("No")
'''
浮動小数点は長い数を扱うと誤差が生じる
また、整数で計算しようとした時も√の中身は0以上であるという条件から
c > a+b　を忘れてはいけない
'''
n, k = map(int, read().split())
s = read()
k -= 1
s= s[:k] + str.lower(s[k]) + s[k+1:]
print(s)

### FIXED CODE ###

read = input
n, k = map(int, read().split())
s = read()
k -= 1
s= s[:k] + str.lower(s[k]) + s[k+1:]
print(s)
from collections import Counter

n = int(input())
s =  Counter("".join(sorted(input())) for i in range(n))

print(sum(map(lambda x : x * (x - 1) // 2, s.values())))


### FIXED CODE ###

a,b=map(int,input().split())
print(max(a+b,max(a-b,a*b)))
# input
N, M = map(int, input().split())

c = []

c_append = c.append

for i in range(M):
    sm, cm = map(int, input().split())
    c_append((sm, cm))

if (1, 0) in c:
    print(-1)
else:
    ans = -1

    # check
    for i in range(1000):
        str_i = str(i)

        if N < len(str_i):
            break

        if False not in [int(str_i[sm - 1]) == cm for sm, cm in c]:
            ans = i
            break

    print(ans)

### FIXED CODE ###

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

c = []

c_append = c.append

for i in range(M):
    sm, cm = map(int, input().split())
    c_append((sm, cm))

ans = -1

# check
for i in range(1000):
    str_i = str(i)

    if N < len(str_i):
        break

    if N == len(str_i) and False not in [int(str_i[sm - 1]) == cm for sm, cm in c]:
        ans = i
        break

print(ans)
x,t = map(int, input().split())
print(max(0. x-t)

### FIXED CODE ###

x,t = map(int, input().split())
print(max(0, x-t))
import math

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

S = input()
T = input()

x = N * M // math.gcd(N,M)
flag = True

#print(S[0 * (N / math.gcd(N,M)) + 1])
for i in range(math.gcd(N,M)):
  if not(S[i * (N // math.gcd(N,M))] == T[i * (M // math.gcd(N,M))]):
    flag = False
#    print(S[i * (N // math.gcd(N,M))]  , T[i * (M // math.gcd(N,M))])
if flag:
  print(x)
else:
  print('-1')

### FIXED CODE ###

def gcd(a,b):
  if a%b == 0:
    return b
  return gcd(b,a%b)


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

S = input()
T = input()

x = N * M // gcd(N,M)
flag = True

#print(S[0 * (N / math.gcd(N,M)) + 1])
for i in range(gcd(N,M)):
  if not(S[i * (N //gcd(N,M))] == T[i * (M // gcd(N,M))]):
    flag = False
#    print(S[i * (N // math.gcd(N,M))]  , T[i * (M // math.gcd(N,M))])
if flag:
  print(x)
else:
  print('-1')
ソースコード 

Copy
Copy
y1_list = list(map(int,input().split()))
y2_list = list(map(int,input().split()))
y3_list = list(map(int,input().split()))
 
a1 = list()
a2 = list()
a3 = list()
for i in range(3):
    a1.append(y1_list[i] - y2_list[i])
    a2.append(y2_list[i] - y3_list[i])
    
if a1[0] == a1[1] and a1[2] == a1[0]:
    if a2[0] == a1[1] and a2[2] == a1[0]:
        print("Yes")
        
    else:
        print("No")
else:
    print("No")

### FIXED CODE ###

y1_list = list(map(int,input().split()))
y2_list = list(map(int,input().split()))
y3_list = list(map(int,input().split()))
L = [y1_list,y2_list,y3_list]
 
a1 = list()
a2 = list()
b1 = list()
b2 = list()
 
for i in range(3):
    a1.append(y1_list[i] - y2_list[i])
    a2.append(y2_list[i] - y3_list[i])
    b1.append(L[i][0] - L[i][1])
    b2.append(L[i][1] - L[i][2])
 
 
if (a1[0] == a1[1] and a1[2] == a1[0])and(b1[0] == b1[1] and b1[2] == b1[0]):
    if (a2[0] == a2[1] and a2[2] == a2[0])and(b2[0] == b2[1] and b2[2] == b2[0]):
        print("Yes")
        
    else:
        print("No")
else:
    print("No")
n,k,x,y=map(int, input().split("¥n"))
tmp=0
if n>=k:
    print(x*k+y*(n-k))
else:
    print(x*n)

### FIXED CODE ###

n=int(input())
k=int(input())
x=int(input())
y=int(input())
print(min(n,k)*x+max(n-k,0)*y)
S = input()
N = len(S)
MOD = 10 ** 9 + 7

q = 3 if S[0] == '?' else 1
a = b = c = 0
if S[0] in 'A?':
    a = 1
for s in S[1:]:
    if s == '?':
        c = c * 3 + b
        b = b * 3 + a
        a = a * 3 + q
        q *= 3
    elif s == 'A':
        a += q
    elif s == 'B':
        b += a
    elif s == 'C':
        c += b
    a, b, c = a % MOD, b % MOD, C % MOD

ans = c % MOD
print(ans)

### FIXED CODE ###

S = input()
N = len(S)
MOD = 10 ** 9 + 7

dp = [0, 0, 0, 0]
dp[0] = 1

for s in S:
    factor = 3 if s == '?' else 1
    for j, c in zip([2, 1, 0], 'CBA'):
        dp[j + 1] = dp[j + 1] * factor % MOD
        if s == c or s == '?':
            dp[j + 1] += dp[j]
    if s == '?':
        dp[0] = (dp[0] * 3) % MOD

ans = dp[-1] % MOD

print(ans)
n = int(input())

sayTable = []
for i in range(n):
	a = int(input())
	
	sayArray = []
	for j in range(a):
		x, y = [int(v) for v in input().split()]
		sayArray.append((x-1, y+1))
	sayTable.append(sayArray)

def count(honest):
	count = 0
	for v in honest:
		if v == 2:
			count += 1
	return count

def checkHonest(sayArray, honest):
	for x, y in sayArray:
		if y == 2 and honest[x] != 2:
			return False
	return True

def checkHonestAll(sayTable, honest):
	for i in range(n):
		h = honest[i]
		if h != 2:
			continue
		for x, y in sayArray:
		if honest[x] != y:
			return False
	return True

def setHonest(honest, sayArray):
	for x, y in sayArray:
		honest[x] = y

def search(sayTable, honest, i):
	if i >= n;
		if checkHonestAll(sayTable, honest):
			return count(honest)
		else:
			return 0

	count = 0
	h = honest[i]
	if (h == 0 or h == 2) and checkHonest(sayTable, honest):
		copyHonest = honest[:]
		setHonest(copyHonest, sayTable[i])
		copyHonest[i] = 2
		c = search(sayTable, copyHonest, i + 1)
		if count < c:
			count = c

	honest[i] = 1
	c = search(sayTable, honest, i+1)
		if count < c:
			count = c
	return count

print(search(sayTable, [0] * n, 0));



### FIXED CODE ###

n = int(input())

sayTable = []
for i in range(n):
	a = int(input())
	
	sayArray = []
	for j in range(a):
		x, y = [int(v) for v in input().split()]
		sayArray.append((x-1, y+1))
	sayTable.append(sayArray)

def countHonest(honest):
	count = 0
	for v in honest:
		if v == 2:
			count += 1
	return count

def checkHonest(sayArray, honest):
	for x, y in sayArray:
		if honest[x] == 0:
				continue
		if y == 2 and honest[x] != 2:
			return False
	return True

def checkHonestAll(sayTable, honest):
	for i in range(n):
		h = honest[i]
		if h != 2:
			continue
		sayArray = sayTable[i]
		for x, y in sayArray:
			if y != honest[x]:
				return False
	return True

def setHonest(sayArray, honest):
	for x, y in sayArray:
		honest[x] = y

def search(sayTable, honest, i):
	if i >= n:
		if checkHonestAll(sayTable, honest):
			return countHonest(honest)
		else:
			return 0

	count = 0
	h = honest[i]
	sayArray = sayTable[i]
	if (h == 0 or h == 2) and checkHonest(sayArray, honest):
		copyHonest = honest[:]
		setHonest(sayArray, copyHonest)
		copyHonest[i] = 2
		c = search(sayTable, copyHonest, i+1)
		if count < c:
			count = c

	honest[i] = 1
	c = search(sayTable, honest, i+1)
	if count < c:
		count = c
	return count

print(search(sayTable, [0] * n, 0))
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[int(input()) for i in range(n)]
a.sort()
# b=sorted(a,reverse=True)
c=[0]*n
ans=0
for i in range((n-1)//2):
    ans-=a[i]
for i in range((n-2)//2):
    ans+=a[n-1-i]
ans*=2
if n%2!=0:
    ans+=a[n//2]+a[n//2+1]
else:
    ans+=a[n//2]-a[n//2-1]

ans2=0
for i in range((n-1)//2):
    ans2+=a[n-1-i]
for i in range((n-2)//2):
    ans2-=a[i]
ans2*=2
if n%2!=0:
    ans2-=a[n//2]+a[n//2-1]
else:
    ans2+=a[n//2]-a[n//2+1]

# print(ans)
# print(ans2)

print(max(ans,ans2))

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[int(input()) for i in range(n)]
a.sort()
if n==2:
    print(a[1]-a[0])
    quit()

ans=0
for i in range((n-1)//2):
    ans-=a[i]
for i in range((n-2)//2):
    ans+=a[n-1-i]
ans*=2
if n%2!=0:
    ans+=a[n//2]+a[n//2+1]
else:
    ans+=a[n//2]-a[n//2-1]

ans2=0
for i in range((n-1)//2):
    ans2+=a[n-1-i]
for i in range((n-2)//2):
    ans2-=a[i]
ans2*=2
if n%2!=0:
    ans2-=a[n//2]+a[n//2-1]
else:
    ans2+=a[n//2]-a[n//2+1]

# print(ans)
# print(ans2)

print(max(ans,ans2))
from numba import njit

@njit("i8(i8)")

n = int(input())    

def solve(n):
    s = [1]*(n+1)
    ans = 1
    for i in range(2,n+1):
        for j in range(i,n+1,i):
            s[j] += 1
        ans += (i * s[i])

print(solve(n))


### FIXED CODE ###

from numba import njit
import numpy as np


@njit("i8(i8)")
def solve(n):
    ans = 1
    res = np.ones(n + 1, dtype=np.int64)
    for i in range(2, n + 1):
        for j in range(i, n + 1, i):
            res[j] += 1
        ans += i * res[i]
    return ans


N = int(input())
print(solve(N))
def count(n):
  ans = 0
  for i in range(1,n+1):
    if n % i == 0:
      ans += 1
  return ans

ans = 0
a = (int(i) for i in input().split())
for i in range(1,n+1):
  if count(i) == 8:
    ans += 1
print(ans)

    

### FIXED CODE ###

def count(n):
  ans = 0
  for i in range(1,n+1):
    if n % i == 0:
      ans += 1
  return ans

ans = 0
N = int(input())
for i in range(1,N + 1):
  if i % 2 == 0:
  	continue
  if count(i) == 8:
    ans += 1
print(ans)
from math import gcd
n, k = map(int, input().split())
a = list(map(int, input().split()))

a_gcd = a[0]
for i in range(1, n):
    a_gcd = gcd(a_gcd, a[i])
ans = True
if k > max(a):
    ans = False
if k % a_gcd != 0:
    ans = False
if k in a:
    ans = True

print('POSSIBLE' if ans else 'IMPOSSIBLE')

### FIXED CODE ###

from fractions import gcd
n, k = map(int, input().split())
a = list(map(int, input().split()))

a_gcd = a[0]
for i in range(1, n):
    a_gcd = gcd(a_gcd, a[i])
ans = True
if k > max(a):
    ans = False
if k % a_gcd != 0:
    ans = False
if k in a:
    ans = True

print('POSSIBLE' if ans else 'IMPOSSIBLE')
x,a=int(input())
if x<a:
  print(0)
else:
  print(10)

### FIXED CODE ###

x,a=map(int,input().split())
if x<a:
  print(0)
else:
  print(10)
A=int(input())
B=int(input())
print(A*B)

### FIXED CODE ###

a,b = map(int,input(). split ())
print(a*b)
N,A,B = [int(x) for x in input().split()]
n = 0
blue = 0
if A == 0:
    print(0)
else:
    for i in range(10**5):
        n = n + A
        blue = blue + A
        if n >= N:
            blue = blue - (n-N)
            break
        else:
            n = n + B
            if n >= N:
                break
    print(blue)

### FIXED CODE ###

S = input()
count = 0
for i in range(len(S)):
    if S[0] == S[i]:
        count += 1
if count == 3:
    print("No")
else:
    print("Yes")
in = input().split(' ')
in = list(map(int, in))
in.pop(0)

P = round(sum(in)/len(in))

sum = 0
for i in range(len(in)):
  sum += (in[i] - P)**2
  
print(sum)

### FIXED CODE ###

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

P = round(sum(numbers)/N)

sum = 0
for i in range(N):
  sum += (numbers[i] - P)**2

print(sum)
def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(12):
        for y in range(12):
            if is_data[x][y] == 1:#島が発見されたら
                print(x,y)
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data[x]) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == 1:
        is_data[x][y] = 0
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)

try:
    is_data=[]
    while True:
        s = input()#入力
        if not s :#空入力のときループぬける
            break
        is_data.append(s)
    for i in range(len(is_data)):
        is_data[i] = list(map(int,is_data[i]))
    is_data = np.array(is_data).reshape(12,12)
except EOFError:

print(counter())


### FIXED CODE ###

def counter():#島の数をカウントする
    count=0
    #12*12個の値をひとつずつ調べる
    for x in range(len(is_data)):
        for y in range(len(is_data)):
            if is_data[x][y] == '1':#島が発見されたら
                dfs(x,y)
                count+=1
    return count
def dfs(x,y):
    if x<0 or x == len(is_data) or y<0 or y == len(is_data):
        return
    if is_data[x][y] == '1':
        is_data[x][y] = '0'
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x-1,y)
        dfs(x,y-1)

is_data=[]
while True:
    try:
        s = list(input())#入力
        if not s:#空入力のとき
            print(counter())
            is_data=[]
            s = []
        else:
            is_data.append(s)
    except EOFError:
        print(counter())
        break
#https://atcoder.jp/contests/abc061/tasks/abc061_d



# coding: utf-8
# Your code here!

#input_template
inpPh = 2
debug = True
debug = False
if not debug:
    inpPh = 0

input1 ='''
3 3
1 2 4
2 3 3
1 3 5 
'''[1:]

input2 ='''
2 2
1 2 1
2 1 1
'''[1:]

input3 ='''
6 5
1 2 -1000000000
2 3 -1000000000
3 4 -1000000000
4 5 -1000000000
5 6 -1000000000
'''[1:]



inputXs = [input1, input2, input3, None]


if debug:
    try:
        inputXs.append(inputA0)
    except:
        pass
    else:
        pass



    
inploc = inpPh - 1 #0,1,2

if inpPh > 0:
    print('selected_input:\n'+inputXs[inploc])


inpX_lst = []
if debug and inpPh > 0:
    inpX_lst = inputXs[inploc].splitlines()


if inpPh == 0:
    N,M = tuple(map(lambda x: int(x), input().split() ) )
else:
    N,M =tuple( map(lambda x: int(x),  inpX_lst.pop(0).split() ) )

elist = []    

for i in range(M):
    if inpPh == 0:
        ai,bi,ci = list(map(lambda x: int(x), input().split() ))
    else:
        ai,bi,ci = list(map(lambda x: int(x), inpX_lst.pop(0).split() ))
    
    ai_loc, bi_loc = ai-1, bi - 1
    elist.append(( ai_loc, bi_loc,ci))

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

for e in elist:
    a,b,c = e
    vlist[a][1].append((a,b,-c))
        
s_loc,g_loc = 0, N-1

vlist[s_loc][0] = 0
#print(vlist)

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g0 = vlist[g_loc][0]            

for v1 in vlist:
    v1_d,v1_elist = v1[0],v1[1]
    #print(v1_d,v1_elist)
    for e in v1_elist:
        a,b,c = e
        v2 = vlist[b]
        v2_d, v2_elist = v2
        if v1_d == None:
            continue
        elif v2_d == None or v2_d > v1_d +c:
            vlist[b][0] = v1_d + c

g1 = vlist[g_loc][0]  

if g0 != g1:
    print('inf',end='')
else:
    print(-g0,end='')

#print('res',g0,g1)
for v in vlist:
    #print(v)        
    pass

### FIXED CODE ###

import sys

INF = float('inf')

def Bellmanford(n, edges, r): #r: 始点
    d = [INF] * n
    d[r] = 0
    
    for i in range(n):
        for (u, v, c) in edges:
            if d[u] != INF and d[u] + c < d[v]:
                d[v] = d[u] + c
                if i == n-1 and v == n-1:
                    return 'inf'
    
    return -d[n-1]
    

N, M = map(int, sys.stdin.readline().split())
Edges = [None] * M

for i in range(M):
    ai, bi, ci = map(int, sys.stdin.readline().split())
    Edges[i] = (ai-1, bi-1, -ci)
    
ans = Bellmanford(N, Edges, 0)

print(ans)
MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
pls=[]
mls=[]
for i in range(N):
  if ls[i]>=0:
    pls.append(ls[i])
  else:
    mls.append(ls[i])
pls=sorted(pls)
mls=sorted(mls,reverse=True)

#N=Kのときは全部かけるしかない
if N==K:
  ans=1
  for i in range(N):
    ans=(ans*ls[i])%MOD
  print(ans)
  exit()
  
#全部負の数でKが奇数のとき
if pls==[] and K%2==1:
  ans=1
  for i in range(K):
    ans=(ans*mls[-1-i])%MOD
  print(ans)
  exit()

#その他
p=len(pls)
m=len(mls)
ans=1
k=K
if k%2==1:
  ans=ans*pls[-1]%MOD
  del pls[-1]
  k-=1
while k>0:
  if m==1:
    ans=(ans*pls[-1]*pls[-2])%MOD
    del pls[-1]
    del pls[-1]
    p-=2
  elif p>1 and pls[-1]*pls[-2]>mls[-1]*mls[-2]:
    ans=(ans*pls[-1]*pls[-2])%MOD
    del pls[-1]
    del pls[-1]
    p-=2
  else:
    ans=(ans*mls[-1]*mls[-2])%MOD
    del mls[-1]
    del mls[-1]
    m-=2
  k-=2
print(ans)

### FIXED CODE ###

MOD=10**9+7
N,K=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ans=set()
ls=sorted(ls, key=lambda x: -abs(x))
mul=1
sign=0
zeroflag=0
flag=[0 for _ in range(N)]
for i in range(K):
  flag[i]=1
  if ls[i]<0:
    sign=(sign+1)%2
if sign==1:
  if 0 in ls:
    zeroflag=1
  a=[0,0,0,0]
  b=[0,0,0,0]
  for j in range(K,N):
    if ls[j]>0:
      for k in range(K):
        if ls[K-1-k]<0:
          a[0]=ls[j]
          b[0]=j
          a[1]=ls[K-1-k]
          b[1]=K-1-k
          break
      break
  for j in range(K,N):
    if ls[j]<0:
      for k in range(K):
        if ls[K-1-k]>0:
          a[2]=ls[j]
          b[2]=j
          a[3]=ls[K-1-k]
          b[3]=K-1-k
          break
      break
  if a==[0,0,0,0]:
    flag.reverse()
  elif b[0]==0 and b[1]==0:
    flag[b[2]]=1
    flag[b[3]]=0
  elif b[2]==0 and b[3]==0:
    flag[b[0]]=1
    flag[b[1]]=0
  elif abs(a[0]*a[3])>abs(a[1]*a[2]):
    flag[b[0]]=1
    flag[b[1]]=0
  else:
    flag[b[2]]=1
    flag[b[3]]=0
if sign==1 and a==[0,0,0,0] and zeroflag==1:
  print(0)
else:
  mul=1
  for i in range(N):
    if flag[i]==1:
      mul=mul*ls[i]%MOD
  print(mul)
s = input()
ans = 0
if s == 'SSS':
    print(3)
elif s == 'SSR' or s == 'RSS':
    print(2)
elif s == 'SRR' or s == 'RSR' s == 'RRS' or s == 'SRS':
    print(1)
else:
    print(0)

### FIXED CODE ###

s = input()
ans = 0
if s == 'SSS':
    print(0)
elif s == 'SSR' or s == 'RSS' or s == 'SRS' or s == 'RSR':
    print(1)
elif s == 'SRR' or s == 'RRS':
    print(2)
else:
    print(3)