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

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()
    S = []
    for l,r in LR:
        S += list(range(l,r+1))
    dp = [0] *(N+1)
    dp[1] = 1
    for i in range(1, N + 1):
        for s in S:
            if i - s > 0:
                dp[i] += dp[i - s]
                dp[i] %= M
            else:
                break
    print(dp[N])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
M = 998244353


class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def segfunc(x, y):
    return x + y


def main():
    N, K = map(int, readline().split())
    LR = list(list(map(int, readline().split())) for _ in range(K))
    LR.sort()

    A = [0] * (N + 1)
    A[1] = 1
    seg = SegTree(A, segfunc=segfunc, ide_ele=0)
    for i in range(2, N + 1):
        for l, r in LR:
            if i - l > 0:
                total = (seg.tree[i + seg.num] + seg.query(max(1, i - r), min(N, i - l + 1)) % M)
                seg.update(i, total)
            else:
                break
    print(seg.tree[seg.num + N] % M)


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

n = int(input())
ans=0
for i in range(10):
    for j in range(10):
        a = 0
        b = 0
        for k in range(1,n+1):
            if str(k)[0] == str(i) and str(k)[-1] == str(j):
                a+=1
            if str(k)[0] == str(j) and str(k)[-1] == str(i):
                b+=1
        ans+=a*b
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0

c = [[0] * 10 for _ in range(10)]

for i in range(1,n + 1):
    c[int(str(i)[0])][int(str(i)[-1])]+=1

for i in range(10):
    for j in range(10):
        ans+=c[i][j] * c[j][i]
print(ans)
### BUGGY CODE ###

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

A.sort()

count = 0
for i in range(len(A)):
    if A[i] in A[:i]:
        continue
    if A[i] in A[i+1:]:
        continue
    flag = False
    for j in range(0, i):
        if (A[i] % A[j] == 0):
            flag = True
            break
    if not flag:
        count += 1

print(count)


### FIXED CODE ###

# エラトステネスの篩

N = int(input())
A = sorted(map(int, input().split()))
maxA = A[N - 1]
dp = [0] * (maxA + 1)

for i in range(len(A)):
    cursor = A[i]
    while cursor <= maxA:
        dp[cursor] += 1
        cursor += A[i]

ans = 0
for a in A:
    if dp[a] == 1:
        ans += 1

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

MOD = 10**9 + 7

N = int(input())
s = input()

# dp[i][j] := i 番目まで決めて i 番目の数より大きいものが j 個のときの場合の数
dp = [[0]*N for _ in range(N)]
dp[0] = [1]*(N+1)
for i in range(N-1):
    # 累積和をとっておく
    # for j in range(N-1):
    #     dp[i][j+1] += dp[i][j]
    for j in range(N-i-1):
        if s[i] == '<':
            for k in range(j+1, N-i):
                dp[i+1][j] += dp[i][k]
        else:
            for k in range(j+1):
                dp[i+1][j] += dp[i][k]
        dp[i+1][j] %= MOD

print(dp[N-1][0])

### FIXED CODE ###

MOD = 10**9 + 7

N = int(input())
s = input()

# dp[i][j] := i 番目まで決めて i 番目の数より大きいものが j 個のときの場合の数
dp = [[0]*N for _ in range(N)]
dp[0] = [1]*(N+1)
for i in range(N-1):
    # 累積和をとっておく
    for j in range(N-1):
        dp[i][j+1] += dp[i][j]
    for j in range(N-i-1):
        if s[i] == '<':
            dp[i+1][j] += dp[i][N-i-1]-dp[i][j]
        else:
            dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD

print(dp[N-1][0])
### BUGGY CODE ###

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

x-=1
y-=1
ans=[]
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

    ans.append(d)

ans2=[0 for i in range(n-1)]
for i in ans:
    for j in range(n-1):
        ans2[j]+=i.count(j+1)
for i in ans2:
    print(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 ###

from collections import deque
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    zeros = [0]*N
    for k in range(K-1):
        que0 = deque()
        que1 = deque()
        T[:k+1] = zeros[:k+1]

        for i in range(k, N-1):
            a = S[i]
            while que1 and que1[-1] <= a:
                que0.pop()
                que1.pop()
            que0.append(i)
            que1.append(a)

            T[i+1] = que1[0] + A[i+1]*(k+2)

            if que0 and que0[0] <= i+1-M:
                que0.popleft()
                que1.popleft()
        S, T = T, S
    print(max(S))
solve()

### FIXED CODE ###

import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()
### BUGGY CODE ###

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

B = [1, A[0]]

for i in range(2, N+1):
    B.append(B[i-1]*A[i-1])

for i in range(K+1, N+1):
    if B[i-1]/B[i-1-K] < B[i]/B[i-K]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(K, N):
    if A[i - K] < A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]
