Harryxun/stf_run huggingface dataset:
from math import gcd


def main():
    #####segfunc######
    def segfunc(x, y):
        return gcd(x, y)

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i + num - 1] = init_val[i]
            # built
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    n = int(input())
    a = tuple(map(int, input().split()))

    #####単位元######
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num
    init(a)

    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0, i), query(i + 1, n)))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd


def main():
    #####segfunc######
    def segfunc(x, y):
        return gcd(x, y)

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i + num - 1] = init_val[i]
            # built
        for i in range(num - 2, -1, -1):
            seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k - 1) // 2
            seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = segfunc(res, seg[p])
            if q & 1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    n = int(input())
    a = tuple(map(int, input().split()))

    #####単位元######
    ide_ele = 0

    # num:n以上の最小の2のべき乗
    num = 2 ** (n - 1).bit_length()
    seg = [ide_ele] * 2 * num
    init(a)

    ans = -1
    for i in range(n):
        ans = max(ans, gcd(query(0, i), query(i + 1, n)))
    print(ans)


if __name__ == '__main__':
    main()
input()
da = list(map(int,input().split()))
 
x = max(da)
y = x + 1
for i in da:
	if i == x:
  		continue
    if abs(x/2 - i ) <= abs(x/2 - y):
		y = i
print(x,y)

### FIXED CODE ###

input()
da = list(map(int,input().split()))
 
x = max(da)
y = x + 1
for i in da:
  if i == x:
    continue
  if abs(x/2 - i ) <= abs(x/2 - y):
    y = i
print(x,y)
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n)]
z = Case

for i in range(1,10001):
   print('{} {} : {}',format(z,i,e))

### FIXED CODE ###

i = 1
while True:
     x = int(input())
     if x == 0: break
     print('Case {}: {}'.format(i, x))
     i += 1
# Modulo Summation
import math
from functools import reduce


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


n = int(input())
a = list(map(int, input().split()))
m = reduce(lcm, a, 1) - 1
print(sum(map(lambda x: m % x, a)))


### FIXED CODE ###

# Modulo Summation
input()
a = list(map(int, input().split()))
x = 1
for i in a:
    x *= i
print(sum(list(map(lambda j: (x - 1) % j, a))))
def submit():
    k = int(input())

    if k % 2 == 0:
        print(-1)
        return
    if k == 5:
        print(-1)
        return

    d = {}
    for t in [1, 3, 7, 9]:
        d[t] = {}
        for i in range(10):
            d[t][t * i % 10] = i
    
    td = k % 10
    curr = 0
    count = 0
    while count == 0 or curr != 0:
        diff = 7 - (curr % 10)
        if diff != 0:
            if diff < 0:
                diff += 10
            coef = d[td][diff]
            curr += coef * k
        curr //= 10
        count += 1

    print(count)
    

submit()    

### FIXED CODE ###


def submit():
    k = int(input())

    if k % 2 == 0:
        print(-1)
        return
    if k % 5 == 0:
        print(-1)
        return

    d = {}
    for t in [1, 3, 7, 9]:
        d[t] = {}
        for i in range(10):
            d[t][t * i % 10] = i
    
    td = k % 10
    curr = 0
    count = 0
    while count == 0 or curr != 0:
        diff = 7 - (curr % 10)
        if diff != 0:
            if diff < 0:
                diff += 10
            coef = d[td][diff]
            curr += coef * k
        curr //= 10
        count += 1

    print(count)
    
submit()
N , W = map(int,input().split())
dp[W+1] = [0]

for i in range(N):
    n , m = map(int,input().split())
    for j in range(W,m-1,-1):
        x = n + dp[j-m]
        if x >= dp[j]:
            dp[j] = x:
            
print(dp[W])


### FIXED CODE ###

N , W = map(int,input().split())
dp = [0]*(W+1)

for i in range(N):
    n , m = map(int,input().split())
    for j in range(W,m-1,-1):
        x = n + dp[j-m]
        if x >= dp[j]:
            dp[j] = x
            
