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

N=int(input())
vertexes=[[] for i in range(N)]
edges=[[int(s) for s in input().split()] for i in range(N-1)]
#頂点ごとに、頂点から伸びる辺のデータを記録
for e in edges:
  vertexes[e[0]-1].append([e[1]-1,e[2]])
  vertexes[e[1]-1].append([e[0]-1,e[2]])

#幅優先探索の開始（v_possibleに入った順に頂点を訪れる）
answer=[-1 for i in range(N)]  #到達していない頂点は-1
answer[0]=0
v_possible=[] #到達可能な頂点と、辺の情報
v=0 #現在の位置
for i in range(N-1):
  for e in vertexes[v]: #行き先の更新
    if answer[e[0]]==-1: #未到達ならv_possibleに追加
      v_possible.append([e[0],v,e[1]]) #[行き先,つながる頂点,距離] 
  v2=v_possible[0] #v_possibleの最初の頂点に移動
  answer[v2[0]]=(answer[v2[1]]+v2[2])%2
  v=v2[0]
  del v_possible[0]
  
#答を出力
for i in range(N):
  print(answer[i])


### FIXED CODE ###

N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1): #辺の情報と距離を記録
  u, v, w = map(int, input().split())
  edge[u-1].add((v-1, w))
  edge[v-1].add((u-1, w))

#幅優先検索
dist = [0] * N #距離
stack = [0]
while stack: #stackが空になるまで
  vrt = stack.pop()
  for to, w in edge[vrt].copy():
    stack.append(to)
    dist[to] = dist[vrt] + w
    edge[vrt].discard((to, w))
    edge[to].discard((vrt, w))
    
for i in range(N):
  print(dist[i]%2)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    cnt = 0
    while n > 1:
        a_max = max(a[:n])
        a_max_i = a.index(a_max)
        cnt += (n - a_max_i) * a_max - sum(a[a_max_i:n])
        n = a_max_i
    print(cnt)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    maxv = 0
    ans = 0
    for a in A:
        if maxv > a:
            ans += maxv - a
        else:
            maxv = a  
    print(ans)

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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

N, Q = LI()
AB = []
PX = []
for i in range(N-1):
    AB.append(LI())

for i in range(Q):
    PX.append(LI())

"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？


"""

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

perr('AB')
perr(AB)
d = {}
for a, b in AB:
    # abの頂点若い方に足していく
    if a not in d.keys():
        d[a] = []
    if b not in d.keys():
        d[a].append(b)
    else:
        d[a].append(b)
        d[a].extend(d[b])

perr('d')
perr(d)

ans = [0 for _ in range(N)]
for p, x in PX:
    perr('px')
    perr([p, x])
    ans[p-1] += x
    if p not in d.keys():
        continue
    for i in d[p]:
        perr('i')
        perr(i)
        ans[i-1] += x

perr('ans')
perr(ans)
for a in ans:
    print(a, end=' ')


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)

if 'LOCAL' in os.environ:
    N = 2* 10** 5
    Q = 2 * 10 ** 5
    AB = [[i, i + 1] for i in range(1, N)]
    PX = [[i, 10] for i in range(Q)]
else:
    N, Q = LI()
    AB = []
    PX = []
    for i in range(N-1):
        AB.append(LI())

    for i in range(Q):
        PX.append(LI())


"""
そもそも各頂点の部分木をdictに入れましょうか？
参照するような形で。
2には3
3には4,5
4,5はNoneだと、参照しやすいか？

