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

N = int(input())

# 最初の符号
print(0, flush=True)
first = input()

if first == 'Vacant':
    exit()

if first == 'Male':
    first = 1
else:
    first = -1

notHas = 0
has = N - 1

while has - notHas > 1:
    mid = (notHas + has) // 2
    print(mid, flush=True)
    ret = input()

    if ret == 'Vacant':
        exit()

    if ret == 'Male':
        ret = 1
    else:
        ret = -1

    trueValue = first * (-1)**(mid % 2 + 1)
    if ret == trueValue:
        notHas = mid
    else:
        has = mid

print(has, flush=True)
input()
exit()

### FIXED CODE ###

N = int(input())

# 最初の符号
print(0, flush=True)
first = input()

if first == 'Vacant':
    exit()

if first == 'Male':
    first = 1
else:
    first = -1

notHas = 1
has = N - 1

while has - notHas > 1:
    mid = (notHas + has) // 2
    print(mid, flush=True)
    ret = input()

    if ret == 'Vacant':
        exit()

    if ret == 'Male':
        ret = 1
    else:
        ret = -1

    trueValue = first * (-1)**(mid % 2)
    if ret == trueValue:
        notHas = mid
    else:
        has = mid

print(notHas, flush=True)
ret = input()

if ret == 'Vacant':
    exit()

print(has, flush=True)
input()
exit()
### BUGGY CODE ###

from math import sqrt

def func(num):
    if num < 6:
        return 0
    for i in range(2, lim_n+1):
        for j in range(2, i+1):
            for k in range(2, j+1):
                p = i**2 + j ** 2 + k ** 2
                if p > 2 * num:
                    break
                elif p == 2 * num:
                    if (j + k) - i != 0 and ((j + k) - i) % 2 == 0:
                        if i == j and j == k:
                            if i  % 2 ==1:
                                break
                            return 1
                        elif i != j and j != k:
                            return 6
                        else:
                            return 3
                        
    return 0

n = int(input())
lim_n = int(sqrt(n))
for i in range(1, n+1):
    print(func(i))

### FIXED CODE ###

from math import sqrt

n = int(input())
lim_n = int(sqrt(n*2))
result = [0] * n

