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

n,x,y=list(map(int,input().split()))

x-=1
y-=1
ans=[0 for i in range(n)]
for i in range(n):
    d=[100000 for i in range(n)]
    d[i]=0
    q=[]
    q.append(i)
    while q:
        p=q.pop()
        if(p-1>=0 and d[p]+1<d[p-1]):
            q.append(p-1)
            d[p-1]=d[p]+1
        if(p+1<n and d[p]+1<d[p+1]):
            q.append(p+1)
            d[p+1]=d[p]+1

        if(p==x and d[x]+1<d[y]):
            q.append(y)
            d[y]=d[x]+1
        if(p==y and d[y]+1<d[x]):
            q.append(x)
            d[x]=d[y]+1

    for j in range(1,n):
        ans[j]+=d.count(j)

for i in range(1,n):
    print(ans[i]//2)

### FIXED CODE ###

n,x,y=map(int,input().split())
x-=1
y-=1
d=[10000 for i in range(n)]
ans=[0 for i in range(n)]
for i in range(n):
    for j in range(i,n):
        m=min(abs(i-j),abs(x-i)+abs(y-j)+1,abs(y-i)+abs(x-j)+1)
        ans[m]+=1

for i in range(1,n):
    print(ans[i])
### BUGGY CODE ###

N, M = map(int, input().split())
m = set(range(N))
for i in range(M):
	L, R = map(int, input().split())
	_m = set(range(L-1, R))
	m = m & _m
print(len(m))


### FIXED CODE ###

N, M = map(int, input().split())
L, R = 0, N
for i in range(M):
	_L, _R = map(int, input().split())
	L = max(_L, L)
	R = min(_R, R)

print(max(R - L + 1, 0))
### BUGGY CODE ###

import sys
from collections import deque

N, Q = list(map(int, input().split()))
E = {}

# change limit for deep tree (recursion)
sys.setrecursionlimit(int(2e5+10))

for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1,b-1 # 1-indexed -> 0-indexed
  if a not in E:
    E[a] = [b]
  else:
    E[a].append(b)
  if b not in E:
    E[b] = [a]
  else:
    E[b].append(a)

P = [0] * N
for i in range(Q):
  a,b= list(map(int, input().split()))
  P[a-1] += b # 1-indexed -> 0-indexed
  
#print(E)
#print(P)

visited = [False for i in range(N)]
d = deque()

d.append(0)
while len(d) > 0:
  parent = d.pop()
  visited[parent] = True
  
  next_point = E[parent]
  
  for child in next_point:
    if visited[child]:
      continue
    P[child] += P[parent]
    d.append(child)
  
print(" ".join(list(map(str,P))))

### FIXED CODE ###

import sys
from collections import deque

N, Q = list(map(int, input().split()))
E = {}

# change limit for deep tree (recursion)
sys.setrecursionlimit(int(2e5+10))

for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1,b-1 # 1-indexed -> 0-indexed
  if a not in E:
    E[a] = [b]
  else:
    E[a].append(b)
  if b not in E:
    E[b] = [a]
  else:
    E[b].append(a)

P = [0] * N
for i in range(Q):
  a,b= list(map(int, input().split()))
  P[a-1] += b # 1-indexed -> 0-indexed
  
#print(E)
#print(P)

visited = [False for i in range(N)]
d = deque()

d.append(0)
while len(d) > 0:
  parent = d.pop()
  visited[parent] = True
  
  next_point = E[parent]
  
  for child in next_point:
    if visited[child]:
      continue
    P[child] += P[parent]
    d.append(child)
  
print(" ".join(list(map(str,P))))
### BUGGY CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
xyc = list(list(map(int, input().split())) for _ in range(M))
l1 = []
lx = []
ly = []
for i in range(100001):
    l1.append(list(c for x, y, c in xyc))
min_a = min(a)
min_b = min(b)
max_l1 = max(list(map(int, max(l1))))
for k in range(M):
    lx.append(list(x for x, y, c in xyc))
    ly.append(list(y for x, y, c in xyc))
    j = lx[0][k]
    p = ly[0][k]
    ans = min((min_a + min_b), ((a[j - 1] + b[p - 1]) - max_l1))
print(ans)

### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = min(a) + min(b)
for k in range(M):
    x, y, c = map(int, input().split())
    ans = min(ans, ((a[x - 1] + b[y - 1]) - c))
print(ans)
### BUGGY CODE ###

N=int(input())
S=[]
for i in range(N):
  s=str(input())
  s_list=sorted(list(s))
  S +=[s_list]

count=0
for i in range(N-1):
  for j in range(i+1,N):
    if S[i]==S[j]:
      count +=1
print(count)

### FIXED CODE ###

from collections import defaultdict
N=int(input())
S={}
S_counter = defaultdict(int)
count=0
for i in range(N):
  s="".join(sorted(input()))
  if s in S:
    count += S[s]
    S[s] += 1
  else:
    dict={s:1}
    S.update(dict)
print(count)
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
num = []
if d < 0 and a > 0:
  print(a * d)
elif d > 0 and a > 0:
  print(b * d)
else:
  num = []
  for i in range(a, b + 1):
    for j in range(c, d + 1):
      num.append(i * j)
  print(max(num))

### FIXED CODE ###

a, b, c, d = map(int, input().split())
num = [a*c, a*d, b*c, b*d]
print(max(num))
### BUGGY CODE ###

from time import time
from random import randint
now = time()

MAX = 26

d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
t = [i % MAX + 1 for i in range(d)]

last = [0] * MAX

score = 0
for day, e in enumerate(t, 1):
    score += s[day-1][e-1]
    last[e-1] = day

    for ec, elast in zip(c, last):
        score -= ec * (day - elast)

while time() - now <= 1.9:
    prev_score = score

    ed = randint(1, d)
    eq = randint(1, MAX)

    q_old = t[ed-1]
    d_prev = {q_old: 0, eq: 0}

    c_old = c[q_old-1]
    c_new = c[eq-1]

    for day, e in enumerate(t, 1):
        if e in d_prev.keys():
            d_prev[e] = day

        score += c_old * (day - d_prev[q_old])
        score += c_new * (day - d_prev[eq])

    score -= s[ed-1][q_old-1]
    score += s[ed-1][eq-1]

    t[ed-1] = eq

    d_prev = {q_old: 0, eq: 0}

    for day, e in enumerate(t, 1):
        if e in d_prev.keys():
            d_prev[e] = day

        score -= c_old * (day - d_prev[q_old])
        score -= c_new * (day - d_prev[eq])

    if prev_score > score:
        t[ed-1] = q_old
        score = prev_score

print(*t, sep="\n")


### FIXED CODE ###

for i in range(365):
    print(i % 26 + 1)
### BUGGY CODE ###

import math
n=int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def check(x,y):
    if float.is_integer(math.sqrt(x)) and float.is_integer(math.sqrt(y)):
        return True

x,y=0,0
maxs=10**9
for i in range(1, int(n**0.5)+1):
    if n % i == 0:
        if maxs>=i and maxs>=n//i:
            x=i
            y=n//i
            break
print("0 0 0 "+str(x)+" "+str(y)+" 0")

### FIXED CODE ###

import math
n=int(input())
x1,y1=0,0
x2,y2=10**9,1
y3 = n//x2 +1
if y3>x2:
    y3=x2
x3 = y3*x2 - n


output=[x1,y1,x2,y2,x3,y3]
output=list(map(str,output))
    
print(" ".join(output))
### BUGGY CODE ###

N,Q=map(int,raw_input().split())
C=set(map(int,raw_input().split()))
for i in range(Q):
    q=input()
    print max(map(lambda x:x%q,C))

### FIXED CODE ###

N,Q=map(int,raw_input().split())
A=map(int,raw_input().split())
maxA=max(A)
T=[0]*(maxA+2)
for i in A:
    T[i]=1
L=[0]*(maxA+2)
num=0
for i in range(maxA+2):
    L[i]=num
    if T[i]==1:
        num=i
for i in range(Q):
    q=input()
    maxv=0
    cur=maxA
    while True:
        p=cur%q
        maxv=max(maxv,p)
        if cur-p<=0: break
        cur=L[cur-p]
    print maxv
### BUGGY CODE ###

from fractions import gcd
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return divisors
  
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
 
A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)

