Harryxun/stf_run huggingface dataset:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def coprime(a, b):
    return gcd(a, b) == 1

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

A,B=map(int, input().split())
if (A==1)or(B==1)or(coprime(A,B)):
  print(1)
else:
  A=make_divisors(A)
  B=make_divisors(B)
  C=list(set(A)&set(B))
  C=C.sort(reverse=True)
  count=0
  for i in range(len(C)):
    for j in range(i+1,len(C)):
      if (C[j]!=1)and(C[i]%C[j]==0):
        count=count+1
        break
  print(len(C)-count)

### FIXED CODE ###

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

def coprime(a, b):
    return gcd(a, b) == 1

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

A,B=map(int, input().split())
if (A==1)or(B==1)or(coprime(A,B)):
  print(1)
else:
  A=make_divisors(A)
  B=make_divisors(B)
  C=list(set(A)&set(B))
  C.sort(reverse=True)
  count=0
  for i in range(len(C)):
    for j in range(i+1,len(C)):
      if (C[j]!=1)and(C[i]%C[j]==0):
        count=count+1
        break
  print(len(C)-count)
n = int(input())
ai = [int(x) for x in input().split()]

ai.sort()

temp = [abs(x) for x in ai[1:-1]]

o1 = -ai[0] + sum(temp) + ai[-1]

print(o1)

temp1 = ai.pop(-1)
num_p = sum(x >= 0 for x in ai)
if num_p is len(ai):
  num_p = len(ai) - 1
for i in range(num_p):
  temp2 = ai.pop(-1)
  temp3 = ai[0]
  print(temp3, temp2)
  ai[0] = temp3 -temp2

for i in range(len(ai)):
  temp2 = ai.pop(0)
  print(temp1, temp2)
  temp1 = temp1 - temp2


### FIXED CODE ###

n = int(input())
ai = [int(x) for x in input().split()]

ai.sort()

temp = [abs(x) for x in ai[1:-1]]

o1 = -ai[0] + sum(temp) + ai[-1]

print(o1)

temp1 = ai.pop(-1)
num_p = sum(x >= 0 for x in ai)
if num_p == len(ai):
  num_p -= 1
for i in range(num_p):
  temp2 = ai.pop(-1)
  print(ai[0], temp2)
  ai[0] -= temp2

for i in range(len(ai)):
  temp2 = ai.pop(0)
  print(temp1, temp2)
  temp1 -= temp2
A, B, C, D = map(int, input())

if A + B > C + D:
    print('Left')
elif A + B == C + D:
    print('Balanced')
else:
    print('Right')

### FIXED CODE ###

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

if A + B > C + D:
    print('Left')
elif A + B == C + D:
    print('Balanced')
else:
    print('Right')
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    if N % 2 == 0:
        used = [False] * (N + 1)
        i = 0
        span = 1
        cnt = 0
        while cnt < M:
            cnt += 1
            while used[i]:
                i += 1
            print(i + 1, i + 1 + span)
            used[i] = True
            used[i + span] = True
            span += 1
    else:
        for i in range(M):
            print(i + 1, N - i)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    if N % 2 == 0:
        for i in range(M):
            x = i + 1
            y = N - i - 1
            if y - x > (N - y + x):
                print(x, y)
            else:
                print(x, y - 1)
    else:
        for i in range(M):
            print(i + 1, N - i)


if __name__ == "__main__":
    main()
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, L] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    A = [int(input_raw[i]) for i in range(N)]
    B = deque([A[i] + A[i + 1] for i in range(N - 1)])
    sumA = sum(A)
    s_idx = 1
    t_idx = len(B)
    seq = []
    for i in range(N - 1):
        if sumA < L:
            print "Impossible"
            return
        if B[len(B) - 1] < L:
            B.pop()
            sumA -= A[t_idx]
            seq.append(t_idx)
            t_idx += 1

        else :
            B.popleft()
            sumA -= A[s_idx - 1]
            seq.append(s_idx)
            s_idx += 1
        if len(seq) == N - 1:
            break

    print "Possible"
    for i in range(len(seq)):
        print seq[i]





if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, L] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = read_func().strip().split()
    A = [int(input_raw[i]) for i in range(N)]
    B = deque([A[i] + A[i + 1] for i in range(N - 1)])
    sumA = sum(A)
    s_idx = 1
    t_idx = len(B)
    seq = []
    for i in range(N - 1):
        if sumA < L:
            print "Impossible"
            return
        if B[len(B) - 1] < L:
            B.pop()
            sumA -= A[t_idx]
            seq.append(t_idx)
            t_idx -= 1

        else :
            B.popleft()
            sumA -= A[s_idx - 1]
            seq.append(s_idx)
            s_idx += 1
        if len(seq) == N - 1:
            break

    print "Possible"
    for i in range(len(seq)):
        print seq[i]





