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

import sys
sys.setrecursionlimit(100000)

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

# 木
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

## クエリを覚えておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

# 和をとっていく
ans = [0]*N
ans[0] = scores[0]
used = [False] * N

def dfs(G, v):
   # vを訪問済みにする
   used[v] = True
   #グラフ中の次のVについて
   for next_v in G[v]:
       # すでに見られていたら無視
       if used[next_v]: continue
       # 見られていない場合、再帰的に探索
       # 親のスコアも足していく
       ans[next_v] = ans[v] + scores[next_v]
       dfs(G, next_v)

dfs(G,0)
print(*ans)


### FIXED CODE ###


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

# 木
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    G[u-1].append((v-1))
    G[v-1].append((u-1))

## クエリを覚えておく
scores = [0]*N
for i in range(Q):
    p,x = map(int, input().split())
    scores[p-1] += x 

# 和をとっていく
ans = [0]*N
ans[0] = scores[0]
used = [False] * N

"""
dfs TLEする。なんで
"""
# import sys
# sys.setrecursionlimit(100000)
# def dfs(G, v):
#    # vを訪問済みにする
#    used[v] = True
#    #グラフ中の次のVについて
#    for next_v in G[v]:
#        if used[next_v]: continue
#        ans[next_v] = ans[v] + scores[next_v]
#        dfs(G, next_v)
# dfs(G,0)
# print(*ans)

# 木をBFSをする
from collections import deque
used = [False] * N
used[0] = True # 始めどこから行くか
q = deque([0])
while len(q) > 0:
    v = q.popleft()
    Vs = G[v]
    for next_v in Vs: 
        if not used[next_v]:
            q.append(next_v)
            ans[next_v] = ans[v] + scores[next_v]
            used[next_v] = True