### FIXED CODE ###

from fractions import gcd
 
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
 
    # divisors.sort()
    return divisors
  
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, int(n**0.5)+1):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
 
A,B = list(map(int,input().split()))
 
aaa = []
 
aaa = make_divisors(gcd(A,B))
        
count = 0
 
for i in range(len(aaa)):
    if isPrime(aaa[i]) == True:
        count += 1
        
print(count+1)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A.insert(0, 0)

    ans = 0
    for i in range(1, N+1):
        for j in range(A[i]+i+1, N+1):
            if j - i == A[j] + A[i]:
                ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

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

    mp = dict()
    ans = 0
    for i in range(N):
        x = i - A[i]
        ans += mp.get(x, 0)
        y = A[i] + i
        mp[y] = mp.get(y, 0) + 1
    print(ans)

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

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

for t in T:
    if t in D:
        D.remove(t)
    else:
        print("NO")
        break
        
else:
    print("YES")

### FIXED CODE ###

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

D = sorted(D)
T = sorted(T)


i = len(D)-1
j = len(T)-1

flag = True
while(0<=i and 0<=j):
    if D[i] > T[j]:
        i -= 1
    elif D[i] == T[j]:
        i -= 1
        j -= 1
    else:
        flag = False
        break
        
if flag == False or (i<=-1 and j>-1):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