if __name__ == '__main__':
    main()
a,b = map(int, raw_input().split())
d = a / b
r = a % b
f = float(a) / float(b)
print " ".join([str(d), str(r), str('%.5f'.float(f))])

### FIXED CODE ###

a,b = map(int, raw_input().split())
d = a / b
r = a % b
f = float(a) / float(b)
print " ".join([str(d), str(r), str('%.5f' % f)])
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    X = [0 for _ in range(N)]
    Y = [0 for _ in range(N)]
    for i in range(N):
        x, y = map(int, input().split())
        X[i] = x
        Y[i] = y

    cnt = {}
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            rx = X[i] - X[j]
            ry = Y[i] - Y[j]
            if (rx, ry) not in cnt:
                cnt[(rx, ry)] = 1
            else:
                cnt[(rx, ry)] += 1
            if (-rx, -ry) not in cnt:
                cnt[(-rx, -ry)] = 1
            else:
                cnt[(-rx, -ry)] += 1

    cnt = [[v, k] for k, v in cnt.items()]
    cnt.sort(reverse=True)
    res = N - cnt[0][0] // 2
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())

    if N == 1:
        return print(1)

    X = [0 for _ in range(N)]
    Y = [0 for _ in range(N)]
    for i in range(N):
        x, y = map(int, input().split())
        X[i] = x
        Y[i] = y

    cnt = {}
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            rx = X[i] - X[j]
            ry = Y[i] - Y[j]
            if (rx, ry) not in cnt:
                cnt[(rx, ry)] = 1
            else:
                cnt[(rx, ry)] += 1
            if (-rx, -ry) not in cnt:
                cnt[(-rx, -ry)] = 1
            else:
                cnt[(-rx, -ry)] += 1

    cnt = [[v, k] for k, v in cnt.items()]
    cnt.sort(reverse=True)
    res = N - cnt[0][0] // 2
    print(res)


if __name__ == '__main__':
    main()
[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)

### FIXED CODE ###

[x,y]=list(map(int,input().split()))
if ((x%3)+(y%3))%3!=0:
	print(0)
else:
	n=int((x+y)/3)
	r=y-n
	if r<0 or r>n:
		print(0)
	else:
		if r>n-r:
			r=n-r
		mod=1000000007
		kaijo=[1]
		for i in range(1,n+1):
			kaijo.append(kaijo[-1]*i%mod) #これで、kaijo[i]=i!となる。
		gyakugen=[pow(kaijo[n-r],mod-2,mod)]
		for i in reversed(range(1,n-r+1)):
			gyakugen.append(gyakugen[-1]*i%mod) #これで、gyakugen[i]=n-r-iの逆元となる
		kotae=kaijo[n]*gyakugen[0]*gyakugen[n-2*r]%mod

		print(kotae)
n = input()
list = []

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

list.sort(key=lambda x:(x[0],x[1]))
for l in list:
    print(l[0])


### FIXED CODE ###


n = int(input())
list = []

for i in range(n):
    sp = input().split()
    s = str(sp[0])
    p = int(sp[1])
    list.append([i+1, s, p])

list.sort(key=lambda x:(x[1],-x[2]))
for l in list:
    print(l[0])
import sys
sys.setrecursionlimit(10 ** 6)

def is_bipartite(v, r, d):
    color[v] = d
    for u in E[v]:
        if u == r:
            continue
        if color[u] == d:
            return False
        is_bipartite(u, v, (d + 1) % 2)
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
color = [-1] * N

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

