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

import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, m = input_list()
    starts = []
    ends = []
    for _ in range(m):
        a, b = input_list()
        if a == 1:
            starts.append((a, b))
        elif b == n:
            ends.append(a)
    for a, b in starts:
        if b in ends:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

def get_camulative(l):
    import itertools
    # 累積和
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

s = []
e = []
for _ in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == n:
    e.append(a)

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！

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

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])

def BELLMANFORD(point,d,p):
    cost       = {node:-float("inf") for node in range(1,n+1)}
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.copy().items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.copy().items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！


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

d={}
for s in range(m):
    a,b,c=map(int,input().split())
    if a in d:
        d[a].append((b,c))
    else:
        d[a]=[(b,c)]

#print(d)


def BELLMANFORD(point,d,p):
    cost       = [-float("inf") for node in range(n+1)]  #infじゃないと閉路検出がうまくいかない
    cost[point]= 0
    for i in range(n-1):                                  #経路の長さは最大n-1であるため
        for now,lis in d.items():
            for nex,c in lis:
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p

    negative=[0]*n                                        #負閉路の長さは最大nであるため
    
    for i in range(n):                  #閉路判定 negativeの1は閉路に入っている部分を表す
        for now,lis in d.items():
            for nex,c in lis:
                if negative[now-1]==1:
                    negative[nex-1]=1
                if cost[nex]<cost[now]+c-p:
                    cost[nex]=cost[now]+c-p
                    negative[now-1]=1
 
    return cost,negative

def main():
    x,y=(BELLMANFORD(1,d,p))
    
    if y[n-1]==1:
        print(-1)
    else:
        print(max(x[n],0))

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

import itertools

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

C = list(itertools.combinations(A, 2))

ans = 0
for i, j in C:
    ans += i * j
    ans = ans % (1e9 + 7)
print(int(ans))

### FIXED CODE ###

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

S = sum(A)
S2 = sum(map(lambda x: x * x, A))