print(dp[W])
N,A=map(int,input().split())
print("Yes" if N%500<=A else "No")

### FIXED CODE ###

N=int(input())
A=int(input())
if N%500<=A:
    print("Yes")
else:
    print("No")
N,T = map(int, input().split())

ans = []

for i in range(N):
    c,t = list(map(int, input().split()))
    if T > t[i]:
        number = c[i]
        ans.appned(number)
    

if len(ans) == 0:
    print("TLE")
else:
    print(min(ans))        

### FIXED CODE ###

N, T = map(int,input().split())
c = []
t = []

for i in range(N):
  c1, t1 = map(int,input().split())
  c.append(c1)
  t.append(t1)
  
ans = []

for i in range(N):
  if t[i] <= T:
    ans.append(c[i])

if len(ans) == 0:
  print("TLE")
else:
  print(min(ans))
import math
n,m=list(map(int,input().split()))
lim=(int)(2*m/((n-1)*(n)))
for i in reversed(range(1,lim+2)):
    a=m%i
    b=m/i
    print(i,a,b,n)
    if a==0 and b>=n:
        for j in range(1,(int)(n/3+1)):
            if(math.factorial(b-2)
                    /(math.factorial(n-j-1)*math.factorial(b-n+j-1))>0):
                print(j*i)
                exit()


### FIXED CODE ###

n, m = (list)(map(int, input().split()))