if is_bipartite(0, -1, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def is_bipartite(v, d):
    color[v] = d
    for u in E[v]:
        if color[u] == d:
            return False
        elif color[u] != -1:
            continue
        if not is_bipartite(u, (d + 1) % 2):
            return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
color = [-1] * N

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

if is_bipartite(0, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)
import itertools

n,m=map(int, input().split()) 
ab=[list(map(int, input().split())) for _ in range(m)]
#ab=Input.split()
#d：隣接行列
print(ab)
print(type(ab))
d = [[] for i in range(n)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    
#per：順列列挙
per= list(itertools.permutations(range(1,n)))
cnt=0
for i in range(len(graph)):
    x = [0]+per[i]
    for j in range(n):
        #隣接していなければ終了
        if not x[j+1] in d[x[j]]:
            break
        cnt+=1
print(cnt)
        

### FIXED CODE ###

import itertools

n,m=map(int, input().split()) 
ab=[list(map(int, input().split())) for _ in range(m)]
#ab=Input.split()
#d：隣接行列

d = [[] for i in range(n)]
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    d[a-1].append(b-1)
    d[b-1].append(a-1)
    
#per：順列列挙
per= itertools.permutations(range(1,n))
ans=0
for i in per:
    cnt=1
    x = [0]+list(i)
    for j in range(1,n):
        #隣接していなければ終了
        if not x[j] in d[x[j-1]]:
            break
        else:
            cnt+=1
    if(cnt==n):
        ans+=1
print(ans)
def main():
    S = input()
    N = len(S)
    from collections import Counter
    c = Counter(S)
    # print(c.most_common())
    if N == 3 and c.most_common()[0][1] >= (N+1)//2:
        print("NO")
    elif c.most_common()[0][1] > (N+1)//2 or \
            (c.most_common()[0][1] >= (N+1)//2 and c.most_common()[1][1] >= (N+1)//2):
        print("NO")
    else:
        print("YES")


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = input()
    N = len(S)
    a = S.count("a")
    b = S.count("b")
    c = S.count("c")
    ma = max(a, b, c)
    mi = min(a, b, c)
    if ma - mi > 1:
        print("NO")
    else:
        print("YES")


if __name__ == '__main__':
    main()
def resolve():

    N=int(input())
    A=sorted(list(map(int,input().split())),reverse=True)
    temp=-1
    maxans=0
    AA=Counter(A)
    for (i,j) in AA.items():
        if j>=4:
            maxans=max(i**2,maxans)
        if j>=2:
            if temp>=0:
                maxans=max(maxans,temp*i)
            temp=max(i,temp)
    print(maxans)




resolve()

### FIXED CODE ###

# import bisect
from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# from operator import xor
import sys

sys.setrecursionlimit(10 ** 5 + 10)


# input = sys.stdin.readline

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

    AA = Counter(A).most_common()

    ls = []
    for i in range(len(AA)):
        if AA[i][1] >= 2:
            ls.append(AA[i])
        else:
            break

    ls=sorted(ls, key=lambda x: x[0])

    try:
        ans = ls[-1][0] * ls[-2][0]
        for i in reversed(range(len(ls))):
            if ls[i][1] >= 4:
                ans = max(ans, ls[i][0] ** 2)
        print(ans)
    except:
        print(0)


resolve()
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        repn[u - 1].append((v - 1, w))
        repn[v - 1].append((u - 1, w))
    
    """
    Greedyに隣接する頂点ごとに色を塗っていけばよい
    """

    color = [-1] * N
    color[0] = 0
    q = [0]
    while q:
        v = q.pop()
        for u, w in repn[v]:
            if color[u] != -1:
                continue
            if w % 2 == 0:
                color[u] = color[v]
            else:
                color[u] = (1 + color[v]) % 2
            q.append(u)
    for ans in color:
        print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v, w = map(int, input().split())
        repn[u - 1].append((v - 1, w))
        repn[v - 1].append((u - 1, w))
    
    """
    Greedyに隣接する頂点ごとに色を塗っていけばよい
    """

    color = [-1] * N
    color[0] = 0
    q = [0]
    while q:
        v = q.pop()
        for u, w in repn[v]:
            if color[u] != -1:
                continue
            if w % 2 == 0:
                color[u] = color[v]
            else:
                color[u] = (1 + color[v]) % 2
            q.append(u)
    for ans in color:
        print(ans)


if __name__ == "__main__":
    main()
n,x,=map(int, input().split())
w = list(map(int, input().split()))

d=0
if(x==0):
print(0)
else:
    for i in range(n):
        d=d+w[i]
        if(d>x):
            break
        if(d>=10000):
            break
   
    print(i+1)


### FIXED CODE ###

n,x = map(int,input().split())
li = list(map(int,input().split()))
 
ans = 1
now = 0
 
for i in li:
    now += i
    if now <= x:
        ans += 1
    else:
        break
 
print(ans)
# -*- coding: utf-8 -*-

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

if A*B >= C*D:
    print(A*B)
else:
    print(C*D)



### FIXED CODE ###

# -*- coding: utf-8 -*-

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

if A*B >= C*D:
    print(A*B)
else:
    print(C*D)
H, W = map(int, input().split())
S = [input() for _ in range(H)]
newS = [['#']*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            c = max(0, j-1)
            d = min(W-1, j+1)
            if i == 0:
                cnt = S[i][c:d+1].count('#')
                cnt += S[i+1][c:d+1].count('#')
            elif i == H-1:
                cnt = S[i][c:d+1].count('#')
                cnt += S[i-1][c:d+1].count('#')
            else:
                cnt = S[i][c:d+1].count('#')
                cnt += S[i-1][c:d+1].count('#')
                cnt += S[i+1][c:d+1].count('#')
            newS[i][j] = str(cnt)
for i in newS:
    print(''.join(i))


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ad = ['.' for _ in range(W)]
S.append(ad)
S.insert(0, ad)
newS = [['#' for _ in range(W)] for _ in range(H)]
for i in range(1, H+1):
    for j in range(W):
        if S[i][j] == '.':
            c = max(0, j-1)
            d = min(W-1, j+1)
            cnt = S[i][c:d+1].count('#')
            cnt += S[i-1][c:d+1].count('#')
            cnt += S[i+1][c:d+1].count('#')
            newS[i-1][j] = str(cnt)
for i in newS:
    print(''.join(i))
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

path = [list() for _ in range(N+1)]
for i in range(N-1):
    a, b = ab[i][0], ab[i][1]
    path[a].append([b, i])
    path[b].append([a, i])

color_max = 0
color_list = [0]*(N-1)
visit = [False]*(N+1)
visit[1] = True
def dfs(node, color, used_path):
    global visit
    nxt_color = 0
    for nxt in path[node]:
        nxt_node = nxt[0]
        use_path = nxt[1]
        if visit[nxt_node] == False:
            visit[nxt_node] = True
            nxt_color += 1
            if nxt_color == color:
                nxt_color += 1
            dfs(nxt_node, nxt_color, use_path)
    
    global color_list
    if used_path != -1:
        color_list[used_path] = color

dfs(1, 0, -1)


for c in color_list:
    color_max = max(c, color_max)
print(color_max)
print("\n".join(map(str, color_list)))
            

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

path = [list() for _ in range(N+1)]
for i in range(N-1):
    a, b = ab[i][0], ab[i][1]
    path[a].append([b, i])
    path[b].append([a, i])

color_max = 0
color_list = [0]*(N-1)
visit = [False]*(N+1)
visit[1] = True
def dfs(node, color, used_path):
    global visit
    nxt_color = 0
    for nxt in path[node]:
        nxt_node = nxt[0]
        use_path = nxt[1]
        if visit[nxt_node] == False:
            visit[nxt_node] = True
            nxt_color += 1
            if nxt_color == color:
                nxt_color += 1
            dfs(nxt_node, nxt_color, use_path)
    
    global color_list
    if used_path != -1:
        color_list[used_path] = color

dfs(1, 0, -1)


for c in color_list:
    color_max = max(c, color_max)
print(color_max)
print("\n".join(map(str, color_list)))
import numpy as np
import math
n = int(input())
l = np.empty(n)
l = np.nan

k = 0
while i <= n ** 0.5:
  if n % i == 0:
    l[k] = i + n / i - 2
  i += 1
print(int(np.nanmin(l)))

### FIXED CODE ###

n = int(input())

for i in range(int(n ** 0.5)):
  if n % (int(n ** 0.5) - i) == 0:
    j = n // (int(n ** 0.5) - i)
    break
    
print(int(n ** 0.5) - i + j - 2)
n=int(input())
d=dict()
for a in map(int,input().split()):
  if a not in d:
    d[a]=1
  else:
    d[a]+=1
m=int(input())
t=dict()
for a in map(int,input().split()):
  if a not in t:
    t[a]=1
  else:
    t[a]+=1
ans="YES"
for i in t.keys():
  if not t[i]==d[i]:
    ans="NO"
print(ans)

### FIXED CODE ###

n=int(input())
d=dict()
for a in map(int,input().split()):
  if a not in d:
    d[a]=1
  else:
    d[a]+=1
m=int(input())
t=dict()
for a in map(int,input().split()):
  if a not in t:
    t[a]=1
  else:
    t[a]+=1
  if a not in d:
    d[a]=0
ans="YES"
for i in t.keys():
  if not t[i]<=d[i]:
    ans="NO"
print(ans)
i = int(input())
list = []

if i % 2 == 0:
    for m in range(2, int((i+2)/2) + 1):
        if i % m == 0:
            list.append(m + i / m)

if i % 2 == 1:
    for m in range(1, int((i+1)/2), 2):
        if i % m == 0:
            list.append(m + i / m)


list.sort()
print(int(list[0]-2))


### FIXED CODE ###

i = list(map(int, input().split()))

if i[0] <= 9:
    if i[1] <= 9:
        print(i[0] * i[1])
    else:
        print('-1')

else:
    print('-1')
return x*x*x

### FIXED CODE ###

print(int(input()) ** 3)
n, a, b = [int(i) for i in input().split()]

if (a ^ b) % 2 == 1 and (a ^ b) != 1:
    print('NO')
    exit()

def dfs(i, a):
    if i == 1:
        return [a & 1, ~a & 1]
    res = dfs(i - 1)
    if a & ((1 << i) - 1) != res[0]:
        res.reverse()
    return [(a & (1 << (i - 1))) + r for r in res] + [((~a) & (1 << (i - 1))) + r for r in res[::-1]]

ans = [(1 << (n - 1)) + r for r in dfs(n - 1, b)[::-1]] + [r for r in dfs(n - 1, a)]
index = ans.index(a)
print('YES')
print(*(ans[index:] + ans[:index]))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, a, b = [int(i) for i in input().split()]

if bin(a ^ b).count('1') % 2 == 0:
    print('NO')
    exit()

def dfs(i, a, b):
    if i == 1:
        return [a, b]
    d = (a ^ b) & -(a ^ b)
    ad = ((a & (~d ^ d - 1)) >> 1) + (a & d - 1)
    bd = ((b & (~d ^ d - 1)) >> 1) + (b & d - 1)
    c = ad ^ 1

    res1 = dfs(i - 1, ad, c)
    res2 = dfs(i - 1, bd, c)
    ans1 = [((r & ~(d - 1)) << 1) + (r & d - 1) + (d & a) for r in res1]
    ans2 = [((r & ~(d - 1)) << 1) + (r & d - 1) + (d & b) for r in res2[::-1]]
    return ans1 + ans2

print('YES')
print(*dfs(n, a, b))
def II(): return int(input())
def LI(): return [int(i) for i in input().split()]

N, K = LI()
H = LI()

cost = [0] * n
cost[0] = 0
for n in range(1, N):
  MIN = min(
  	[ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, K+1) if n-k>=0 ]
  )
  cost[n] = MIN

print(cost[-1])

### FIXED CODE ###

#  def II(): return int(input())
#def LI(): return [int(i) for i in input().split()]

#N, K = LI()
#H = LI()

#cost = [0] * N
#cost[0] = 0
#for n in range(1, N):
#  cost[n] = min([ cost[n-k]+abs(H[n-k]-H[n]) for k in range(1, min(n+1, K+1)) ])

#print(cost[-1])

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    a = [0] * n
    a[0] = 0
    for i in range(1, n):
        a[i] = min([a[j] + abs(h[i] - h[j]) for j in range(max(0, i - k), i)])
    print(a[-1])
 
if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-
INF=10**10

def main():
    
    n,m=list(map(int,input().split()))
    a=[0 for _ in range(n)]
    b=[0 for _ in range(n)]
    c=[0 for _ in range(n)]
    d=[[INF for i in range(n)] for i in range(n)]
    for i in range(n):
        a[i],b[i],c[i]=list(map(int,input().split()))
        a[i]-=1
        b[i]-=1
        d[a[i]][b[i]]=c[i]
        d[b[i]][a[i]]=c[i]
    
    for i in range(n):
        d[i][i]=0
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
                d[j][i]=d[i][j]
    ans=0
    for j in range(m):
        temp=1
        for i in range(n):
            if d[i][b[j]]==d[i][a[j]]+c[j]:
                temp=0
                break
        ans+=temp
    print(ans)
    
    
    
        
        
    
if __name__=="__main__":
    main()
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
INF=10**10

def main():
    
    n,m=list(map(int,input().split()))
    a=[0 for _ in range(m)]
    b=[0 for _ in range(m)]
    c=[0 for _ in range(m)]
    d=[[INF for i in range(n)] for i in range(n)]
    for i in range(m):
        a[i],b[i],c[i]=list(map(int,input().split()))
        a[i]-=1
        b[i]-=1
        d[a[i]][b[i]]=c[i]
        d[b[i]][a[i]]=c[i]
    
    for i in range(n):
        d[i][i]=0
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
                d[j][i]=d[i][j]
    ans=0
    for j in range(m):
        temp=1
        for i in range(n):
            if d[i][b[j]]==d[i][a[j]]+c[j]:
                temp=0
                break
        ans+=temp
    print(ans)
    
    
    
        
        
    
if __name__=="__main__":
    main()