print(*ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 S(): return input()

def prime(num):
    m = int(math.sqrt(num)) + 1
    for i in range(2, m):
        if num % i == 0:
            return False
    return True

def main():
    gcd = fractions.gcd
    A, B = LI()
    m = gcd(A, B)
    cnt = 1
    for i in range(2, m + 1):
        if not prime(i):
            continue
        if m % i == 0:
            cnt += 1
    print(cnt)
main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 S(): return input()

def integer_factorization(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n //= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    return prime_count

prime = [True] * (10**6 + 2)
prime[1] = False
max_range = int(math.sqrt(10**6)) + 1

for i in range(2, 10**6 + 1):
    if not prime[i]:
        continue
    if prime[i]:
        num = i + i
        while num < max_range:
            prime[num] = False
            num += i

def main():
    gcd = fractions.gcd
    A, B = LI()
    m = gcd(A, B)
    cnt = 1
    cnt += len(integer_factorization(m))
    # for i in range(2, int(math.sqrt(m)) + 1):
    #     if m % i != 0:
    #         continue
    #     if prime[i]:
    #         cnt += 1
    print(cnt)
main()
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s_max = 0
max_i=0
ret = 0
s_list = [sum(p[i:i+k]) for i in range(n-k+1)]
s_max=max(s_list)
max_i=s_list.index(s_max)

for i in range(k):
  p_i = p[max_i+i]
  ret+=(1+p_i)*p_i/(2*p_i)
  
print(ret)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
max_i=0
ret = 0
p_s=sum(p[0:k])
s_max=p_s
for i in range(n-k):
  p_s=p_s-p[i]+p[i+k]
  if s_max<p_s:
    s_max=p_s

print(s_max/2+k/2)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = input()

perm = list(combinations(range(N), 3))
ans = 0
for i in range(len(perm)):
    a1 = perm[i][0]
    a2 = perm[i][1]
    a3 = perm[i][2]
    if a3-a2 == a2 - a1:
        continue
    if len(set([S[a1], S[a2], S[a3]])) == 3:
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')
sum_rgb = r*g*b

# rgbの組み合わせの総数から距離が等しいものを引く
for i in range(N-2):
    for j in range(i+1, N-1):
        k = j + (j-i)
        if k > N-1:
            continue
        if len(set([S[i], S[j], S[k]])) == 3:
            sum_rgb -= 1
print(sum_rgb)
### BUGGY CODE ###

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

d=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(d):
	r=list(map(int,input().split()))
	s.append(r)

def score(T):
	last=[0]*26
	happy=0
	for i in range(d):
		last[T[i]-1]=i+1
		happy+=s[i][T[i]-1]
		for j in range(26):
			happy-=(i+1-last[j])*c[j]
	return happy

t=[]
for i in range(d):
	t.append(i%26+1)

t2=time()
while t2-t1<1.9:
	tt=t.copy()
	tt[randint(1,d)-1]=randint(1,26)
	if score(tt)>score(t):
		t=tt.copy()
	t2=time()
for x in t:
	print(x)

### FIXED CODE ###

d=int(input())
c=list(map(int,input().split()))
s=[]
for i in range(d):
	r=list(map(int,input().split()))
	s.append(r)
for i in range(d):
	print(i%26+1)
### BUGGY CODE ###

import math
import itertools

def swap(a,b):
    return max(a,b),min(a,b)

def comb(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

N = int(input())
an = list(map(int,input().split()))
#an = [5,10,12]
an.sort()

max_v = 0
max_e = None
for i in an[:-1]:
    n,r = swap(an[-1], i)
    v = comb(n,r)
    if v > max_v:
        max_v = v
        max_e = (n,r)
    #print(c, comb(*c))

print(max_e[0], max_e[1])


### FIXED CODE ###

import math
import itertools

def swap(a,b):
    return max(a,b),min(a,b)

def comb(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

_ = input()
an = list(map(int,input().split()))
#an = [5,10,12]
an.sort()
target = an[-1]/2
res = min(enumerate(an), key=lambda x: abs(target - x[1]))
print(an[-1], res[1])
### BUGGY CODE ###

import sys
a = sys.stdin.read().split('\n')[:-1]
s = a[0]
q = int(a[1])
f = 1
for i in range(0, q):
    if a[2 + i][0] == '1':
        f = 1 - f
    if a[2 + i][0] == '2':
        if a[2 + i][2] == '21'[f]:
            s = a[2 + i][4] + s
        else:
            s += a[2 + i][4]
if f == 1:
    print(s)
else:
    b = ''
    for c in reversed(s):
        b += c
    print(b)

### FIXED CODE ###

import sys
a = sys.stdin.read().split('\n')[:-1]
q = int(a[1])
f = 1
l = [[], []]
for i in range(2, q + 2):
    if a[i][0] == '1':
        f = 1 - f
    else:
        l[0 if a[i][2] == '21'[f] else 1].append(a[i][4])
if f != 1:
    l[1].reverse()
    print(''.join(l[1]) + ''.join(reversed(list(a[0]))) + ''.join(l[0]))
else:
    l[0].reverse()
    print(''.join(l[0]) + a[0] + ''.join(l[1]))
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

pushed = [1]

while True:
  button = A[pushed[-1] - 1]
  if button in pushed:
    print("-1")
    break
  elif button == 2:
    print(len(pushed))
    break;
  else:
    pushed.append(button)

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

button = [0] * N
button[0] = 1
next_button = 1
i = 0

while True:
  button[next_button - 1] = 2
  next_button = A[next_button - 1]
  if button[next_button - 1] == 2:
    print("-1")
    break
  elif next_button == 2:
    i += 1
    print(i)
    break
  else:
    button[next_button - 1] = 1
    i += 1
### BUGGY CODE ###

n = int(input())
a = []
b = []
c = 0
for i in range(n):
 ak = int(input())
 a.append(ak)
a.sort()
for i in range(n-1):
 bk = a[i+1] -  a[i]
 b.append(bk)
if len(b) % 2 == 1:
 for i in range(len(b) // 2):
  c += sum(b[i:len(b)-i])*2
 c += b[len(b)//2]
else:
 for i in range(len(b) // 2):
  c += sum(b[i:len(b)-i])*2
 c -= min(b[len(b)//2-1],b[len(b)//2])
print(c)

### FIXED CODE ###

n = int(input())
a = []
b = []
d = []
c = 0
for i in range(n):
 ak = int(input())
 a.append(ak)
a.sort()
for i in range((len(a)-1)//2):
 d.append(a[-i-1]-a[i])
for i in range(n-1):
 bk = a[i+1] -  a[i]
 b.append(bk)
e = len(b)
c = sum(d) * 2
if e % 2 == 1:
 c += b[e//2]
else:
 c -= min(b[e//2-1],b[e//2])
print(c)
### BUGGY CODE ###

MOD = int(10**9 + 7)

N, K = map(int, input().split())
tot = [0]*(K+1)

for i in range(K,0,-1):
    tot[i] = (K//i)**N
    s = 2
    while s*i <= K:
        tot[i] -= tot[s*i]
        s += 1
        
ans = 0
for i in range(K+1):
    ans += ((tot[i]%MOD)*i)%MOD

print(ans%MOD)

### FIXED CODE ###

MOD = int(10**9 + 7)

def pow_mod(x, n, mod):
    if n > 1:
        return pow_mod(pow(x,2) % mod, n//2, mod) * pow(x, n%2) % mod
    else:
        return x


N, K = map(int, input().split())
tot = [0]*(K+1)

for i in range(K,0,-1):
    tot[i] = pow_mod(K//i, N, MOD)
    s = 2
    while s*i <= K:
        tot[i] -= tot[s*i]
        s += 1
        
ans = 0
for i in range(K+1):
    ans += ((tot[i]%MOD)*i)%MOD

print(ans%MOD)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a,b,c=[list(map(int,input().split())) for i in range(3)]
l=sorted([bb+cc for bb in b for cc in c],reverse=1)[:k]
t=sorted([ll+aa for aa in a for ll in l],reverse=1)
for i in range(k):
    print(t[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a,b,c=[list(map(int,input().split())) for i in range(3)]
l=sorted([bb+cc for bb in b for cc in c],reverse=1)[:k]
t=sorted([ll+aa for aa in a for ll in l],reverse=1)
for i in range(k):
    print(t[i])
### BUGGY CODE ###

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

import numpy as np

# TESTCASE #
test = ""
#test = \
"""
3 2
5 1 4
2 3
1 5
ans:
14
"""

"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
ans:
338
"""

"""
3 2
100 100 100
3 99
3 99
ans:
300
"""

"""
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
ans:
10000000001
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
### MAIN ###
        
n, m = map(int, input2().split())
a = np.array(list(map(int, input2().split())))
bcs = [tuple(map(int, input2().split())) for _ in range(m)]
bcs.sort()

for query in bcs:
    
    a.sort()
    a[:query[0]] = np.maximum(a[:query[0]], query[1])
    
    
print(np.sum(a))
    










### FIXED CODE ###

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

import numpy as np

# TESTCASE #
test = ""
#test = \
"""
3 2
5 1 4
2 3
1 5
ans:
14
"""

"""
10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4
ans:
338
"""

"""
3 2
100 100 100
3 99
3 99
ans:
300
"""

"""
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000
ans:
10000000001
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
### MAIN ###
        
n, m = map(int, input2().split())
a = np.array(list(map(int, input2().split())), dtype="int64")
bcs = [tuple(map(int, input2().split()))[::-1] for _ in range(m)]

a.sort()
bcs = sorted(bcs, reverse=True)

i = 0
for query in bcs:
    #print(query)
    a[i:i+query[1]] = np.maximum(a[i:i+query[1]], query[0])
    i += query[1]
    #print(a)    
print(np.sum(a))
### BUGGY CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]

#pp = [max(ls[i:])-x for i, x in enumerate(ls, 1) if i != len(ls)]

p = min(ls) - max(ls)

for i, x in enumerate(ls, 1):
    if i == len(ls):
        break
    if max(ls[i:]) - x > p:
        p = max(ls[i:]) - x

print(p)



### FIXED CODE ###

n = int(input())
m = [int(input()) for _ in range(n)]

def fx(raw):
    min_n = raw[0]
    max_n = raw[1] - raw[0]
    for i in raw[1:]:
        if i - min_n >= max_n:
            max_n = i - min_n
        if i < min_n:
            min_n = i
    return max_n


if __name__ == '__main__':
    print(fx(m))
### BUGGY CODE ###

H, W, M = map(int,input().split())

X = [0] * H
Y = [0] * W

A = []
while M:
    M -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    X[x] += 1
    Y[y] += 1

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = False
for i in xms:
    for j in yms:
        if not (i, j) in A:
            ans = True
  
cnt = xm + ym         
print(cnt if ans else cnt - 1)

### FIXED CODE ###

import sys

input = sys.stdin.readline
H, W, M = map(int,input().split())
q=set(tuple(map(lambda x :int(x)-1,input().split())) for _ in range(M))

X = [0] * H
Y = [0] * W

for i, j in q:
    X[i] += 1
    Y[j] += 1
    
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = xm + ym - 1

bl = False
for i in xms:
    for j in yms:
        if not (i, j) in q:
            print(ans + 1)
            sys.exit()
            bl = True
            
print(ans)
### BUGGY CODE ###

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

As = input().split()
A = [0]*N

for n in range(N): 
  A[n] = float(int(As[n]))
A.sort()

for m in range(M):
  
  midx = 0
  mval = 0
  for n in range(N):
    if mval<A[n]:
      mval = A[n]
      midx = n
  A[midx]=A[midx]/2.0
  
Asum = 0
for n in range(N):
  Asum += int(A[n])
print(Asum)

### FIXED CODE ###

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

As = input().split()
A = [0]*N

for n in range(N): 
  A[n] = float(int(As[n]))+0.1
A.sort()

tid = [0]*M
ct = -1
cid = -1
ms = 0

for m in range(M):
  if ct==-1:
    A[N-1] = A[N-1]/2.0
    tid[0] = N-1
    ct = 1
    cid = 0
  else:
    if N-1-m+ms<0 or A[tid[cid]]>A[N-1-m+ms]:
      A[tid[cid]] = A[tid[cid]]/2.0
      tid[ct] = tid[cid]
      ct += 1
      cid += 1
      ms+=1
    else:
      A[N-1-m+ms] = A[N-1-m+ms]/2.0
      tid[ct] = N-1-m+ms
      ct += 1

Asum = 0
for n in range(N):
  Asum += int(A[n])
print(Asum)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
s=input()
s=list(s.replace('BC','Z'))
ans=0
 
def seisan(list):
    count=0
    N=len(list)-1
    for index,content in enumerate(list):
        if content=="A":
            count+=(N-index)
            N-=1
    return count

temp=[]
while s:
    this=s.pop(0)
    if this=="B" or this=="C":
        ans+=seisan(temp)
        temp.clear()
    else:
        temp.append(this)

print(ans+seisan(temp))


### FIXED CODE ###

# coding: utf-8
# Your code here!
s=list(input().replace("BC","Z"))[::-1]
ans=0

def seisan(list):
    count=0
    N=len(list)-1
    for index,content in enumerate(list):
        if content=="A":
            count+=(N-index)
            N-=1
    return count

temp=[]
while s:
    this=s.pop(-1)
    if this=="B" or this=="C":
        ans+=seisan(temp)
        temp.clear()
    else:
        temp.append(this)

print(ans+seisan(temp))
#ちょくだいさん連投ゆるして
### BUGGY CODE ###

N,K=map(int,input().split())
a=[int(i) for i in input().split()]
mask=(1<<(K))-1
a.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(N):
  dp[i+1]=(dp[i]|(dp[i]<<a[i]))&mask

def solve(x):
  if (dp[x]<<a[x])>=1<<K:
    return True
  else:
    return False
  
for i in range(-1,N)[::-1]:
  if solve(i):
    break
    
print(N-i-1)

### FIXED CODE ###

from bisect import bisect_left
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
a=a[:bisect_left(a,K)]
d=[False]*(K)
d[0]=True
curr_max=0
ans=len(a)
for i,a in reversed(list(enumerate(a))):
  if curr_max+a>=K:
    ans=i
  c=curr_max
  for j in range(curr_max+1)[::-1]:
    if j+a<K and d[j]:
      d[j+a]=True
      c=max(c,j+a)
  curr_max=c
print(ans)
### BUGGY CODE ###

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

count = 0
for i in range(n):
  a = p[i]
  alist = p[:i+1]
  alist.sort()
  if alist[0] == a:
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
p = list(map(lambda x: int(x), input().split()))
 
count = 0
maxs = p[0]
for i in range(n):
  if maxs >= p[i]:
    maxs = p[i]
    count += 1
print(count)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
li = list(map(int, input().split()))
di = {}
for i, d in enumerate([2,5,5,4,5,6,3,7,6], 1):
    di[i] = d

# honsuu list
ns = set()
# honsuu-> disit list
n2d = {}
for a in li:
    hon = di[a]
    ns.add(hon)
    if (hon not in n2d) or (n2d[hon] < a):
        n2d[hon] = a
ns = list(ns)
ns.sort(reverse=True)

from collections import Counter, deque
cnt = Counter()
Q = deque()
for hon in ns:
    if n - hon >= 0:
        Q.append(((hon,), n - hon))
ma = 0
mali = []
while len(Q) > 0:
    lis, remain = Q.pop()
    if remain == 0 and len(lis) > ma:
        ma = len(lis)
        mali = lis
    for hon in ns:
        if remain - hon >= 0:
            Q.append((lis + (hon,), remain - hon))

digits = [n2d[n] for n in mali]
digits.sort(reverse=True)

print(*digits, sep='')


### FIXED CODE ###

n, m = list(map(int, input().split()))
li = list(map(int, input().split()))
di = {}
for i, d in enumerate([2,5,5,4,5,6,3,7,6], 1):
    di[i] = d
li.sort(reverse=True)
dd = {}
for a in li:
    hon = di[a]
    if hon not in dd:
        dd[hon] = a

h2d = [-float('inf')] * (n + 1)
h2d[0] = 0
pre = [None] * (n + 1)
for j in range(1, n + 1):
    for a in li:
        ho = di[a]
        if j < ho:
            continue
        dig = h2d[j - ho] + 1
        if dig > h2d[j]:
            h2d[j] = dig
            pre[j] = j - ho

ans = []
while n > 0:
    ans.append(dd[n - pre[n]])
    n = pre[n]
ans.sort(reverse=True)
print(*ans, sep='')
### BUGGY CODE ###

MOD = 10 ** 9 + 7

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
    exit()
time = (X+Y) // 3
diff = X - Y
if abs(diff) > time:
    print(0)
    exit()
x_time = (time+diff) // 2
res = 1
for i in range(1,time+1):
    res = res*i%MOD
for i in range(1,x_time+1):
    res = res*mod_inv(i,MOD)%MOD
for i in range(1,time-x_time+1):
    res = res*mod_inv(i, MOD)%MOD
print(res)
#print(mod_combination(time, x_time, MOD))


### FIXED CODE ###

import numpy as np
from math import factorial
MOD = 10 ** 9 + 7

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv



U = 10**6
fact, fact_inv = make_fact(U,MOD)

X, Y = map(int, input().split())
if (X + Y) % 3 != 0:
    print(0)
    exit()
time = (X+Y) // 3
diff = X - Y
if abs(diff) > time:
    print(0)
    exit()
x_time = (time+diff) // 2

answer = fact[time] * fact_inv[x_time] % MOD * fact_inv[time-x_time] % MOD
print(answer)
### BUGGY CODE ###

import fractions
from functools import reduce


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


N = int(input())
a = list(map(int, input().split()))
ans = [0]*N
for i in range(0, N):
    tmp = a.pop(0)
    ans[i] = gcd_list(a)
    a.append(tmp)

ans.sort()
print(ans[N-1])


### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
L = [0] * n
R = [0] * n
for i in range(1, n):
    L[i] = fractions.gcd(a[i - 1], L[i - 1])
    R[n - 1 - i] = fractions.gcd(a[n - i], R[n - i])
for i in range(0, n):
    ans[i] = fractions.gcd(L[i], R[i])
ans.sort()
print(ans[n - 1])
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
password = [0, 0, 0]
flag = False
for i in range(1000):
    for j in range(3):
        password[j] = i // (10 ** j) % 10
    index = 2
    for k in range(n):
        if password[index] == int(s[k]):
            index -= 1
        if index == -1:
            ans += 1
            break
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
password = [0, 0, 0]
for i in range(1000):
    for j in range(3):
        password[2 - j] = i // (10 ** j) % 10
    if str(password[0]) in s:
        index = s.index(str(password[0]))
        if str(password[1]) in s[index + 1:]:
            index2 = index + 1 + s[index + 1:].index(str(password[1]))
            if str(password[2]) in s[index2 + 1:]:
                ans += 1
print(ans)
### BUGGY CODE ###


N = int(input())
S = input()
ans = 0
anslst = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            anslst.append(str(i) + str(j) + str(k))

tmp = ans
for i in anslst:
    for j in range(N):
        if i[0] == S[j]:
            for k in range(j + 1, N):
                if i[1] == S[k]:
                    for n in range(k + 1, N):
                        if i[2] == S[n]:
                            ans += 1
                            break
                    break
        if tmp != ans:
            tmp = ans
            break
print(ans)

### FIXED CODE ###


N = int(input())
S = input()
ans = 0
anslst = []
for i in range(10):
    for j in range(10):
        for k in range(10):
            anslst.append(str(i) + str(j) + str(k))

tmp = ans
for i in anslst:
    a, b, c = i
    index1 = S.find(a)
    index2 = S.find(b, index1 + 1)
    index3 = S.find(c, index2 + 1)
    if index1 != -1 and index2 != -1 and index3 != -1:
        ans += 1
print(ans)
### BUGGY CODE ###

N, M, Q = list(map(int, input().split(' ')))
LR = []
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    LR.append((l, r))
pq = []
for i in range(Q):
    p, q = list(map(int, input().split(' ')))
    pq.append((p, q))

memo = {}
for p, q in pq:
    if (p, q) not in memo:
        memo[(p, q)] = sum([(p <= l and r <= q) for l, r in LR])
    print(memo[(p, q)])


### FIXED CODE ###

N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_g = {}
def g(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_g:
        memo_g[(p, q)] = st_ed.get((p, q), 0) + g(p + 1, q)
    return memo_g[(p, q)]

memo_f = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_f:
        temp = f(p, q - 1) + g(p, q)
        memo_f[(p, q)] = temp
    return memo_f[(p, q)]

memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])
### BUGGY CODE ###

j=lambda:map(int,raw_input().split())
n,q=j()
c=[1,-1,1]+[0]*(n-2)+[1]
for p in[-1]*q:a,b=j();c[a],c[b]=c[b],c[a];i=c.index(p);c[i-1]=c[i+1]=1
print sum(c)

### FIXED CODE ###

j=lambda:map(int,raw_input().split())
n,q=j()
u=1
c=[1]*3+[0]*(n-2)+[1]
for p in[-1]*q:a,b=d=j();u+=u in d and a+b-2*u;c[a],c[b]=c[b],c[a];c[u-1]=c[u+1]=1
print sum(c)-2