print((S*S-S2)//2 % 1000000007)
### BUGGY CODE ###

import math
S_list = list(input())
n = len(S_list)
x = 0
Timod_list = []

for i in range(n):
  Ti_list = S_list[i:n+1]
  Ti_str = ""
  for y in Ti_list:
    Ti_str = Ti_str + y
  Ti = int(Ti_str)
  Timod = Ti % 2019
  Timod_list = Timod_list + [Timod]

Timod_list.sort()
Timodlist_len= len(Timod_list)

Tlist0 = Timod_list.count(0)
x = x + Tlist0

Timod_lists = [x for x in Timod_list if Timod_list.count(x) > 1]
Timodlists_len = len(Timod_lists)

for j in range(Timodlists_len):
  Tlist = Timod_lists.count(Timod_lists[j])
  x = x + 1 / 2 * math.factorial(Tlist) / Tlist
    
x = int(x)
print(x) 

### FIXED CODE ###

S = input()
Sliststr = list(S)
Slist = [int(s) for s in Sliststr]
Smod = [0]
mod10 = [1]
count = [0]*2019
ans = 0
for i in range(len(S)-1):
  mod10.append(mod10[i]*10%2019)
for i in range(len(S)):
  Smod.append((Smod[i]+Slist[-i-1]*mod10[i])%2019)
for i in range(len(Smod)):
  count[Smod[i]] += 1
for i in range(2019):
  ans += count[i] * (count[i]-1) // 2
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

def runLength(string):
    """文字列strをランレングス圧縮して返す関数
    ex: "0000111101" => [(0,4), (1,4), (0,1), (1,1)]
    """
    res = []
    data, count = string[0], 1
    for i in range(1, len(string)):
        if string[i] == data:
            count += 1
        else:
            res.append((data, count, i))
            data, count = string[i], 1
    res.append((data, count, i))
    return res


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

rl = runLength(S)
keys = [rli[2] for rli in rl]
nrl = len(rl)

ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == S[j]:
            continue
        elif set([S[i], S[j]]) == {"R", "G"}:
            if 2*j - i < N and S[2*j - i] == "B":
                ans += max(sum([rl[x][1] for x in range(bisect_left(keys, j+1), nrl) if rl[x][0] == "B"]) - 1, 0)
            else:
                ans += sum([rl[x][1] for x in range(bisect_left(keys, j+1), nrl) if rl[x][0] == "B"])
        elif set([S[i], S[j]]) == {"B", "G"}:
            if 2*j - i < N and S[2*j - i] == "R":
                ans += max(sum([rl[x][1] for x in range(bisect_left(keys, j+1), nrl) if rl[x][0] == "R"]) - 1, 0)
            else:
                ans += sum([rl[x][1] for x in range(bisect_left(keys, j+1), nrl) if rl[x][0] == "R"])
        else:
            if 2*j - i < N and S[2*j - i] == "G":
                ans += max(sum([rl[x][1] for x in range(bisect_left(keys, j+1), nrl) if rl[x][0] == "G"]) - 1, 0)
            else:
                ans += sum([rl[x][1] for x in range(bisect_left(keys, j+1), nrl) if rl[x][0] == "G"])

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N-2):
    for d in range(1, (N-i-1)//2+1):
        if {S[i], S[i+d], S[i+2*d]} == {"R", "G", "B"}:
            ans -= 1

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

import copy

N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
for i in range(N):
    Ai = copy.copy(A)
    Ai.remove(Ai[i])
    Ai.sort(reverse=True)
    print(Ai[0])

### FIXED CODE ###

import copy

N = int(input())
A = []
for n in range(N):
    A.append(int(input()))

V = copy.copy(A)
V.sort(reverse=True)
for i in range(N):
    if V[0] == A[i]:
        print(V[1])
    else:
        print(V[0])
### BUGGY CODE ###

n = int(input())
s = input()

lenS = len(s)
#print(lenS)
ans = 0
tempAns = 0
for i in reversed(range(1,lenS//2+1)):
	for j in range(0,n-i+1):
		tempS1 = s[j:j+i]
		#print(tempS)
		tempS2 = s[j+i:]
		if (tempS1 in tempS2):
			ans = i
			break
			#print(s[j+i+k-1:j+2*i+k-1], i, j, k)
	if (ans > 0):
		break
print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ans = 0
lenS = 1
for i in range(n):
	tempS = s[i:i+lenS]
	while (tempS in s[i+lenS:]):
		lenS += 1
		tempS = s[i:i+lenS]
		ans += 1

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

n,k=map(int, input().split())
a=list(map(int, input().split()))

class segtree:
    x_unit=0 # 要素として入れられる最大値
    def __init__(self,N):
        self.n=(1<<len(bin(N-1)[2:]))
        self.x=[self.x_unit]*(2*self.n)

    def build(self, seq):
        for i,j in enumerate(seq, start=self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = 0
            # セグ木トーナメント表の左右を比較
            # 例えばn=8の時、seq[4]はx[12]に、seq[5]はx[13]に入っている
            # さらにx[14]とx[15]の間に来るのはx[7]、x[12]とx[13]の間に来るのはx[6]

    def fold(self,l,r): # 区間[l, r)値に+1 
        l+=self.n
        r+=self.n-1
        while l<r:
            if l%2==1: # lが奇数
                self.x[l]+=1
                l+=1 # 偶数に調節
            if r%2==0: # rが偶数
                self.x[r]+=1
                r-=1 # 開区間なので1個前は奇数番目の要素
            l //= 2
            r //= 2
        if l==r:
            self.x[l]+=1
        #print(self.x)
    def get(self,i): # seq[i]に対する値を取得 
        i+=self.n
        ret=self.x[i]
        while i>1:
            i //= 2
            ret+=self.x[i]
        return ret

for z in range(min(k,100)):
    seq=[0]*n
    q=[(max(0, i-a[i]), min(n,i+a[i]+1)) for i in range(n)]
    seg=segtree(n)
    seg.build(seq)
    for i in range(n):
        l,r=q[i]
        seg.fold(l,r)
    ans=[]
    for i in range(n):
        ans.append(seg.get(i))
    a=ans+[]
    if all([i==n for i in a]):
        break
print(*a)

### FIXED CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(k):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
    if all([i==n for i in a]):
        break
print(*a)
### BUGGY CODE ###

def gcd(a, b):
  if(b % a == 0):
    return a
  else:
    ans = 1
    i = 2
    while a!= 1:
      if(a % i == 0):
        while a % i == 0:
          a/= i
        while b % i == 0:
          b/= i
          ans*= i
        i+= 1
    return ans
          

def ggcd(lista):
  l = lista[0]
  for i in range(1, len(lista)):
    l = gcd(l, lista[i])
  return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
d = []

for item in x:
  d.append(abs(X- item))
  
print(ggcd(d))

### FIXED CODE ###

def gcd(a, b):
  if(a == b):
    return a
  elif(a % b == 0):
    return b
  elif(b % a == 0):
    return a
  elif(a == 1 or b == 1):
    return 1
  elif(a > b):
    return gcd(a- a// b* b, b)
  elif(a < b):
    return gcd(a, b- b// a* a)

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])

gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(d[i+ 1])

print(ggcd(gcds))
### BUGGY CODE ###

# coding: utf-8

a = input()
q = int(input())

for i in range(q):
    q_list = input().split()
    if q_list[0] == '1':
        a = a[::-1]
    else:
        if q_list[1] == '1':
            a = q_list[2] + a
        else:
            a += q_list[2]
print(a)


### FIXED CODE ###

# coding: utf-8

a = input()
q = int(input())
mode = 1
L = ''
R = ''

for _ in range(q):
    q_list = input().split()

    if q_list[0] == '1':
        mode *= -1
    else:
        if q_list[1] == '1':
            if mode == 1:
                L += q_list[2]
            else:
                R += q_list[2]
        else:
            if mode == -1:
                L += q_list[2]
            else:
                R += q_list[2]
result = L[::-1] + a + R
if mode == -1:
    result = result[::-1]
print(result)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
for s in ss:
	for i in range(len(s)):
		prefix.add(s[:i+1])
grundy = 0
for p in list(prefix):
	le = len(p)
	if p[le-1] == "0":
		t = p[:le-1] + "1"
	else:
		t = p[:le-1] + "0"
	if t not in prefix:
		grundy ^= (l-le+1) & (-l+le-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

### FIXED CODE ###

import sys
#from collections import defaultdict
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [list(input())[::-1] for _ in range(n)]

def addTree(tree, sentence):
	if not sentence:
		return None   

	if sentence[-1] not in tree:
		tree[sentence[-1]] = {}

	p = sentence.pop()
	tree[p] = addTree(tree[p], sentence)

	return tree

def createTree(sentences):    
	tree = {}
	for sentence in sentences:
		tree = addTree(tree, sentence)

	return tree

tree = createTree(ss)
#print(tree)

grundy = 0
def dfs(cur, level):
	global grundy
	if cur is None:
		return
	elif len(cur) == 1:
		grundy ^= (l-level) & (-l+level)
	for k in cur.keys():
		dfs(cur[k], level+1)
	return
	
dfs(tree, 0)

if grundy == 0:
	print("Bob")
else:
	print("Alice")
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
LR=[]
for i in range(Q):
    LR.append(list(map(int, input().split())))
A=[0]*N

for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        A[i]+=1

for i in range(Q):
    print(sum(A[LR[i][0]-1:LR[i][1]])\
          - int(A[LR[i][1]-1]==1))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
LR=[]
for i in range(Q):
    LR.append(list(map(int, input().split())))

L=[0]*N
R=[0]*N
for i in range(N-1):
    if S[i]=='A' and S[i+1]=='C':
        L[i]+=1
for i in range(1,N):
    L[i]+=L[i-1]

for i in range(1,N):
    if S[i]=='C' and S[i-1]=='A':
        R[i]+=1
for i in range(1,N):
    R[i]+=R[i-1]

for i in range(Q):
    print(min(L[LR[i][1]-1],R[LR[i][1]-1])-\
          min(L[LR[i][0]-1],R[LR[i][0]-1]))
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(N):
    ans += i

print(ans)


### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

N=int(input())
lst=list(map(int, input().split()))
count=0
for i in range(N):
    if lst[i]==min(lst[:i+1]):
        count+=1
print(count)

### FIXED CODE ###

N=int(input())
lst=list(map(int, input().split()))
count=0
m=2*10**5
for i in range(N):
    if m>lst[i]:
        m=lst[i]
    if lst[i]==m:
        count+=1
print(count)
### BUGGY CODE ###

from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = [list(map(int, input().split()))+[i] for i in range(q)]
query.sort(key = lambda x: x[1])
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for x in range(q):
    l, r, z = query[x]
    for i in range(right, r):
        if appear[c[i]] != -1:
            bit.add(appear[c[i]]+1, -1)
        appear[c[i]] = i
        bit.add(appear[c[i]]+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

for i in range(q):
    print(ans[i])


### FIXED CODE ###

from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = [list(map(int, input().split()))+[i] for i in range(q)]
query.sort(key = lambda x: x[1])
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for l, r, z in query:
    for i in range(right, r):
        num = appear[c[i]]
        if num != -1:
            bit.add(num+1, -1)
        appear[c[i]] = i
        bit.add(i+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

print(*ans, sep="\n")
### BUGGY CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

L=[[0]*w for i in range(h)]
R=[[0]*w for i in range(h)]
U=[[0]*w for i in range(h)]
D=[[0]*w for i in range(h)]

for i in range(h):
 for j in range(w):
  if s[i][j]=='#':
   L[i][j]=U[i][j]=0
   continue
  if i==0 and j==0:
   L[i][j]=1
   U[i][j]=1
  elif i==0:
   L[i][j]=L[i][j-1]+1
   U[i][j]=1
  elif j==0:
   L[i][j]=1
   U[i][j]=U[i-1][j]+1
  else:
   L[i][j]=L[i][j-1]+1
   U[i][j]=U[i-1][j]+1

for i in range(h-1,-1,-1):
 for j in range(w-1,-1,-1):
  if s[i][j]=='#':
   R[i][j]=D[i][j]=0
   continue
  if i==h-1 and j==w-1:
   R[i][j]=1
   D[i][j]=1
  elif i==h-1:
   R[i][j]=R[i][j+1]+1
   D[i][j]=1
  elif j==w-1:
   R[i][j]=1
   D[i][j]=D[i+1][j]+1
  else:
   R[i][j]=R[i][j+1]+1
   D[i][j]=D[i+1][j]+1

ans=0
for i in range(h):
 for j in range(w):
  ans=max(ans,R[i][j]+L[i][j]+U[i][j]+D[i][j]-3)
print(ans)

### FIXED CODE ###

import numpy as np

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

s=np.array(s)
s=np.where(s=='.',1,0)

L=np.zeros((h,w),dtype=np.int)
R=np.zeros((h,w),dtype=np.int)
U=np.zeros((h,w),dtype=np.int)
D=np.zeros((h,w),dtype=np.int)

for i in range(w):
 L[:,i]=(L[:,i-1]+1)*s[:,i]
 R[:,-i-1]=(R[:,-i]+1)*s[:,-i-1]
for i in range(h):
 U[i]=(U[i-1]+1)*s[i]
 D[-i-1]=(D[-i]+1)*s[-i-1]

ans=np.max(L+R+U+D)-3
print(ans)
### BUGGY CODE ###

n = int(input())
an = map(int, input().split())

sum_an = []
tmp = 0
for a in an:
    tmp += a
    sum_an.append(tmp)

c = 0
before_positive = sum_an[0] <= 0
for i in range(n):
    if before_positive and sum_an[i] >= 0:
        p = abs(sum_an[i]) + 1
        c += p
        for j in range(i, n):
            sum_an[j] -= p
        before_positive = False
    elif not before_positive and sum_an[i] <= 0:
        p = abs(sum_an[i]) + 1
        c += p
        for j in range(i, n):
            sum_an[j] += p
        before_positive = True
    else:
        before_positive = not before_positive

print(c)


### FIXED CODE ###

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

c1 = 0
c2 = 0
sum1 = 0 # 偶数番目が正
sum2 = 0 # 奇数番目が正
for i in range(n):
    sum1 += an[i]
    sum2 += an[i]
    if i%2 == 0:
        if sum1 <= 0:
            p = abs(sum1) + 1
            c1 += p
            sum1 += p
        if sum2 >= 0:
            p = abs(sum2) + 1
            c2 += p
            sum2 -= p
    else:
        if sum1 >= 0:
            p = abs(sum1) + 1
            c1 += p
            sum1 -= p
        if sum2 <= 0:
            p = abs(sum2) + 1
            c2 += p
            sum2 += p

print(min(c1, c2))
### BUGGY CODE ###

import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
a = map(int, readline().split())
b = list(map(int, readline().split()))
b.sort(reverse=True)

x = len(b)
c = [(k, len(list(L))) for k, L in groupby(b)]
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for vv in c[i+1:]:
    if not v[0] % vv[0]:
      x -= 1
      break
print(x)

### FIXED CODE ###

import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort()
# print(b)

x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]
# print(c)
m = c[-1][0]
# print(m)
s = [True] * (m + 1)
# print(len(s))

a = 0
for i, le in c:
  if s[i]:
    if le <= 1:
      a += 1
    for v in range(i, m + 1, i):
      s[v] = False
# print(s)
print(a)
### BUGGY CODE ###

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

ans = A
for i in range(A + 1, B + 1):
    ans = ans ^ i
print(ans)


### FIXED CODE ###

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


def F(C):
    num = (C + 1) // 2
    if C % 2 == 0:
        if num % 2 == 0:
            return C
        else:
            return 1 ^ C
    else:
        if num % 2 == 0:
            return 0
        else:
            return 1


print(F(A - 1) ^ F(B))

print()
### BUGGY CODE ###

def warshall_floyd(N, A):
    dist = [[A[i][j] for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = warshall_floyd(N, A)
    edges = list()
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((A[i][j], i, j))  # (cost, from, to)
    edges.sort(key=lambda e: e[0])
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        if A[from_node][to_node] > wf[from_node][to_node]:
            print(-1)
            return
        to_be_added = True
        for via_node in range(N):
            if via_node in [from_node, to_node]:
                continue
            if wf[from_node][to_node] == wf[from_node][via_node] + wf[via_node][to_node]:
                to_be_added = False
                break
        if to_be_added:
            ans += A[from_node][to_node]
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def main():
    INF = 10**12
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    for i in range(N):
        A[i][i] = INF
        wf[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans // 2))


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

n = int(input())
a = list(map(int, input().split()))
p =[]
for i in range(n) :
    p.append([i+1,a[i]])

p.sort(key=lambda x: x[1])
r = ''
q = [x[0] for x in p]
for i in range(n) :
    r = r + ' ' + str(q[i])

print (r)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
p =[]
for i in range(n) :
    p.append([i+1,a[i]])

p.sort(key=lambda x: x[1])
q = list(map(str,[x[0] for x in p]))
r = ' '.join(q)


print (r)