カウントを若い順にやっていく
"""
AB = sorted(AB, key=lambda x: x[0])
perr('AB')
perr(AB)
d = {}
for p, x in PX:
    if p not in d.keys():
        d[p] = 0
    d[p] += x
for a, b in AB:
    if b not in d.keys():
        d[b] = 0
    if a not in d.keys():
        d[a] = 0
    d[b] += d[a]
for i in range(1, N+1):
    print(d[i], end=' ')
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

S = sorted(A)
D = {a: i for i, a in enumerate(S)}

BB = [0] * (N+1)
for i in range(N):
    BB[D[A[i]] + 1] = B[i]

for i in range(1, N+1):
    BB[i-1] ^= BB[i]

def bl(L, k):
    l, r = -1, len(L)
    while r - l > 1:
        m = (l+r) // 2
        if L[m] >= k:
            r = m
        else:
            l = m
    return r

A = [D[a] for a in A]
X = [[] for _ in range(N+1)]
DD = {}
for i in range(M):
    l, r = map(int, input().split())
    l = bl(S, l)
    r = bl(S, r+1)
    X[l].append(r)
    X[r].append(l)
    DD[(l<<18) + r] = i
    DD[(r<<18) + l] = i

Q = deque([i for i in range(N+1)])
P = [-1] * (N+1)
CH = [[] for _ in range(N+1)]
R = []
done = [0] * (N+1)
while Q:
    i = deque.pop(Q)
    if P[i] < 0: R.append(i)
    for j in X[i]:
        if P[j] >= 0: continue
        if j != P[i]:
            R.append(j)
            P[j] = i
            CH[i].append(j)
            deque.append(Q, j)

ANS = []
for i in R[1:][::-1]:
    if BB[i]:
        BB[i] ^= 1
        BB[P[i]] ^= 1
        if P[i] < 0:
            print(-1)
            exit()
        ANS.append(DD[(i<<18) + P[i]] + 1)
if sum(BB) == 0:
    print(len(ANS))
    print(*sorted(ANS))
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# from bisect import bisect_left as bl, bisect_right as br
# from collections import deque
N, M = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b

S = sorted(A)
D = {a: i for i, a in enumerate(S)}

BB = [0] * (N+1)
for i in range(N):
    BB[D[A[i]] + 1] = B[i]

for i in range(1, N+1):
    BB[i-1] ^= BB[i]

def bl(L, k):
    l, r = -1, len(L)
    while r - l > 1:
        m = (l+r) // 2
        if L[m] >= k:
            r = m
        else:
            l = m
    return r

A = [D[a] for a in A]
X = [[] for _ in range(N+1)]
DD = {}
for i in range(M):
    l, r = map(int, input().split())
    l = bl(S, l)
    r = bl(S, r+1)
    X[l].append(r)
    X[r].append(l)
    DD[(l<<18) + r] = i
    DD[(r<<18) + l] = i

# Q = deque([i for i in range(N+1)])
# Q = [i for i in range(N+1)]
P = [-1] * (N+1)
CH = [[] for _ in range(N+1)]
R = []
done = [0] * (N+1)
for ii in range(N+1):
    Q = [ii]
    while Q:
        i = Q.pop()
        if P[i] < 0:
            R.append(i)
            done[i] = 1
        for j in X[i]:
            if P[j] >= 0: continue
            if j != P[i] and done[j] == 0:
                R.append(j)
                done[j] = 1
                P[j] = i
                CH[i].append(j)
                # X[j].remove(i)
                # deque.append(Q, j)
                Q.append(j)

ANS = []
for i in R[1:][::-1]:
    if BB[i]:
        BB[i] ^= 1
        BB[P[i]] ^= 1
        if P[i] < 0:
            print(-1)
            exit()
        ANS.append(DD[(i<<18) + P[i]] + 1)
if sum(BB) == 0:
    print(len(ANS))
    print(*sorted(ANS))
else:
    print(-1)
### BUGGY CODE ###

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

def bubble_sort(lst):
    for i in reversed(range(len(lst))):
        for j in range(i):
            if lst[j][0] > lst[j + 1][0]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

bubble_sort(a)
purchase_price = 0

for price, count in a:
    if count < m:
        purchase_price += price * count
        m -= count

    else:
        purchase_price += price * m
        m = 0

print(purchase_price)

### FIXED CODE ###

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

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


for price, count in a:
    if count < m:
        purchase_price += price * count
        m -= count

    else:
        purchase_price += price * m
        m = 0

print(purchase_price)
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())

ans = [math.floor(a*x/b) - a*math.floor(x/b) for x in range(1, n+1)]

print(max(ans))

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = min(b-1, n)
print(math.floor(a*(x%b)/b))
### BUGGY CODE ###

class DoublyLinkedListNode:
    def __init__(self, num):
        self.num  = num
        self.next = None
        self.prev = None

    def setNext(self, node):
        self.next = node

    def setPrev(self, node):
        self.prev = node

    def getNum(self):
        return self.num

    def getNext(self):
        return self.next

    def getPrev(self):
        return self.prev

class DoublyLinkedList:
    def __init__(self):
        self.first = None
        self.last  = None

    def insert(self, x):
        node = DoublyLinkedListNode(x)

        if self.first == None:
            self.first = node
            self.last  = node
            return

        self.first.setPrev(node)
        node.setNext(self.first)

        self.first = node

    def delete(self, x):
        node = self.first

        while node != None:
            if node.getNum() == x:
                if id(node) == id(self.first):
                    self.deleteFirst()
                    break

                if id(node) == id(self.last):
                    self.deleteLast()
                    break

                pnode = node.getPrev()
                nnode = node.getNext()

                if pnode != None:
                    pnode.setNext(nnode)
                if nnode != None:
                    nnode.setPrev(pnode)

                break

            node = node.getNext()

    def deleteFirst(self):
        node = self.first.getNext()

        if node == None:
            self.first = None
            self.last  = None
            return

        node.setPrev(None)
        self.first = node

    def deleteLast(self):
        node = self.last.getPrev()
        if node == None:
            self.first = None
            self.last  = None
            return

        node.setNext(None)
        self.last = node

    def __iter__(self):
        self._it = self.first
        return self

    def __next__(self):
        node = self._it
        if node == None:
            raise StopIteration

        self._it = self._it.getNext()
        return node.getNum()

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

    lst = DoublyLinkedList()

    for _ in range(n):
        cmds = input().split()

        if 'insert' == cmds[0]:
            lst.insert(int(cmds[1]))
        if 'delete' == cmds[0]:
            lst.delete(int(cmds[1]))
        if 'deleteFirst' == cmds[0]:
            lst.deleteFirst()
        if 'deleteLast' == cmds[0]:
            lst.deleteLast()

    print(" ".join([str(x) for x in lst]))

if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import deque

def main():
    lst = deque()

    n = int(input())

    for _ in range(n):
        cmd = input().split()

        if 'insert' == cmd[0]:
            lst.appendleft(cmd[1])
        if 'delete' == cmd[0]:
            try:
                lst.remove(cmd[1])
            except:
                pass
        if 'deleteFirst' == cmd[0]:
            lst.popleft()
        if 'deleteLast' == cmd[0]:
            lst.pop()

    sep = ''
    for n in lst:
        print(sep+n, end='')
        sep = ' '
    print()

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

H,N=map(int,input().split())

A=[]
B=[]

for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

DP=[[1000000000]*(H+max(A)+1) for i in range(N+1)]


for i in range(N):
    DP[i+1][A[i]]=B[i]


for i in range(N):
    for h in range(H+max(A)+1):
        DP[i+1][h]=min(DP[i+1][h],DP[i][h])
        if h-A[i]>=0:
            DP[i+1][h]=min(DP[i+1][h-A[i]]+B[i],DP[i+1][h])

print(min(DP[N][H:]))

### FIXED CODE ###

H,N=map(int,input().split())

A=[]
B=[]

for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

DP=[[1000000000]*(H+max(A)+1) for i in range(N+1)]


for i in range(N):
    DP[i+1][A[i]]=B[i]


for i in range(N):
    for h in range(H+max(A)+1):
        DP[i+1][h]=min(DP[i+1][h],DP[i][h])
        if h-A[i]>=0:
            DP[i+1][h]=min(DP[i+1][h-A[i]]+B[i],DP[i+1][h])

print(min(DP[N][H:]))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

cards = sorted(A)
op.sort(key=lambda x: -x[1])

i = 0

for m in range(M):
    b, c = op[m]
    for _ in range(b):
        if cards[i] < c:
            cards[i] = c
            i += 1
        if i >= N:
            break
    else:
        continue
    break

print(sum(cards))


### FIXED CODE ###

import sys

input = sys.stdin.readline

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

cards = sorted(A)
op.sort(key=lambda x: -x[1])

i = 0

for m in range(M):
    b, c = op[m]
    for _ in range(b):
        if cards[i] < c:
            cards[i] = c
            i += 1
            if i >= N:
                break
        else:
            break
    else:
        continue
    break

print(sum(cards))
### BUGGY CODE ###

#!/usr/bin/env python

import sys
import re

s= sys.stdin.readline().strip()
#
c= 0
pat= re.compile("(A+)((BC)+)")
while True:
    m =pat.search( s )
    if not m: break
    n = len( m.group(0) )
    a = len( m.group(1) )
    bc= len( m.group(2) ) // 2
    s= ("A"*a) + s[m.end():]
    c+= a*bc
print( c )


### FIXED CODE ###

#!/usr/bin/env python

import sys
import re

s= sys.stdin.readline().strip()
s= s.replace("BC","D")
s= re.sub("[BC]+"," ",s).split()

t= 0
for seg in s:
    a= 0
    for c in seg:
        if c=="A": a+=1
        elif c=="D": t+= a
#
print( t )
### BUGGY CODE ###

def main():
    # 入力
    n, m, r = map(int, input().split())
    abc = [list(map(int, input().split())) for _ in [0]*m]
    # グラフ
    g = [[] for _ in [0]*n]
    [g[a-1].append([b-1, c]) for a, b, c in abc]

    # 逆辺
    g2 = [[] for _ in [0]*n]
    [g2[b-1].append([a-1, c]) for a, b, c in abc]

    # 前処理用のDFS
    def remove_edge(graph, start):
        q = [start]
        memo = [True for _ in range(n)]
        memo[start] = False
        while q:
            qq = q.pop()
            for i, j in graph[qq]:
                if memo[i]:
                    q.append(i)
                    memo[i] = False
        return {i for i, j in enumerate(memo) if j == True}

    # 前処理
    rmv = remove_edge(g, 0) | remove_edge(g2, n-1)
    for i in rmv:
        g[i] = []
    for i in range(n):
        for j in g[i]:
            if j[0] in rmv:
                g[i].remove(j)

    # ベルマンフォード
    dist = [-10**15 for _ in [0]*n]
    dist[0] = 0

    for k in range(n):
        for p in range(n):
            for i, j in g[p]:
                dist[i] = max(dist[i], dist[p]+j-r)
        if k == n-2:
            d1 = [t for t in dist]
        if k == n-1:
            d2 = [t for t in dist]

    # 1からでもnの間に負の閉路があるときは-1
    if d1 == d2:
        print(max(d1[-1], 0))
    else:
        print(-1)
main()

### FIXED CODE ###

#入力
n,m,r=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*m]
#グラフ
g=[[] for _ in [0]*n]
[g[a-1].append([b-1,c]) for a,b,c in abc]
#逆辺
g2=[[] for _ in [0]*n]
[g2[b-1].append([a-1,c]) for a,b,c in abc]

#ベルマンフォード
dist=[-10**15 for _ in [0]*n]
dist[0]=0
a,b=-10**15,-10**15

for k in range(n):
    for p in range(n):
        for i,j in g[p]:
            dist[i]=max(dist[i],dist[p]+j-r)
    if k==n-2:
        d1=[t for t in dist]
    if k==n-1:
        d2=[t for t in dist]
    
#負の経路上の頂点の一覧
loop=set()
for i in range(n):
    if d1[i]!=d2[i]:
        loop.add(i)    
ans=max(d2[n-1],0)

#1からの到達可能地点
q=[0]
memo=[True for _ in range(n)]
memo[0]=False
while q:
    qq=q.pop()
    for i,j in g[qq]:
        if memo[i]:
            q.append(i)
            memo[i]=False
            
#nからの逆辺による到達可能地点
q=[n-1]
memo2=[True for _ in range(n)]
memo2[n-1]=False
while q:
    qq=q.pop()
    for i,j in g2[qq]:
        if memo2[i]:
            q.append(i)
            memo2[i]=False
            
#1からでもnからでも行ける点でかつ負の閉路に入っているものがあるときは-1
for i in loop:
    if memo[i]==False and memo2[i]==False:
        ans=-1
        
print(ans)
### BUGGY CODE ###

n,k = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]

dif = lambda x,y: abs(x-y)

dp = [0,dif(arr[0],arr[1])]

for i in range(2,n):
    H = arr[i]
    minCost = min([dp[j]+dif(arr[j],H) for j in range(max(0,i-k),i)])
    dp.append(minCost)

print(dp[-1])


### FIXED CODE ###

ni,ki = [int(i) for i in input().split()]
arri = [int(i) for i in input().split()]
    
def getRes(arr,n,k):
    dp = [0]*n
    for i in range(1,n):
        H = arr[i]
        dp[i] = min([dp[j]+abs(arr[j]-H) for j in range(max(0,i-k),i)])
    return dp[-1]

print(getRes(arri,ni,ki))
### BUGGY CODE ###

N, T = map(int, input().split())
ls = []
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])

dp = [[0]*(T) for i in range(N+1)]

for i in range(N):
  a,b = ls[i]
  for j in range(T-1, a-1, -1):
    dp[i+1][j] = max(dp[i][j], dp[i][j-a]+b)

last = [0]*N
last[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  last[i] = max(last[i+1], ls[i][1])

ans = 0

for i in range(1,N+1):
  ans = max(ans, max(dp[i-1])+last[i-1])

print(ans)

### FIXED CODE ###

N, T = map(int, input().split())
dp = [[0]*T for i in range(N+1)]

ls = []
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])

for i in range(N):
  a, b = ls[i]
  for j in range(T-1, a-1, -1):
    dp[i+1][j] = max(dp[i][j], dp[i][j-a]+b)
    
pre = [0]*N
pre[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  pre[i] = max(pre[i+1], ls[i][1])
    
ans = 0
for i in range(N-1):
  ans = max(ans, max(dp[i+1])+pre[i+1])
ans = max(ans, max(dp[-1]))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans *= i
if ans > 1e18: print("-1")
else: print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
mark = False
if 0 in a:
    print(0)
    mark = True
if mark==False:
    for i in range(n):
        ans *= a[i]
        if ans > 1000000000000000000:
            mark = True
            print(-1)
            break
if not mark: print(ans)
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans *= A[i]
if 10 ** 18 < ans:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
if 0 in A:
    print(0)
else:
    for i in range(N):
        ans *= A[i]
        if 10 ** 18 < ans:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    k=(2*y-x)//3
    l=(2*x-y)//3
    a = comb(k+l,l,10**9+7)
    print(a)


### FIXED CODE ###

'''
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
'''

def comb_mod(n, r, MOD):
    if n < 0 or r < 0 or n < r:
        return 0

    factrial = [1] * (n+1)
    for k in range(1, n+1):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (n+1)
    fact_inv[n] = pow(factrial[n], MOD - 2, MOD)
    for k in range(n-1, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

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

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
else:
    k=(2*y-x)//3
    l=(2*x-y)//3
    a = comb_mod(k+l,l,10**9+7)
    print(a)
### BUGGY CODE ###

import copy
N,M=map(int,input().split())
D=[]
for _ in range(M):
    if _==0:
        LR=list(map(int,input().split()))
        for u in range(LR[0],LR[1]+1):
            D.append(u)
    else:
        LR=list(map(int,input().split()))
        DD=copy.deepcopy(D)
        for v in DD:
            if v not in range(LR[0],LR[1]+1):
                D.remove(v)
print(len(D))

### FIXED CODE ###

N,M=map(int,input().split())
LR=list(list(map(int,input().split())) for _ in range(M))
L=1
R=N
for i in range(M):
    L=max(L,LR[i][0])
    R=min(R,LR[i][1])
print(R-L+1 if L<=R else 0)
### BUGGY CODE ###

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

for i in range(k):
    tmpa = a[:]
    b = [0] * n
    for j in range(n):
        for k in range(-tmpa[j], tmpa[j] + 1):
            if 0 <= j + k < n:
                b[j + k] += 1
    a = b[:]
    if sum(a) == n ** 2:
        break

print(*b)

### FIXED CODE ###

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

for i in range(k):
    b = [0] * (n + 1)
    for j in range(n):
        b[max(0, j - a[j])] += 1
        b[min(n, j + a[j] + 1)] -= 1
    a = list(accumulate(b))
    if sum(a) == n ** 2:
        a.pop()
        print(*a)
        exit()

a.pop()
print(*a)
### BUGGY CODE ###

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

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

else:
    ans=0
    m=min(A)
    for i in d:
        if d[i]>1 or (i!=m and i%m==0):
            continue
        p=1
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                if j in d or i//j in d:
                    p=0
                    break
        ans+=p

print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
M=max(A)+1
table=[0 for _ in range(M)]

for i in range(N):
    if i>0 and A[i]==A[i-1]:
        table[A[i]]=0
        continue
    table[A[i]]=1
    for n in range(2,M):
        if A[i]*n>=M:
            break
        table[A[i]*n]=0
print(sum(table))