def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)

    for i in range(K):
        r_, c_, v_, = NMI()
        grid[r_ - 1][c_ - 1] = v_

    dp = [[[0 for _ in range(4)] for _ in range(C + 2)] for _ in range(R + 2)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[i][j][k]
                try:
                    v = grid[i][j]
                except:
                    v = 0

                if k == 3:
                    dp[i + 1][j][0] = max(a, dp[i + 1][j][0])
                    continue
                dp[i + 1][j][0] = max(a, a + v, dp[i + 1][j][0])
                dp[i][j + 1][k] = max(a, dp[i][j + 1][k])
                dp[i][j + 1][k + 1] = max(a + v, dp[i][j + 1][k + 1])

    print(max(dp[R][C][0], dp[R][C][1], dp[R][C][2], dp[R][C][3]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp = [[[0 for _ in range(C+2)] for _ in range(R+2)] for _ in range(4)]

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[i][r][c]
                try:
                    val = grid[r][c]
                except:
                    val = 0

                if i == 3:
                    # 取らずに下
                    dp[0][r + 1][c] = max(now, dp[0][r + 1][c])
                    continue

                # 取って下
                dp[0][r+1][c] = max(now + val, dp[0][r+1][c])
                # 取らずに下
                dp[0][r+1][c] = max(now, dp[0][r+1][c])
                # 取って横
                dp[i+1][r][c+1] = max(now + val, dp[i+1][r][c+1])
                # 取らずに横
                dp[i][r][c+1] = max(now, dp[i][r][c+1])

    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))


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

n = int(input())
s = [input() for i in range(n)]

cnt = 0
for i in range(n):
    for j in range(n):
        i_ = (n+i)%n
        j_ = (n+j)%n
        for k in range(n):
            for l in range(n):
                if s[(i_+k)%n][(j_+l)%n] != s[(i_+l)%n][(j_+k)%n]:
                    break
            else:
                continue
            break
        else:
            cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

cnt = 0

def is_symmetry(s_):
    for k in range(n):
        for l in range(k+1, n):
            if s_[k][l] != s_[l][k]:
                return False
    return True

for i in range(n):
    i_ = (n+i)%n
    s_ = s[i_:] + s[:i_]
    if is_symmetry(s_):
        cnt += 1

print(cnt*n)
### BUGGY CODE ###

import bisect
import copy
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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




N=one_int()
L=many_int()

L=sorted(L)

sankaku_dict={}
search_end={}
count=0
for i in range(len(L)-1):
    low=L[i]
    Lcopy = copy.deepcopy(L)
    Lcopy.remove(low)
    
    for j in range(i+1, len(L)):
        #すでに探索済みか判定
        temp = str(L[i]) +","+ str(L[j])
        if temp in search_end:
            continue
        high = L[j]
        Lcopy2 = Lcopy[j:]
        
        #下限を取得    
        under_index = bisect.bisect_right(Lcopy2,high-low)
        #上限を取得
        high_index = bisect.bisect_left(Lcopy2,high+low)
        
#         for va in Lcopy2[under_index:high_index]:
#             temp = sorted([high,low, va])
#             temp = (temp[0]*10**8) + (temp[1]*10**4) + temp[2]
#             sankaku_dict[temp]=1
        count+=len(Lcopy2[under_index:high_index])

# len(sankaku_dict)
print(count)
# print(len(sankaku_dict.keys()))

### FIXED CODE ###

import bisect
import copy
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

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


N=one_int()
L=many_int()

L=sorted(L)

sankaku_dict={}
count=0
for i in range(len(L)-1):
    low=L[i]
    for j in range(i+1, len(L)):
        #すでに探索済みか判定
        high = L[j]
        
        #上限を取得
        high_index = bisect.bisect_left(L[j+1:], high+low)
        count+=high_index#len(L[j+1:high_index])

# len(sankaku_dict)
print(count)
# print(len(sankaku_dict.keys()))
### BUGGY CODE ###

from collections import Counter

n = int(input())
lst = []
lstn = [] 
cnt = 0

def nCr(n,r):
    r = min(r,n-r)
    numerator = 1
    for i in range(n,n-r,-1):
        numerator *= i
    denomination = 1
    for i in range(r,1,-1):
        denomination *= i
    return numerator // denomination

for i in range(n):
    s = input()
    c = Counter(s)
    if c not in lst:
        lst.append(c)
        lstn.append(1)
    else:
        k = lst.index(c)
        lstn[k] += 1

for x in lstn:
    if x >= 2:
        cnt += nCr(x,2)
print(cnt)

### FIXED CODE ###

from collections import Counter

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

sorted_S =  [''.join(sorted(s)) for s in S]
c = Counter(sorted_S)

print(sum([n * (n-1)//2 for n in  list(c.values())]))
### BUGGY CODE ###

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

result = 1

for i in range(N):
  result *= a[i]
if result > 10**18:
  print(-1)
else:
  print(result)

### FIXED CODE ###

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

result = 1

if 0 in a:
  print(0)
  exit()
else:
  for i in range(N):
    result *= a[i]
    if result > 10**18:
      print(-1)
      exit()
  print(result)
### BUGGY CODE ###

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

l = ""
while len(l) < N:
    for i in range(A):
        if len(l) < N:
            l += "b"
    for j in range(B):
        if len(l) < N:
            l += "r"
    

print(l.count("b"))

### FIXED CODE ###

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

x = (N // (A+B)) * A
y = N%(A+B)

if y >= A:
    x += A
else:
    x += y

print(x)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
T = [1] * (N)
for i in range(N):
  for j in range(N):
    if T[j] == 1 and i != j and A[j] % A[i] == 0:
      T[j] = 0
print(sum(T))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = max(A)
num = [0] * (M)
T = [0] * (M)
for a in A:
  num[a-1] += 1
  T[a-1] = 1
for i in range(M):
  if num[i] != 0 and T[i] == 1:
    n = 2 * (i + 1)
    while n <= M:
      T[n-1] = 0
      n += (i + 1)
ans = 0
for i in range(M):
  if T[i] == 1 and num[i] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
B.sort()
BC,ans=[0 for _ in range(n)],0
C=list(map(int,input().split()))
C.sort()

for i in range(n):
  left,right=-1,n
  
  while right - left > 1:
    mid = (left + right) // 2
    
    if B[mid] > A[i]:
      right = mid
    else:
      left = mid
  k = right
  
  for j in range(k,n):
    if BC[j]:
      ans += BC[j]
      continue
    
    left,right=-1,n
    
    while right - left > 1:
      mid = (left + right) // 2
      
      if C[mid] > B[j]:
        right = mid
      else:
        left = mid
        
    ans += (n - right)
    BC[j] = n - right
    
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

n,ans=int(input()),0

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

A.sort()
C.sort()

for b in B:
  j = bisect_left(A,b)
  k = bisect_right(C,b)
  ans += j*(n-k)
  
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
city = []
p_list = []
for i in range(m):
    p, y = map(int, input().split())
    city.append([p, y, i])
city.sort(key=lambda x: x[1])
city.sort()
n = 0
for i in range(m):
    p_list.append(city[i][0])
max_p = max(p_list)

for i in range(max_p + 1):
    for j in range(p_list.count(i)):
        city[n].append(str(p_list[n]).zfill(6) + (str(j + 1)).zfill(6))
        n += 1

city.sort(key=lambda x: x[2])
for i in range(m):
    print(city[i][3])


### FIXED CODE ###

n, m = map(int, input().split())
tmp = [list(map(int, input().split())) for i in range(m)]
city = [[] for i in range(n+1)]
answers = [''] * m

for i, (pref, year) in enumerate(tmp):
    city[pref].append([year, i])

for i in range(n+1):
    for j, (year, index) in enumerate(sorted(city[i])):
        ans = str(i).zfill(6) + str(j+1).zfill(6)
        answers[index] = ans

print(*answers, sep='\n')
### BUGGY CODE ###

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

def half(n,z):
	exist_odd = False
	count = 0
	while True: 
		for i in z:
			if i % 2 != 0:
				exist_odd = True

		if exist_odd:
			print(count)
			break
		
		for i in z:		
			i /= 2
		
		count += 1

half(n,z)


### FIXED CODE ###

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

def half(n,z):
	existodd = 0
	count = 0
	while True: 
		for i in z:
			if i % 2 != 0:
				existodd = 1

		if existodd:
			print(count)
			break
		
		for i in range(n):		
			z[i] /= 2
		
		count += 1
	
half(n,z)
### BUGGY CODE ###

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

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

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

for l, r in LR:
    ans = lst[r-1] - lst[l-1]
    print(ans)


### FIXED CODE ###

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

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

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

for l, r in LR:
    ans = lst[r-1] - lst[l-1]
    print(ans)
### BUGGY CODE ###

import sys
n=int(input())
a=[int(input()) for _ in range(n)]
c=[]
s=a[0]
cnt=1
while(1):
    if s==2:
        print(cnt)
        sys.exit()
    if s in c:
        print(-1)
        sys.exit()
    c.append(s)
    s=a[s-1]
    cnt+=1

### FIXED CODE ###

import sys
n=int(input())
a=[int(input()) for _ in range(n)]
c=set()
s=a[0]
cnt=1
while(1):
    if s==2:
        print(cnt)
        sys.exit()
    if s in c:
        print(-1)
        sys.exit()
    c.add(s)
    s=a[s-1]
    cnt+=1
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = [s]
    ans = k
    Qappend = Q.append
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    while len(Q) != 0:
        v = Q.pop()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans *= cand
            cand -= 1
            Qappend(i)
        ans = ans % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


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

def resolve():
    def Dijkstra(s, g, edge, inf=float("inf")):
        import heapq
        d = {}
        d[s] = 0
        used = set()
        used.add(s)
        queue = []
        for q in edge[s]:
            heapq.heappush(queue, q)
        while queue:
            dist, point = heapq.heappop(queue)
            if point in used:
                continue
            d[point] = dist
            if point == g:
                return dist
            used.add(point)
            for nextdist, nextp in edge[point]:
                if not nextp in used:
                    heapq.heappush(queue, (dist + nextdist, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    inf = 10 ** 10
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, -1)].add((1, (p, c)))
        edge[(q, -1)].add((1, (q, c)))
        edge[(p, c)].add((0, (p, -1)))
        edge[(q, c)].add((0, (q, -1)))
        edge[(p, c)].add((0, (q, c)))
        edge[(q, c)].add((0, (p, c)))
    print(Dijkstra((0, -1), (n - 1, -1), edge, inf))


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    def Dijkstra(s, g):
        from collections import deque
        d = {s}
        queue = deque()
        for q in edge[s]:
            queue.append((1, q))
        while queue:
            dist, point = queue.popleft()
            if point in d:
                continue
            d.add(point)
            if point == g:
                return dist
            for nextp in edge[point]:
                if not nextp in d:
                    if not -1 in point or -1 in nextp:
                        queue.appendleft((dist, nextp))
                    else:
                        queue.append((dist + 1, nextp))
        return -1
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    n, m = map(int, input().split())
    edge = defaultdict(set)
    for _ in range(m):
        p, q, c = map(int, input().split())
        p, q = p - 1, q - 1
        edge[(p, c)].add((q, c))
        edge[(q, c)].add((p, c))
        edge[(p, c)].add((p, -1))
        edge[(q, c)].add((q, -1))
        edge[(p, -1)].add((p, c))
        edge[(q, -1)].add((q, c))
    print(Dijkstra((0, -1), (n - 1, -1)))


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

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

for v in itertools.combinations(a,2):
    if v[0] == v[1]:
        print('NO')
        exit()
print('YES')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if len(a) == len(set(a)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] %= 1000000007
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        c = a[i] * a[j]
        c %= 1000000007 
        ans += c
ans %= 1000000007
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
b = 0
c = 0
for i in range(n):
    b += a[i]
    c += a[i] * a[i]
ans = (b * b - c) // 2
ans %= 1000000007
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
stones = list(map(int,input().split()))
dp =[1000000007] *N

dp[0]=0
dp[1]=abs(stones[1]-stones[0])

for i in range(2,N):
    for j in range(max(0, i - K), i):
        dp[i] = min(abs(stones[i] - stones[j]) + dp[j], dp[i])

print(dp[-1])


### FIXED CODE ###

N,K = map(int,input().split())
stones = list(map(int,input().split()))
dp =[0] *N

for i in range(1,N):
    dp[i] = min(abs(stones[i] - stones[j]) + dp[j] for j in range(max(0, i - K), i))

print(dp[-1])