spot_num = int(input())
spot_place = [ int(p) for p in input().split(" ") ]

for i in range(spot_num):
  total_price = 0
  current_place = 0

  for j in range(spot_num):
    if i == j:
      continue
    total_price += abs(spot_place[j] - current_place)
    current_place = spot_place[j]

  print(total_price + abs(0 - current_place))

### FIXED CODE ###

spot_num = int(input())
spot_place = [ int(p) for p in input().split(" ") ]
diff_table = []
max_num = 0

for i in range(spot_num):
  if i == 0:
    max_num += abs(spot_place[0] - 0)
    diff_table.append(abs(spot_place[1] - 0) - \
    (abs(spot_place[0] - 0) + abs(spot_place[1] - spot_place[0])))
  elif i == spot_num-1:
    diff_table.append(abs(0 - spot_place[i-1]) - \
    (abs(spot_place[i] - spot_place[i-1]) + abs(0 - spot_place[i])))
    max_num += abs(spot_place[i] - spot_place[i-1])
  else:
    diff_table.append(abs(spot_place[i+1] - spot_place[i-1]) - \
    (abs(spot_place[i] - spot_place[i-1]) + abs(spot_place[i+1] - spot_place[i])))
    max_num += abs(spot_place[i] - spot_place[i-1])
    
max_num += abs(0 - spot_place[spot_num-1])

for i in range(spot_num):
  print(max_num+diff_table[i])
### BUGGY CODE ###

# coding: utf-8

S = input()
Q = int(input())


rev = False
for _ in range(Q):
    line = input()

    if line[0] == "1":
        rev = not rev

    else:
        if line[2] == "1":
            if rev:
                S = "".join([S, line[4]])
            else:
                S = "".join([line[4], S])
        else:
            if rev:
                S = "".join([line[4], S])
            else:
                S = "".join([S, line[4]])

if rev:
    print(S[::-1])
else:
    print(S)


### FIXED CODE ###

# coding: utf-8

S = input()
Q = int(input())


heads = {}
tails = {}
h = 0
t = 0
rev = False
for _ in range(Q):
    line = input()

    if line[0] == "1":
        rev = not rev

    else:
        if line[2] == "1":
            if rev:
                # S = "".join([S, line[4]])
                tails[t] = line[4]
                t += 1
            else:
                # S = "".join([line[4], S])
                heads[h] = line[4]
                h += 1
        else:
            if rev:
                # S = "".join([line[4], S])
                heads[h] = line[4]
                h += 1
            else:
                # S = "".join([S, line[4]])
                tails[t] = line[4]
                t += 1

head = [None] * h
tail = [None] * t

for i in range(h):
    head[i] = heads[i]
head = head[::-1]

for i in range(t):
    tail[i] = tails[i]

head_joint = "".join(head)
tail_joint = "".join(tail)
joint = "".join([head_joint, S, tail_joint])

if rev:
    print(joint[::-1])
else:
    print(joint)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]

def count_cb_ob(s):
    st = []
    for i, si in enumerate(s):
        if si == '(' or len(st) == 0 or st[-1] != '(':
            st.append(si)
        else:
            st.pop()
    return st.count(')'), st.count('(')