for i in range(2, lim_n+1):
    for j in range(2, i+1):
        for k in range(2, j+1):
            p = i**2+j**2+k**2
            if p > 2*n:
                break
            if p % 2 == 1:
                continue
            if (j + k) - i < 2:
                continue
            if i == j and j == k:
                if i  % 2 ==1:
                    continue
                result[p//2-1] += 1
            elif i != j and j != k:
                result[p//2-1] += 6
            else:
                result[p//2-1] += 3

for item in result:
    print(item)
### BUGGY CODE ###

n = int(input())

ans = []

for i in range(n):
  s = input()
  if s in ans:
    pass
  else:
    ans.append(s)

print(len(ans))

### FIXED CODE ###

n = int(input())

s = [input() for _ in range(n)]

print(len(set(s)))
### BUGGY CODE ###

import sys
def check(S):
    stop = True
    if len(S) < 2:
        print(base_S_length - len(S))
        sys.exit()
    for i in range(len(S) - 1):
        if (S[i] + S[i + 1]) == 1:
            S[i] = S[i + 1] = 2
            stop = False    
    if stop:
        print(base_S_length - len(S))
        sys.exit()
    S = list(filter(lambda a: a != 2, S))
    check(S)

S = list(map(int, list(input())))
base_S_length = len(S)
check(S)

### FIXED CODE ###

def main():
    S = list(map(int, list(input())))

    cnt1 = sum(S)
    cnt0 = len(S) - cnt1
    print(2 * min(cnt0, cnt1))


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

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[['' for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+s[i]
            else:
                if len(dp[i+1][j])>len(dp[i][j+1]):
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    print(dp[n][m])
if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                if dp[i+1][j]>dp[i][j+1]:
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()
### BUGGY CODE ###

import fractions

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

def lcm(x, y):
	return (x * y) // fractions.gcd(x, y)

num = a[0]
for i in range(1, n):
	num = lcm(num, a[i])

ans = 0
for i in range(n):
	ans += (num//a[i]) % 1000000007
	if ans > 1000000007:
		ans = ans%1000000007

print(ans)

### FIXED CODE ###

import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for i in range(n):
	l = l // fractions.gcd(l, a[i])*a[i]
 
ans = 0
for i in range(n):
	ans += l//a[i]
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
n = int(input())
a = [int(n) for n in input().split()]
sum = [0]*n
sum[0] = a[0]
ans = 0
for i in range(1,n):
    sum[i] = sum[i-1]
    while((sum[i]+a[i])*sum[i-1] >= 0):
        if(sum[i-1] > 0):
            a[i]-=1
            ans+=1
        else:
            a[i]+=1
            ans+=1
        # print(a)
    sum[i] += a[i]
print(ans)
# print(a)
# print(sum)


### FIXED CODE ###

import sys
N = int(input())
a = [int(_) for _ in input().split()]

#+,-,+,-
asum = [0]*(N)
ansp = 0
if(a[0] <= 0):
    ansp+=1-a[0]
    asum[0]=1
else:
    asum[0] = a[0]
for i in range(1,N):
    asum[i] = asum[i-1] + a[i]
    if(asum[i-1]*asum[i] >= 0):
        if(asum[i-1]>0):
            ansp+=1+asum[i]
            asum[i]=-1
        else:
            ansp+=1-asum[i]
            asum[i]=1
# print(asum)
# print(ansp)
#-,+,-,+,,,
ansn = 0
if(a[0] >= 0 ):
    ansn+=1+a[0]
    asum[0]=-1
else:
    asum[0] = a[0]
for i in range(1,N):
    asum[i] = asum[i-1] + a[i]
    if(asum[i-1]*asum[i] >= 0):
        if(asum[i-1]>0):
            ansn+=1+asum[i]
            asum[i]=-1
        else:
            ansn+=1-asum[i]
            asum[i]=1
# print(asum)
# print(ansn)
print(min(ansp,ansn))
### BUGGY CODE ###

N, K = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]

x = 1
for i in range(N):
    x_before = x
    x = x * A[i]
    if i >= K:
        x = x / A[i - K]
        if x > x_before:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

N, K = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]

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

import sys
input = sys.stdin.readline
H,W = map(int,input().split())
Gd,L,R,U,D=[None]*H,[None]*H,[None]*H,[None]*H,[None]*H
for _ in range(H):
  Gd[_] = list(input())
  L[_], R[_], D[_], U[_] = [0]*W, [0]*W, [0]*W, [0]*W
for h in range(H):
  for w in range(W):
    if Gd[h][w]=='#':
      R[h][w]=0
    else:
      if w==0:
        R[h][w]=1
      else:
        R[h][w]=R[h][w-1]+1
    wr=W-w-1
    if Gd[h][wr]=='#':
      L[h][wr]=0
    else:
      if w==0:
        L[h][wr]=1
      else:
        L[h][wr]=L[h][wr+1]+1

for w in range(W):
  for h in range(H):
    if Gd[h][w]=='#':
      D[h][w]=0
    else:
      if h==0:
        D[h][w]=1
      else:
        D[h][w]=D[h-1][w]+1
    hr=H-h-1
    if Gd[hr][w]=='#':
      U[hr][w]=0
    else:
      if h==0:
        U[hr][w]=1
      else:
        U[hr][w]=U[hr+1][w]+1
ret = 0
for w in range(W):
  for h in range(H):
    ret = max(ret, D[h][w]+U[h][w]+R[h][w]+L[h][w]-3)
print(ret)

### FIXED CODE ###

import numpy as np
H,W = map(int,input().split())
HL=list(range(H))
WL=list(range(W))
Gd = np.array([list(input()) for _ in HL])
Gd = np.where(Gd=='.', 1, 0)
L=np.zeros((H,W),dtype=np.int64)
R=np.zeros((H,W),dtype=np.int64)
U=np.zeros((H,W),dtype=np.int64)
D=np.zeros((H,W),dtype=np.int64)

for w in WL:
  R[:,w]=(R[:,w-1]+1)*Gd[:,w]
  L[:,-w-1]=(L[:,-w]+1)*Gd[:,-w-1]
for h in HL:
  D[h,:]=(D[h-1,:]+1)*Gd[h,:]
  U[-h-1,:]=(U[-h,:]+1)*Gd[-h-1,:]
print(np.max(D+U+L+R-3))
### BUGGY CODE ###

import math
from decimal import Decimal
 
n = int(input())
 
if n == 0:
  print(':(')
else:
  for i in range(1, n):
    if math.floor(Decimal(str(i)) * Decimal("1.08")) == n:
      print(i)
      break
  else:
    while True:
      pass

### FIXED CODE ###

n = int(input())
 
ans = -1
for i in range(1, n+1):
  if int(i  * 1.08) == n:
    ans = i
if ans == -1:
  print(':(')
else:
  print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

sum = 0

for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i] * A[j]
            
        
print(sum % (10**9+7))

### FIXED CODE ###

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

sum = 0
B = []
B.append(0)

for t in range(N):
    B.append(A[t] + B[t])
    
B.remove(0)
    
for i in range(N):
    sum += A[i] * (B[N-1] - B[i])
        
print(sum % (10**9+7))
### BUGGY CODE ###

import itertools

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

taisen = list(itertools.combinations(range(n), 2))
taisen_dic = {}
for i in range(len(taisen)):
    taisen_dic[taisen[i]] = i

B = [[0] * (n-1) for i in range(n)]

for i in range(n):
    for j in range(n-1):
        key0, key1 = min(i, A[i][j]), max(i, A[i][j])
        B[i][j] = taisen_dic[(key0, key1)]

#print(B)

nn = len(taisen)

P = [0] * nn

for k in range(nn):
    #print(P)
    for i in range(n):
        for j in range(n-2):
            P[B[i][j+1]] = max(P[B[i][j+1]], P[B[i][j]] + 1)

P_n = P[:]

for k in range(1):
    for i in range(n):
        for j in range(n-2):
            P[B[i][j+1]] = max(P[B[i][j+1]], P[B[i][j]] + 1)


if P_n != P:
    print(-1)
else:
    print(max(P) + 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで
### BUGGY CODE ###

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

N = min(X,Y,Z)
ans = []
SUM = []
for i in range(N):
    SUM.append(A[i]+B[i]+C[i])

for i in range(N):
    ans = []
    for j in range(X):
        flag2 = 0
        for k in range(Y):
            flag = 0
            for l in range(Z):
                if A[j]+B[k]+C[l] >= SUM[i]:
                    ans.append(A[j]+B[k]+C[l])
                else: 
                    if l == 0:
                        flag = 1
                    break
            if k == 0 and flag == 1:
                flag2 = 1
                break
        if flag2 == 1:
            break
    if len(ans) >= K:
        break

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

### FIXED CODE ###

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

ans = []

for j in range(X):
    if j+1 > K:
        break
    for k in range(Y):
        if j*k+1 > K:
            break
        for l in range(Z):
            if j*k*l+1 <= K:
                ans.append(A[j]+B[k]+C[l])
            else: 
                break
                
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

def calc_lcs(X, Y):
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = [[0]*1001 for i in range(1000+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i][j - 1], c[i - 1][j]) 
            max_lcs = max(max_lcs, c[i][j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())

    for _ in range(num):
        X = input()
        Y = input()
        # X = 'abcbdab'
        # Y = 'bdcaba'


        # ???????????????
        result = calc_lcs(X, Y)

        # ???????????¨???
        print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    return c


def check_max(array):
    """ 2次元配列の中の最大の値を返す """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(K: int, S: int):
    count = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if x + y + z == S:
                    count += 1
    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(K, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(K: int, S: int):
    count = 0
    for x in range(K+1):
        for y in range(K+1):
            if 0 <= S - x - y <= K:
                count += 1
    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    solve(K, S)

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

import sys
sys.setrecursionlimit(10**6)
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

ans = [0]*n

for i in range(q):
    p,x = map(int,input().split()) 
    ans[p-1] += x

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)

dfs()

print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

ans = [0]*n

for i in range(q):
    p,x = map(int,input().split()) 
    ans[p-1] += x

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)

dfs()

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

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if sum(a) == sum(b):
    if a == b:
        print("Yes")
    else:
        print("No")
elif sum(a) > sum(b):
    print("No")
else:
    for i in range(sum(b)-sum(a)):
        for j in range(N):
            if a[j] < b[j]:
                a[j] += 2
                break
        if (abs(a[j]-b[j]))%2 == 1:
            b[j] += 1
        else:
            for k in range(N):
                flg = 0
                if b[k] < a[k]:
                    b[k] += 1
                    flg = 1
                    break
            if flg == 0:
                b[0] += 1
    if a == b:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if a == b:
    print("Yes")
elif sum(a) >= sum(b):
    print("No")
else:
    aa = 0
    bb = 0
    for i in range(N):
        if a[i]-b[i] > 0:
            bb += a[i]-b[i]
        elif b[i]-a[i] > 0:
            aa += (b[i]-a[i])//2
    if aa >= bb:
        print("Yes")
    else: 
        print("No")
### BUGGY CODE ###

from itertools import *
N,Y = map(int,input().split())
if 10000*N < Y:
  print(-1,-1,-1)
  exit()
for i in range(N):
  for j in range(N-i):
    k = N-i-j
    for xyz in permutations([i,j,k],3):
      x,y,z = xyz
      if 10000*x + 5000*y + 1000*z == Y:
        print(x,y,z)
        exit()
print(-1,-1,-1)

### FIXED CODE ###

from itertools import *
N,Y = map(int,input().split())
if 10000*N < Y:
  print(-1,-1,-1)
  exit()
for i in range(N):
  for j in range(N-i):
    k = N-i-j
    for xyz in permutations([i,j,k],3):
      x,y,z = xyz
      if 10000*x + 5000*y + 1000*z == Y:
        print(x,y,z)
        exit()
print(-1,-1,-1)
### BUGGY CODE ###

import collections
S = input()
S = S[::-1]
d = 1
mods = [0]
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  d *= 10
  
c = collections.Counter(mods)
result = 0
for i,j in c.most_common():
  if j >= 2:
    result += j*(j-1)//2
print(result)

### FIXED CODE ###

S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
result = 0
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  result += counter[mods[-1]] - 1
  d *= 10
  d %= 2019

print(result)
### BUGGY CODE ###

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

l = 1
r = 3
w = a[0]
x = a[1]
y = a[2]
z = sum(a[3:])
result = max(w,x,y,z) - min(w,x,y,z)

for i in range(2, n - 1):
    if r == i:
        r += 1
    w = sum(a[:l])
    x = sum(a[l:i])
    res_l = abs(w - x)
    y = sum(a[i:r])
    z = sum(a[r:])
    res_r = abs(y - z)
    temp = l
    while temp < i:
        p = sum(a[:temp])
        q = sum(a[temp:i])
        sum_temp = abs(q - p)
        if sum_temp < res_l:
            res_l = sum_temp
            l = temp
            w = p
            x = q
        if p >= q:
            break
        temp += 1
    temp = r
    while temp < n:
        p = sum(a[i:temp])
        q = sum(a[temp:])
        sum_temp = abs(q - p)
        if sum_temp < res_r:
            res_r = sum_temp
            r = temp
            y = p
            z = q
        if p >= q:
            break
        temp += 1
    temp_res = max(w,x,y,z) - min(w,x,y,z)
#    print(temp_res, w, x, y, z, l, i, r)
    if temp_res < result:
        result = temp_res

print(result)

### FIXED CODE ###

from functools import reduce

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

left = 0
right = 2
p = a[0]
q = a[1]
r = a[2]
s = reduce(lambda x, y: x + y, a[3:])
temp = right + 1
res_right = abs(s - r)
x = r
y = s
while temp < n - 1:
    x += a[temp]
    y -= a[temp]
    if abs(x - y) < res_right:
        right = temp
        r = x
        s = y
        res_right = abs(x - y)
    if x >= y:
        break
    temp += 1
result = max(p,q,r,s) - min(p,q,r,s)

for i in range(2, n - 2):
    q += a[i]
    r -= a[i]
    if i == right:
        right += 1
        r += a[i + 1]
        s -= a[i + 1]
    res_left = abs(p - q)
    res_right = abs(r - s)
    temp = left + 1
    x = p
    y = q
    while temp < i:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_left:
            left = temp
            p = x
            q = y
            res_left = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp = right + 1
    x = r
    y = s
    while temp < n - 1:
        x += a[temp]
        y -= a[temp]
        if abs(x - y) < res_right:
            right = temp
            r = x
            s = y
            res_right = abs(x - y)
        if x >= y:
            break
        temp += 1
    temp_res = max(p, q, r, s) - min(p, q, r, s)
    if temp_res < result:
        result = temp_res

print(result)
### BUGGY CODE ###

from scipy.misc import comb

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

if ((x+y)%3 != 0):
    print(0)
    exit()
else:
    n1 = (-x+2*y)//3
    n2 = (2*x -y)//3
    npath = comb(n1+n2, n1, exact=True)
    print(npath % (10**9+7))


### FIXED CODE ###

# 法Pの下での組み合わせ数 nCk を求める
# MAX: nの最大値

P = (10**9)+7

fac=[]
inv=[]
finv=[]

# 拡張ユークリッドアルゴリズム
# (d, x, y): d=ax+by を満たすd, x, yを求める
# aとbが互いに素な整数であればgcd(a,b)=d=1, ax=1 (mod b)
# xは法bの元でaの乗法逆元a^-1になる
def exEuclid(a, b):
    if (b==0):
        return (a, 1, 0)
    else:
        (dd, xx, yy) = exEuclid(b, a % b)
        return (dd, yy, xx - (a//b)*yy)

def COMinit(MAX):
    global fac, inv, finv
    fac=[1 for _ in range(MAX)]
    inv=[1 for _ in range(MAX)]
    finv=[1 for _ in range(MAX)]
    #print('len(fac): {}'.format(len(fac)))
    #print(MAX)
    for i in range(2,MAX):
        #print(i)
        fac[i] = fac[i-1]*i % P
        (d, x, y) = exEuclid(i, P)
        inv[i] = x
        finv[i] = finv[i-1]*inv[i] % P

def COM(n, k):
    if(n<k):
        return 0
    elif ( (n<0)or(k<0)):
        return 0
    else:
        return fac[n]*(finv[n-k]*finv[k] % P) % P

####

#print('x, y:')
x, y = list(map(int,input().split()))
MAX = (x+y)//3 +1  # (X+Y)/3より大きい整数 1 <= X, Y <= 10**6
COMinit(MAX)

if ((x+y)%3 != 0):
    print(0)
    exit()
else:
    n1 = (-x+2*y)//3
    n2 = (2*x -y)//3
    if (n1<0):
        print(0)
        exit()
    elif(n2<0):
        print(0)
        exit()
    else:
        npath = COM(n1+n2, n1)
        print(npath)