upper = m//n
ans = 0
for i in range(1, upper+1):
    if m % i == 0:
        ans = i
        if (m // i) > i and (m // i) <= upper:
            ans = m // i
            break

print(ans)
n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = []
for _ in range(m):
    b, c = map(int, input().split())
    bc.append([b, c])
    
a = sorted(a)
bc = sorted(bc, key=lambda x: x[1])

que = []
for b, c in bc:
    que += [c]*b


c = que.pop()
ans = 0
i = 0
while True:
    if a[i] < c:
        ans += c
        if que:
            c = que.pop()
            i += 1
        else:
            i += 1
            break
    else:
        break
print(ans + sum(a[i:]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(reverse=True, key=lambda x: x[1])
j = 0
for i in range(m):
    while j < len(a) and bc[i][0] > 0:
        if a[j] < bc[i][1]:
            a[j] = bc[i][1]
            bc[i][0] -= 1
        j += 1
print(sum(a))
def travel(x,y,t):
    for i in range(t):
        if x+y==t-2*i:
            return True
    return False
n=int(input())
for i in range(n):
    t, x, y = [int(j) for j in input().split() ]
    if not travel(x,y,t):
        print("No")
        exit()
print("Yes")    


### FIXED CODE ###

a,b=[int(i) for i in input().split()]
if a*b%2==1:
  print('Odd')
else:
  print('Even')
N =int(input())
A = list(map(int,input().rstrip().split(" ")))
Aq = []
DP = [0 for i in range(2 * 10 ** 5)]
DPP = []
ans = 0
for i in range(N):
    if i >= A[i]:
        ans += DP[i - A[i]]
    if A[i] <= N:
        DP[A[i] + i] += 1
    
print(ans)

### FIXED CODE ###

N =int(input())
A = list(map(int,input().rstrip().split(" ")))
Aq = []
DP = [0 for i in range(5 * 10 ** 5)]
DPP = []
ans = 0
for i in range(N):
    if i >= A[i]:
        ans += DP[i - A[i]]
    if A[i] <= N:
        DP[A[i] + i] += 1
    
print(ans)
a = input()
if a[2]==a[[3] and a[4]==a[5]:
           print("Yes")
           
esle:
           print("No")

### FIXED CODE ###

s = input()
if s[2]==s[3] and s[4]==s[5]:
  print("Yes")
else:
  print("No")
A, B, C, D = map(int, input().aplit())

l = A + B
r = C + D

if l > r:
  print("Left")
elif l == r:
  print("Balanced")
elif l < r:
  print("Right")

### FIXED CODE ###

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

l = A + B
r = C + D

if l > r:
  print("Left")
elif l == r:
  print("Balanced")
elif l < r:
  print("Right")
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


N = int(input())
A = list(map(int, input().split()))
L = [0 for i in range(N)]
R = [0 for i in range(N)]
T = [0 for i in range(N)]

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

print(max(T))

### FIXED CODE ###

I = list(map(int, input().split()))
A = I[0]
B = I[1]
T = I[2]

ans = (T // A) * B

print(ans)
from sys import stdin


def calc_cost(p, x):
    return (x - p)**2


def min_cost(n, data):
    cost = 1_000_000
    for p in range(1, 100 + 1):
        tmp_cost = sum([calc_cost(p, x) for x in data])
        if tmp_cost < cost:
            cost = tmp_cost
    return cost


def main():
    N = [int(x) for x in stdin.readline().rstrip()]
    CORP = [int(x) for x in stdin.readline().rstrip().split()]
    cost = min_cost(N, CORP)
    print(cost)


main()


### FIXED CODE ###

from sys import stdin


def calc_cost(p, x):
    return (x - p)**2


def min_cost(n, data):
    cost = 1000000
    for p in range(1, 100 + 1):
        tmp_cost = sum([calc_cost(p, x) for x in data])
        if tmp_cost < cost:
            cost = tmp_cost
    return cost


def main():
    N = [int(x) for x in stdin.readline().rstrip()]
    CORP = [int(x) for x in stdin.readline().rstrip().split()]
    cost = min_cost(N, CORP)
    print(cost)


if __name__ == "__main__":
    main()
n = int(input())
a = input().split()
pl = []
sb = []
for i in range(len(a)):
	pl.append(i+int(a[i])+1)
	if i - int(a[i]) > 1:
		sb.append(i-int(a[i])+1)


if len(sb) == 0:
	print('0')
else:

# spl = sorted(pl)
	ssb = sorted(sb)
	t = min(ssb)
	tl = [0] * max(pl)
	for i in ssb:
		tl[int(i)-1] += 1
	# print(pl)
	# print(sb)
	# print(tl)
	cnt = 0
	for i in pl:
		cnt += tl[int(i)-1]

	print(cnt)
	



### FIXED CODE ###

n = int(input())
a = input().split()
pl = []
sb = []
for i in range(len(a)):
	pl.append(i+int(a[i])+1)
	if i - int(a[i]) > 0:
		sb.append(i-int(a[i])+1)


if len(sb) == 0:
	print('0')
else:

# spl = sorted(pl)
	isb = [int(i) for i in sb]
	ipl = [int(i) for i in pl]
	ssb = sorted(isb)
	t = min(ssb)
	# tl = [0] * max(ipl)
	tl = [0] * 2000000	
	for i in ssb:
		if int(i)-1 < len(tl):
			tl[int(i)-1] += 1
	# print(pl)
	# print(sb)
	# print(tl)
	cnt = 0
	for i in pl:
		if int(i)-1 < len(tl):
			cnt += tl[int(i)-1]

	print(cnt)
N, M = map(int, input().split())
A = list(set(map(lambda x : int(x)//2, input().split())))
def gcd(x, y):
  return x if y == 0 else gcd(y, x % y)
def lcm(x, y):
  return (x * y) // gcd(x, y)
l = A[0]
for a in A[1:]:
  l = lcm(l, a)
ans = (M // l + 1) // 2
for a in A[1:]:
  if (l // a) % 2 == 0:
    ans = 0
    break
print(ans)


### FIXED CODE ###

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

a = [0,2,5,5,4,5,6,3,7,6]

kazu = [a[List[i]] for i in range(M)]

def dddd(kazu,X):
  dp = [ [ -float('inf') for j in range(X+1)]  for i in range(M)]
  for i in range(M):
    dp[i][0] = 0

  for i in range(M):
    for j in range(X+1):
      if kazu[i] <= j:
        dp[i][j] = max(dp[i][j-kazu[i]] + 1,dp[i-1][j])
      else:
        dp[i][j] = dp[i-1][j]
  return dp[-1]
   
keta_arr = dddd(kazu,N)
keta = keta_arr[-1]
List.sort(reverse=True)
ans = []

while keta>0:
  for aa in List:
    k = a[aa]
    if N-k < 0:
      continue
    if N-k >= 0:
      if keta_arr[N-k] == keta-1:       
        ans.append(aa)
        N = N-k
        keta -= 1
        break
ans.sort(reverse=True)
print(int(''.join(map(str,ans))))
N = int(input())
S = input()
n = 0
l = [S[0]]
if N > 1:
  for i in range(N):
    if not S[i+1] in l:
      l.append(S[i + 1])
    else:
      n = i + 1
      break
  if S[0:n] == S[n:]:
    print("Yes")
  else:
    print("No")
else:
  print("No")

### FIXED CODE ###

N = int(input())
S = input()
if N > 1:
  if S[0: N // 2] == S[N // 2 :]:
    print("Yes")
  else:
    print("No")
else:
  print("No")
import math
ab=list(map(int,input().split()))
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
print(lcm(ab[0], ab[1]))

### FIXED CODE ###

from fractions import gcd
a,b=map(int,input().split())
def lcm(a,b):
    return a*b // gcd(a,b)
print(lcm(a, b))
N = int(input())

# F(A, B)を定義する
def F(A, B):
    A = str(A)
    B = str(B)
    if len(A) >= len(B):
        return len(A)
    else:
        return len(B)

minimumList = []
for a in range(1, int(N**0.5) + 1):
    if N % a == 0:
        b = N // a
        minimumList.append(F(a, b))
print(min(minimumList))

### FIXED CODE ###

import numpy as np
C = []
for i in range(3):
    c_horizontal = list(map(int, input().split()))
    C.append(c_horizontal)

## Ax = C
A = np.array([
    [1, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 0, 1],
    [0, 1, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 1],
    [0, 0, 1, 1, 0, 0],
    [0, 0, 1, 0, 1, 0],
    [0, 0, 1, 0, 0, 1] ])
# 拡大係数行列
Ab = np.array([
    [1, 0, 0, 1, 0, 0, C[0][0]],
    [1, 0, 0, 0, 1, 0, C[0][1]],
    [1, 0, 0, 0, 0, 1, C[0][2]],
    [0, 1, 0, 1, 0, 0, C[1][0]],
    [0, 1, 0, 0, 1, 0, C[1][1]],
    [0, 1, 0, 0, 0, 1, C[1][2]],
    [0, 0, 1, 1, 0, 0, C[2][0]],
    [0, 0, 1, 0, 1, 0, C[2][1]],
    [0, 0, 1, 0, 0, 1, C[2][2]] ])

# 係数行列と拡大係数行列のランクをそれぞれ求める
rankA = np.linalg.matrix_rank(A)
rankAb = np.linalg.matrix_rank(Ab)

if rankA == rankAb:
    print('Yes')
else:
    print('No')

# print(C)
# A = [0] * 3
# B = [0] * 3
# flgList = []
# for k in range(3):
#     flgHorizontal = [False] * 3
#     flgList.append(flgHorizontal)
# ## c(i, j) = a(i) + b(j)
# for i in range(3):
#     for a in range(101):
#         A[i] = a
#         for j in range(3):
#             B[j] = C[i][j] - A[i]
#                 if C[i][j] == A[i] + B[j]:
#                     print(C[i][j], A[i], B[j])
#                     flgList[i][j] = True
# print(flgList)
# determinantList = [False] * 3
# for m in range(3):
#     if all(flgList[m]):
#         determinantList[m] = True

# if all(determinantList):
#     print('Yes')
# else:
#     print('No')C
n=int(input())
num=map(int,str(n))
if num[-1]=="7" or num[-3]=="7" or num[-2]=="7":
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n=str(input())
if n[-1]=="7" or n[-3]=="7" or n[-2]=="7":
    print("Yes")
else:
    print("No")
n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

### FIXED CODE ###

n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = []
    b = []
    d = [1, 1]
    e = [1, 1]
    f = [0, 1]
    for i in range(2, n):
        d.append(d[-1]*i%z)
        f.append((-f[z%i]*(z//i))%z)
        e.append(e[-1]*f[-1]%z)
    for i in range(k+1):
        b.append(d[n-1]*e[i]*e[n-i-1]%z)
    x = 0
    g = [1]
    for i in range(n-1):
        g.append(g[i]*(m-1)%z)
    for i in range(k+1):
        a.append(b[i]*m*g[n-i-1]%z)
    for i in range(k+1):
        x = (x+a[i])%z
    print(x)
#!/usr/bin/env python
H, W = map(int, input().split())
A_raw = [[int(i) for i in input().split()] for j in range(H)]

c = 1
A = []
d = {}
for h in range(H):
    if h % 2 == 0:
        for a in A_raw[h]:
            A.append(a)
        d.update(zip(range(c, c + W), [(h+1, w) for w in range(1, W+1)]))
    else:
        for a in A_raw[h][::-1]:
            A.append(a)
        d.update(zip(range(c, c + W), [(h+1, w) for w in range(1, W+1)[::-1]]))
    c += W

c = 0
ans = []
for i in range(len(A)-1):
    if A[i] % 2 == 1:
        A[i+1] += 1
        A[i] -= 1
        c += 1
        ans.append([*d[i+1], *d[i+2]])
print(c)
for x in ans:
    print(*x)


### FIXED CODE ###

#!/usr/bin/env python
H, W = map(int, input().split())
A_raw = [[int(i) for i in input().split()] for j in range(H)]

c = 1
A = []
d = {}
for h in range(H):
    if h % 2 == 0:
        for a in A_raw[h]:
            A.append(a)
        d.update(zip(range(c, c + W), [(h+1, w) for w in range(1, W+1)]))
    else:
        for a in A_raw[h][::-1]:
            A.append(a)
        d.update(zip(range(c, c + W), [(h+1, w) for w in range(1, W+1)[::-1]]))
    c += W

c = 0
ans = []
for i in range(len(A)-1):
    if A[i] % 2 == 1:
        A[i+1] += 1
        A[i] -= 1
        c += 1
        ans.append([d[i+1], d[i+2]])
print(c)
for x in ans:
    print(x[0][0], x[0][1], x[1][0], x[1][1])
n = input()
 
A = list(map(int, input().split()))
 
counts = 0
while all(a%2==0 for a in A):
	A = [a/2 for a in A]
    counts += 1
print(counts)

### FIXED CODE ###

n = input()
 
A = list(map(int, input().split()))
 
counts = 0
while all(a%2==0 for a in A):
  A = [a/2 for a in A]
  counts += 1
print(counts)
import sys
n=int(input())
lr=[]
def g(s):
    i = 0
    l = [0]
    for j in s:
        if j =="(":
            i += 1
        else:
            i -= 1
        l.append(i)
    return min(l),max(l)
for _ in range(n):
    s = input()
    l = s.count("(")
    r = len(s) - l
    l_sum += l
    r_sum += r
    mi,ma =g(s)
    lr.append((mi,ma,l,r))
    
cnt = 0
for mi,ma,l,r in lr:
    #print(cnt)
    if cnt+mi>=0:
        cnt += (l-r)
    else:
        print("No")
        sys.exit()
if cnt !=0:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

import sys
n = int(input())
ss =[]
for _ in range(n):
    ss.append(input())
cnt_p = []
cnt_m = []
for i in range(n):
    left = 0
    right = 0
    for s in ss[i]:
        if(s == '('):
            left += 1
        elif(s == ')'):
            if(left > 0):
                left -= 1
            else:
                right += 1
    if(left-right > 0):
        cnt_p.append((right,left))
    else:
        cnt_m.append((right,left))
 
 
cnt_p = sorted(cnt_p, key=lambda x: (x[0]))
cnt_m = sorted(cnt_m, key=lambda x: (x[1]*-1))
cnt = cnt_p + cnt_m
num = 0
for right,left in cnt:
    num -= right
    if(num < 0):
        print('No')
        sys.exit()
    num += left
if(num==0):
    print('Yes')
else:
    print('No')
n = input()
number_list = map(int, input().split())

count = 0
even = True

while even:
    for i, a in enumerate(number_list):
        if a % 2 != 0:
            even = False
        else:
            number_list[i] = a / 2
    if even:
        count += 1
print(count)

### FIXED CODE ###

a = list(input())
print(a.count('1'))
s = int(input())
if s[0]==s[1]==s[2] or s[1]==s[2]==s[3]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = str(input())
if s[0]==s[1]==s[2] or s[1]==s[2]==s[3]:
  print('Yes')
else:
  print('No')
n, k = input().split(" ")
n = int(n)
k = int(k)
a = [int(x) for x in input().split(" ")]
a.sort()
ans = 0
for i in range(k):
 ans += int(a[i])
print(ans)


### FIXED CODE ###

x = input()
print('A' if ord(x) < ord('a') else 'a')
from collections import defaultdict
vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2,weight])
    connect[v2].append([v1,weight])
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print(*ans)
    break

### FIXED CODE ###

vertices, edges = (int(n) for n in input().split(" "))
cost_dp = [[float("inf") if n != m else 0 for n in range(vertices)] for m in range(vertices)]
for e in range(edges):
    v1, v2, weight = (int(n) for n in input().split(" "))
    cost_dp[v1][v2] = weight
for neg in range(2):
    updated = 0
    for t in range(vertices):
        for i in range(vertices):
            for k in range(vertices):
                if cost_dp[i][k] > cost_dp[i][t] + cost_dp[t][k]:
                    updated = 1
                    cost_dp[i][k] = cost_dp[i][t] + cost_dp[t][k]
if neg == 1 and updated:
    print("NEGATIVE CYCLE")
else:
    for ve in range(vertices):
        ans = ["INF" if n == float("inf") else n for n in cost_dp[ve]]
        print(*ans)
a, b, n = list(map(int, input().split()))

if (a + b) <= n:
  a = 0
  b = 0
else:
  if n > a:
    b -= n-a
    a = 0
    if b < 0:
      b = 0
  else:
    a = (n-a)

print("%d %d" %(a,b))

### FIXED CODE ###

a, b = list(map(str, input().split()))
print(b+a)
def shuffle(l,h):
	l.extend(l[0:h])
	del l[0:h]
	
while True :
	card_list = list(raw_input())
	if card_list == ['.']:
		break
	else :
		m = input()
		h_count = [0]*m
		for i in range(m):
			h_count[i] = input()
			shuffle(card_list,h_count[i])
		print("".join(card_list))

### FIXED CODE ###

def shuffle(l,h):
	l.extend(l[0:h])
	del l[0:h]
	
while True :
	card_list = list(raw_input())
	if card_list == ['-']:
		break
	else :
		m = input()
		h_count = [0]*m
		for i in range(m):
			h_count[i] = input()
			shuffle(card_list,h_count[i])
		print("".join(card_list))
a = input().spulit()
A = int(a[0])
B = int(a[1])
C = int(a[2])
D = int(a[3])
q = A*B
w = C*D
if q <= w:
 print(w)
else:
 print(q)

### FIXED CODE ###

a = input().split()
A = int(a[0])
B = int(a[1])
C = int(a[2])
D = int(a[3])
q = A*B
w = C*D
if q <= w:
 print(w)
else:
 print(q)
st = input().split(" ")
s = st[0]
t = st[1]

ab = input().split(" ")
a =int(ab[0])
b =int(ab[1])

u = input()
if u == s:
    print(a-1,b)
if u == t:
    print(a,b-1)


### FIXED CODE ###

abc = input().split(" ")
a = int(abc[0])
b = int(abc[1])
c = int(abc[2])

d = 0
if a==b:
    d=d+1
if b==c:
    d=d+1
if c==a:
    d=d+1
if d==1:
    print("Yes")
else:
    print("No")