cb_obs = list(map(count_cb_ob, S))
f = list(filter(lambda cb_ob: cb_ob[0] < cb_ob[1] , cb_obs))
b = list(filter(lambda cb_ob: cb_ob[0] > cb_ob[1] , cb_obs))
s = list(filter(lambda cb_ob: cb_ob[0] == cb_ob[1] , cb_obs))

f = sorted(f)
b = sorted(b, key=lambda x:x[1], reverse=True)

count = 0
ans = 'Yes'
for down, up in (*f, *s, *b):
    count -= down
    if count < 0:
        ans = 'No'
    count += up

if count != 0:
    print('No')
else:
    print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

N = int(readline())
S = [readline().rstrip().decode() for _ in range(N)]

def count_cb_ob(s):
    st = []
    for i, si in enumerate(s):
        if si == '(' or len(st) == 0 or st[-1] != '(':
            st.append(si)
        else:
            st.pop()
    return st.count(')'), st.count('(')

cb_obs = list(map(count_cb_ob, S))
f = list(filter(lambda cb_ob: cb_ob[0] < cb_ob[1] , cb_obs))
b = list(filter(lambda cb_ob: cb_ob[0] > cb_ob[1] , cb_obs))
s = list(filter(lambda cb_ob: cb_ob[0] == cb_ob[1] , cb_obs))

f = sorted(f)
b = sorted(b, key=lambda x:x[1], reverse=True)

count = 0
ans = 'Yes'
for down, up in (*f, *s, *b):
    count -= down
    if count < 0:
        ans = 'No'
    count += up

if count != 0:
    print('No')
else:
    print(ans)
### BUGGY CODE ###

def main():
    input()
    array = [int(x) for x in input().split()]
    counting_dict = {}
    for val in array:
        if val not in counting_dict:
            counting_dict[val] = [1, 0]
        count = 0
        for key in counting_dict.keys():
            if key > val:
                count += counting_dict[key][0]
        counting_dict[val][1] += count

    swaps = 0
    for value in counting_dict.values():
        swaps += value[1]
    print(swaps)

    return

main()


### FIXED CODE ###

import sys
time_check = False
if time_check:
    import time

num_of_inversions = 0
array = [0 for x in range(200000)]

def merge(left, mid, right):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = array[left:left + n_fore]
    l_fore.append(sys.maxsize)
    l_rear = array[mid:mid + n_rear]
    l_rear.append(sys.maxsize)

    i = j = 0
    global num_of_inversions

    offset = len(l_fore) - 1 + left
    for k in range(left, right):
        if l_fore[i] < l_rear[j]:
            array[k] = l_fore[i]
            i += 1
        else:
            array[k] = l_rear[j]
            num_of_inversions += j - k + offset
            #print(l_fore,l_rear, array[:23])
            #print(num_of_inversions,len(l_fore),len(l_rear),i,j,k)
            j += 1


def merge_sort(left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)
    return


def main():

    n = int(input())
    for idx, value in enumerate(input().split()):
        array[idx] = int(value)

    if time_check:
        start = time.time()

    merge_sort(0, n)

    if time_check:
        print("elapsed_time:", time.time() - start)

    #print(" ".join(map(str, array[:n])))
    print(num_of_inversions)

    return


main()
### BUGGY CODE ###

from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - 1
    for f in frd[i]:
        if uni[i] == uni[f]: ans -= 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

### FIXED CODE ###

from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - 1
    for f in frd[i]:
        if uni[i] == uni[f]: ans -= 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")
### BUGGY CODE ###

h, w = map(int,input().split())
way = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == ".":
            way.append(i*w+j)
wayn = len(way)
mat = 0

for i in way:
    al = [i]
    time = 0
    pp = [i]
    while not len(al) == wayn:
        np = [j for j in pp]
        pp = []
        for j in np:
            if j%w < w-1 and j+1 in way and (not j+1 in al) and (not j+1 in pp):
                pp.append(j+1)
                al.append(j+1)
            if j%w > 0 and j-1 in way and (not j-1 in al) and (not j-1 in pp):
                pp.append(j-1)
                al.append(j-1)
            if j//w < h-1 and j+w in way and (not j+w in al) and (not j+w in pp):
                pp.append(j+w)
                al.append(j+w)
            if j//w > 0 and j-w in way and (not j-w in al) and (not j-w in pp):
                pp.append(j-w)
                al.append(j-w)
        time += 1
    if time > mat:
        mat = time

