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

from scipy.sparse.csgraph import dijkstra

N = int(input())

V = [[0]*N for _ in range(N)]

for i in range(N-1):
    u,v,w = list(map(int, input().split()))
    V[u-1][v-1] = w

D = dijkstra(V, directed=False, indices=0)
#print(D)

for d in D:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import numpy
#from collections import deque
sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

childsof = [[] for _ in range(N+1)]

for _ in range(N-1):
    u,v,w = list(map(int, input().split()))
    childsof[u].append((v,w))
    childsof[v].append((u,w))

distances = [-1]*(N+1)
distances[1] = 0

def dfs(i):
    childs = childsof[i]

    for c in childs:
        j = c[0]
        if distances[j] == -1:
            distances[j] = distances[i] + c[1]
            dfs(j)

dfs(1)

for d in distances[1:]:
    if d % 2 == 0: #even
        print(0)
    else:
        print(1)
### BUGGY CODE ###

from numba import njit

N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

@njit(cache=True)
def calc(N, M, A, X, Y):
    ans = 0
    for a in A:
        aa = (a // N + 1) * M + a % N + 1
        ans += X[aa]
        h = X[aa]
        if h < 0: continue
        Q = [(aa, h)]
        q = 0
        X[aa] -= 1
        Y[aa] = 0
        dd = (-1, 1, M, -M)
        while q < len(Q):
            i, h = Q[q]
            q += 1
            for d in dd:
                j = i + d
                y = Y[j]
                if X[j] >= h + y:
                    X[j] -= 1
                    Q.append((j, h + y))
    return ans
print(calc(N, M, A, X, Y))

### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

def calc(i0):
    h = X[i0]
    if h < 0: return
    Q = deque([(i0, h)])
    X[i0] -= 1
    Y[i0] = 0
    dd = (-1, 1, M, -M)
    while Q:
        i, h = deque.popleft(Q)
        for d in dd:
            j = i + d
            y = Y[j]
            if X[j] >= h + y:
                X[j] -= 1
                deque.append(Q, (j, h + y))
ans = 0
for a in A:
    aa = (a // N + 1) * M + a % N + 1
    ans += X[aa]
    calc(aa)
print(ans)
### BUGGY CODE ###

""" C
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, A):
    M = pow(10, 9) + 7
    result = 0
    for i in range(len(A)):
        result = (result + A[i] * sum(A[i+1:len(A)])) % M
    return result

if __name__ == "__main__":
    _N = readInteger()
    _A = readIntegerSet(_N)

    print(main(_N, _A))

### FIXED CODE ###

""" C
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, A):
    M = pow(10, 9) + 7
    result = 0
    S = sum(A)
    for i in range(len(A)):
        S = S - A[i]
        result = (result + A[i] * S) % M
    return result

if __name__ == "__main__":
    _N = readInteger()
    _A = readIntegerSet(_N)

    print(main(_N, _A))
### BUGGY CODE ###

import math

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
#print(a, b)
for i in range(n):
    a[i], b[i] = map(int, input().split())

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(math.ceil(j / a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(math.ceil(j/ a[i]) * b[i], dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])

### FIXED CODE ###

import math

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
#print(a, b)
for i in range(n):
    a[i], b[i] = map(int, input().split())

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(-(-j // a[i]) * b[i], dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])
### BUGGY CODE ###

n, q = map(int, input().split())
s = list(input())
for i in range(q):
    l, r = map(int, input().split())
    t = s[l - 1:r]
    ans = 0
    for j in range(len(t) - 1):
        if t[j] == 'A' and t[j + 1] == 'C':
            ans += 1
    print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())
num = [0] * n
count = 0
for i in range(n - 1):
    if s[i] == 'A' and s[i + 1] == 'C':
        count += 1
    num[i + 1] = count
for i in range(q):
    l, r = map(int, input().split())
    ans = num[r - 1] - num[l - 1]
    print(ans)
### BUGGY CODE ###

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

b = [0]

for i in range(n):
    b.append(b[i]+a[i])

b = sorted(b)
ans = 0

for i in range(min(b),max(b)+1):
    n = b.count(i)
    
    ans += int((n*(n-1))/2)

print(ans)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter

n = int(input())
l = list(map(int,input().split()))
l.insert(0,0)
a = list(accumulate(l))

count_a = Counter(a)

ans = 0

for i in count_a.values():
    if i < 2:
        continue
    ans += i*(i-1)/2
        

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

job = list()
salary = list()
n,m = map(int,input().split())
k = -1

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    if k == -1 or k > t:
         k = t
    salary.append(t)

    if s - m > 0:
        if salary[0] > k:
              salary.sort()
              k = -1
        del salary[0]
    else:
        m -= 1

print(sum(salary))


### FIXED CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))
### BUGGY CODE ###

k = input()
s = raw_input()

if k==0:
    print s
    exit(0)


l = len(s) / (k+1)
r = (len(s)+k) / (k+1)
left = min(int(s[i:i+l]) for i in xrange(len(s)-l))/10
right = max(int(s[i:i+r]) for i in xrange(len(s)-r))*10
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = 0
    for c in s:
        now = 10*now + int(c)
        if now > mid:
            cnt += 1
            now = int(c)
            if now > mid:
                cnt = 100003
                break
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1


### FIXED CODE ###

k = input()
s = raw_input()

if k==0:
    print s
    exit(0)
if len(s) % (k+1) == 0:
    p = len(s) / (k+1)
    print max(int(s[i:i+p]) for i in xrange(0,len(s),p))
    exit(0)

l = len(s) / (k+1)
r = (len(s)+k) / (k+1)
left = 10**(l-1)
right = 10**r
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = ""
    mid_c = str(mid)
    cp = idx = 0
    for c in s:
        now += c
        if not cp and idx < len(mid_c) and c != mid_c[idx]:
            cp = 1 if c > mid_c[idx] else -1
        idx += 1
        if (idx == len(mid_c) and cp == 1) or idx > len(mid_c):
            cnt += 1
            idx = 1; cp = 0
            if int(c) > mid:
                cnt = 100003
                break
            now = c
            if c != mid_c[0]:
                cp = 1 if c > mid_c[0] else -1
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1
### BUGGY CODE ###

import itertools

n = int(input())
ls = [0] + list(map(int, input().split()))
s0 = list(itertools.accumulate(ls))
s1 = list(itertools.accumulate(ls, lambda a, b: a ^ b))
res = 0
for l in range(1, n + 1):
    for r in range(l, n + 1):
        a = s0[r] - s0[l - 1]
        b = s1[r] ^ s1[l - 1]
        if a == b:
            res += 1
print(res)

### FIXED CODE ###

import itertools

n = int(input())
ls = [0] + list(map(int, input().split()))
s0 = list(itertools.accumulate(ls))
s1 = list(itertools.accumulate(ls, lambda a, b: a ^ b))
res = 0
left = 0
right = 1
count = 0
while left <= n:
    while left < right - 1:
        a = s0[right] - s0[left]
        b = s1[right] ^ s1[left]
        if a != b:
            left += 1
        else:
            res -= (right - left - 1) * (right - left) // 2
            break
    while right <= n + 1:
        if right == n + 1:
            break
        a = s0[right] - s0[left]
        b = s1[right] ^ s1[left]
        if a == b:
            right += 1
        else:
            break
    res += (right - left - 1) * (right - left) // 2
    if right == n + 1:
        break
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
k=1
for i in range(61):
    count0=0
    count1=0
    for j in a:
        if not (j>>i & 1):
            count0+=1
        if j>>i & 1:
            count1+=1
    ans+=((count0*count1)*(k))%mod
    k=(2*k)%mod
    
    
print(ans%mod)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
k=1
for i in range(61):
    count0=0
    count1=0
    for j in a:
        if not (j>>i & 1):
            count0+=1
        if j>>i & 1:
            count1+=1
    ans+=((count0*count1)*(k))%mod
    k=(2*k)%mod
    
    
print(ans%mod)
### BUGGY CODE ###

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

remain = [[0,0,0]]
for i in range(n):
    r, g, b = remain[-1]
    if s[-i-1] == "R":
        r = r+1
    elif s[-i-1] == "G":
        g = g + 1
    elif s[-i-1] == "B":
        b = b + 1

    remain.append([r,g,b])

total = 0
for i in range(n-2):
    if s[i] == "R":
        for j in range(i+1, n):
            if s[j] == "G":
                total += remain[-j-1][2]
                try:
                    if s[i+((j-i)*2)]=="B":
                        total -= 1
                except:
                    pass
            elif s[j] == "B":
                total += remain[-j-1][1]
                try:
                    if s[i+((j-i)*2)]=="G":
                        total -= 1
                except:
                    pass
    elif s[i] == "G":
        for j in range(i+1, n):
            if s[j] == "B":
                total += remain[-j-1][0]
                try:
                    if s[i+((j-i)*2)]=="R":
                        total -= 1
                except:
                    pass
            elif s[j] == "R":
                total += remain[-j-1][2]
                try:
                    if s[i+((j-i)*2)]=="B":
                        total -= 1
                except:
                    pass
    elif s[i] == "B":
        for j in range(i+1, n):

            if s[j] == "R":
                total += remain[-j-1][1]
                try:
                    if s[i+((j-i)*2)]=="G":
                        total -= 1
                except:
                    pass
            elif s[j] == "G":
                total += remain[-j-1][0]
                try:
                    if s[i+((j-i)*2)]=="R":
                        total -= 1
                except:
                    pass
print(total)

### FIXED CODE ###


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

remain = [[0,0,0]]
for i in range(n):
    r, g, b = remain[-1]
    if s[-i-1] == "R":
        r = r+1
    elif s[-i-1] == "G":
        g = g + 1
    elif s[-i-1] == "B":
        b = b + 1

    remain.append([r,g,b])

total = 0

rgb="RGB"
for i in range(n-2):
    first = s[i]
    search = []
    for j in range(3):
        if j==rgb.find(first):
            continue
        else:
            search.append(j)
    total = total + (remain[-i-2][search[0]]*remain[-i-2][search[1]])
    try:
        for j in range(1,n):
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j]:
                total -= 1
    except:
        pass


print(total)
### BUGGY CODE ###

N, M, Q = map( int, input().split())
NN = [ [ 0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L][R] += 1
Sum = [ [ 0 ] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        Sum[i].append(Sum[i][-1]+NN[i][j])
for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p,q+1):
        ans += Sum[i][q] - Sum[i][p-1]
    print(ans)

### FIXED CODE ###

N, M, Q = map( int, input().split())
NN = [ [0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L][R] += 1

for i in range(1,N+1):
    for j in range(1,N+1):
        NN[i][j] += NN[i][j-1]+NN[i-1][j]-NN[i-1][j-1]
for _ in range(Q):
    p, q = map( int, input().split())
    print(NN[q][q]-NN[q][p-1]-NN[p-1][q]+NN[p-1][p-1])
### BUGGY CODE ###

n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort()
d=[]
for i in range(0,m-1):
    d.append(l[i+1] - l[i])
try:
    for i in range(0,n-1):
        d.sort()
        ld=len(d)
        d.pop(ld-1)
    print(sum(d))
except IndexError:
    print(0)

### FIXED CODE ###

n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort()
d=[]
for i in range(0,m-1):
    d.append(l[i+1] - l[i])
d.sort()
for i in range(0,n-1):
    ld = len(d)
    if ld == 0:
        print(0)
        import sys
        sys.exit()
    d.pop(ld-1)
print(sum(d))
### BUGGY CODE ###

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

bits = 0

result = 0
for x in p:
  if x == 1:
    bits |= 1 << x - 1
    result += 1
    continue
  
  lower_bits = '1' * (x - 1)
  
  if (bits & int(lower_bits, 2)) > 0:
    bits |= 1 << x - 1
    continue
    
  result += 1
  bits |= 1 << x - 1

print(result)

### FIXED CODE ###

iterate = int(input())
p = [int(x) for x in input().split()]

result_sum = 0
prev_min = 10  ** 9
for i in range(iterate):
  if p[i] <= prev_min:
    	result_sum += 1
  prev_min = min(prev_min, p[i])

print(result_sum)
### BUGGY CODE ###

import sys
input  = sys.stdin.readline

N,K = map(int,input().split())
hn = list(map(int,input().split()))
rtn = [10**12]*N
for i in range(N):
  if i==0:
    rtn[i]=0
  else:
    rtn[i]=rtn[i-1]+abs(hn[i]-hn[i-1])
    for j in range(K,0,-1):
      if rtn[i]==0:
        break
      if i<j:
        continue
      else:
        rtn[i]=min(rtn[i], rtn[i-j]+abs(hn[i]-hn[i-j]))
print(rtn[N-1])

### FIXED CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
 
dp=[float('inf') for _ in range(n)]
dp[0]=0
for i,hi in enumerate(H[1:],1):
  s=max(0,i-k)
  dp[i]=min([aj + abs(hi-hj) for hj,aj in zip(H[s:i],dp[s:i])])
print(dp[-1])
### BUGGY CODE ###

import itertools

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = []
for p in itertools.product(A, B):
    AB.append(sum(p))
AB.sort(reverse=True)
AB = AB[:K]

l = []
for p in itertools.product(AB, C):
    l.append(sum(p))
l.sort(reverse=True)
for i in range(K):
    print(l[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

S = input()

tmp = len(S)
while True:
  S = S.replace("ST", "")
  if(len(S) == tmp):
    break
  tmp = len(S)
print(len(S))

### FIXED CODE ###

S = input()

result = ""
for s in S:
  if(s == "T" and result == ""):
    result += s
  elif(s == "T" and result[-1] == "S"):
    result = result[:-1]
  else:
    result += s
print(len(result))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
for i in range(N):
  result = result * A[i]
if result > 1000000000000000000:
  print(-1)
else:
  print(result)
  

### FIXED CODE ###

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

def judge(A):
  for i in range(len(A)):
    if A[i] == 0:
      print(0)
      return
  result = 1
  for i in range(N):
    result = result * A[i]
    if result > 1000000000000000000:
      print(-1)
      return
  if result <= 1000000000000000000:
    print(result)
    return
  
judge(A)
### BUGGY CODE ###

import sys


sys.setrecursionlimit(10 ** 9)

n,m = [int(_) for _ in input().split()]
l = [[] for _ in range(n+1)]
a = [0]*m
b = [0]*m
for i in range(m):
    a[i],b[i] = [int(_) for _ in input().split()]
    l[a[i]].append(b[i])
    l[b[i]].append(a[i])
seen = []

def dfs(l, todo):
    global seen
    global c
    if len(todo) != 0:
        s = todo.pop()
        for i in l[s]:
            if i not in seen:
                todo.append(i)
                seen.append(i)
                c += 1
            else:
                continue
        return dfs(l, todo)
    else:
        return 0


for j in range(m):
    l[a[j]].remove(b[j])
    l[b[j]].remove(a[j])
    ans = 0
    seen = []
    for i in range(1, n+1):
        if i not in seen:
            s = i
            seen.append(s)
            c = 1
            todo = [s]
            dfs(l, todo)
            ans += c * (n-c)
    print(ans//2)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def check(a, b):
    global uf
    global ans_list
    if uf.same(a,b):
        ans_list.append(0)
    else:
        ans_list.append(uf.size(a)*uf.size(b))
        uf.union(a,b)
    return 0




n,m = [int(_) for _ in input().split()]
l = []
for i in range(m):
    l.append([int(_) for _ in input().split()])
l.reverse()

ans_list = []
uf = UnionFind(n+1)
for i in range(m):
    a,b = l[i]
    check(a, b)
ans_list.reverse()
s = [0] * m
s[0] = ans_list[0]
for i in range(1, len(ans_list)):
    s[i] = s[i-1] + ans_list[i]
for i in range(len(s)):
    print(s[i])
### BUGGY CODE ###

def E(n):
  return n*(1+n)/2/n

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

tmpmax = 0
for i in range(n-k+1):
  s = 0
  for j in range(k):
    s += E(l[i + j])
  if s >= tmpmax:
    tmpmax = s

print(tmpmax)
  

### FIXED CODE ###

def E(n):
  return n*(1+n)/2/n

n, k = map(int, input().split())
l = list(map(int, input().split()))
ex = []
exsum = [0] *300000

tmpmax = 0
for i in range(n):
  ex.append(E(l[i]))

for i in range(n-k+1):
  if i == 0:
    for j in range(k):
      tmpmax += ex[i+j]
      exsum[i] = tmpmax
  else:
    exsum[i] = exsum[i-1] - ex[i-1] + ex[i+k-1]
  
a = exsum.index(max(exsum))

print(exsum[a])
### BUGGY CODE ###

from collections import deque
import sys

input = sys.stdin.readline
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]


def bfs(x, y):
    queue = deque([(x, y, 0)])
    visited = [[False]*W for _ in range(H)]

    max_cost = 0
    while queue:
        px, py, cost = queue.popleft()
        max_cost = max(max_cost, cost)

        candidate = ((px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1))
        visited[py][px] = True
        for cx, cy in candidate:
            if 0 <= cx < W and 0 <= cy < H and not visited[cy][cx] and maze[cy][cx] == ".":
                queue.append((cx, cy, cost + 1))
    return max_cost


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == ".":
            ans = max(ans, bfs(x, y))

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def main():
    N, *A = map(int, read().split())

    P = [0] * N
    P_max = defaultdict(int)
    for i in range(N):
        P[i] = Counter(prime_factorize(A[i]))
        for p, n in P[i].items():
            if P_max[p] < n:
                P_max[p] = n

    ans = 0
    for i in range(N):
        P_i = P[i]
        b = 1
        for p, n in P_max.items():
            b = b * pow(p, n - P_i[p], MOD) % MOD
        ans = (ans + b) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from math import gcd
from functools import reduce

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def lcm(a, b):
    return a // gcd(a, b) * b


def main():
    N, *A = map(int, read().split())

    ans = 0
    l = 1
    for a in A:
        l, l_prev = lcm(l, a), l
        ans = (ans * (l // l_prev) % MOD + l // a) % MOD

    print(ans)
    return


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

N,M=map(int,input().split())
L=[0]
R=[0]
ans=0

for i in range(M):
    Lt,Rt=map(int,input().split())
    L.append(Lt)
    R.append(Rt)

for i in range(1,N+1):
    flg=1
    for j in range(1,M+1):
        if i >= L[j] and i <= R[j]:
            continue
        flg=0

    if flg==1:
        ans+=1
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
Lm=0
Rm=N
ans=0

for i in range(M):
    Lt,Rt=map(int,input().split())
    if Lm < Lt:
        Lm = Lt
    if Rm > Rt:
        Rm = Rt
if Rm < Lm:
    print(0)
else:
    print(Rm-Lm+1)