print(mat)


### FIXED CODE ###

import queue
h, w = map(int,input().split())
way = ["" for i in range(h+1)]
way[h] = "#"*(w+1)
for i in range(h):
    way[i] = str(input())+"#"
G = [[[] for j in range(w)] for i in range(h)]
road = []
for i in range(h):
    for j in range(w):
        if way[i][j] == "#":
            continue
        else:
            road.append([i,j])
        if way[i+1][j] == ".":
            G[i][j].append([i+1,j])
        if way[i-1][j] == ".":
            G[i][j].append([i-1,j])
        if way[i][j+1] == ".":
            G[i][j].append([i,j+1])
        if way[i][j-1] == ".":
            G[i][j].append([i,j-1])
M = 0

for i in road:
    q = queue.Queue()
    q.put(i)
    t = [[-1 for k in range(w+1)] for j in range(h+1)]
    t[i[0]][i[1]] = 0
    while not q.empty():
        j = q.get()
        for l in G[j[0]][j[1]]:
            if t[l[0]][l[1]] == -1:
                t[l[0]][l[1]] = t[j[0]][j[1]] + 1
                q.put(l)
    for k in t:
        if M < max(k):
            M = max(k)

print(M)
### BUGGY CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect
from scipy.sparse.csgraph import shortest_path
import numpy as np

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

result, path = shortest_path(np.array(A), return_predecessors=True)
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))


### FIXED CODE ###

import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    info = copy.deepcopy(d)
    for i in range(len(info)):
        for l in range(len(info)):
            for k in range(len(info)):
                info[l][k] = min(info[l][k], info[l][i] + info[i][k])
    return info


MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

result = warshall_floyd(A)
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))
### BUGGY CODE ###

n = int(input())
a =[int(x) for x in input().split()]
ans = 0
ans2 = 0
mod = 10**9 + 7
ans_list = []
for index,i in enumerate(a):
    for j in a[index+1:]:
        ans += (i *j)%mod

print(ans%mod)

### FIXED CODE ###

n = int(input())
a_list =[int(x) for x in input().split()]
mod = 10**9 + 7

s_list = [0]*(n+1)
for i,a in enumerate(a_list):
    s_list[i+1] = s_list[i]+a


ans = 0
for i,a in enumerate(a_list):
    ans += a * (s_list[n]-s_list[i+1])
    
print(ans%mod)
### BUGGY CODE ###

from itertools import permutations
n,m,q=map(int,input().split())
a=[]
for i in range(q):
  a.append(list(map(int,input().split())))
ans=0
data=set([''.join(list(i)) for i in list(permutations('1'*(m-1)+'0'*n))])
for i in data:
  s=[1]*(n+1)
  cnt=0
  k=0
  for j in range(n+m-1):
    if i[j]=='1':s[k]+=1
    else:
      s[k+1]=s[k]
      k+=1
  for x,y,z,w in a:
    if s[y-1]-s[x-1]==z:cnt+=w
  ans=max(ans,cnt)
print(ans)

### FIXED CODE ###

n,m,q=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i in range(1<<(m+n)):
  a=[1]
  for j in range(m+n):
    if (i>>j)&1:a[-1]+=1
    else:a+=[a[-1]]
    if a[-1]>m:
      flag=0
      break
    if len(a)>n:
      flag=1
      break
  else:flag=1
  if flag==0 or len(a)<n:continue
  cnt=0
  for s,t,u,v in e:
    if a[t-1]-a[s-1]==u:cnt+=v
  ans=max(ans,cnt)
print(ans)
### BUGGY CODE ###

s = input()
l = len(s)
lst = [None for i in range(l)]
lst[0] = int(s[0])
for i in range(l-1):
    lst[i+1] = lst[i]+int(s[i+1])
lst = [0]+lst
# print(lst)

ans = 0
for i in range(l):
    for j in range(i,l):
        if (lst[j+1]-lst[i])%3==0:
            if int(s[i:j+1])%673==0:
                ans += 1

print(ans)

### FIXED CODE ###

from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(pow(10,n-i-1,mod)))%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

ans = 0
for i in arr.values():
    ans += i*(i-1)//2
print(ans)