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

import heapq

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

def dikstra(sh, sw):
    reached[sh][sw] = 0
    tmp = [(0, sh, sw)]
    heapq.heapify(tmp)
    while tmp:
        c, h, w = heapq.heappop(tmp)
        if c > reached[h][w]:
            continue
        for i in range(4):
            cost = 0
            nh = h + dh[i]
            nw = w + dw[i]
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if maze[nh][nw] == "#":
                continue
            if reached[nh][nw] > reached[h][w] + cost:
                reached[nh][nw] = reached[h][w] + cost
                heapq.heappush(tmp,(reached[nh][nw], nh, nw))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                cost = 1
                nh = h + i
                nw = w + j
                if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                    continue
                if maze[nh][nw] == "#":
                    continue
                if reached[nh][nw] > reached[h][w] + cost:
                    reached[nh][nw] = reached[h][w] + cost
                    heapq.heappush(tmp,(reached[nh][nw], nh, nw))
                

dikstra(Ch, Cw)
ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

INF = 1e10
maze = []

dh = [-1,0,1,0]
dw = [0,1,0,-1]

for i in range(H):
    tmp = list(input())
    maze.append(tmp)

reached = [[INF]*W for _ in range(H)]

l = deque()
l.appendleft((Ch, Cw))
reached[Ch][Cw] = 0
while l:
    h, w = l.popleft()
    d = reached[h][w]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
            continue
        if not maze[nh][nw] != "#":
            continue
        if not reached[nh][nw] > d:
            continue
        reached[nh][nw] = d
        l.appendleft((nh, nw))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nh = h + i
            nw = w + j
            if not (0 <= nh <= H-1 and 0 <= nw <= W-1):
                continue
            if not maze[nh][nw] != "#":
                continue
            if not reached[nh][nw] > d + 1:
                continue
            reached[nh][nw] = d + 1
            l.append((nh, nw))

ans = reached[Dh][Dw]
if ans != INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
MOD = 1000000007
INF = float("inf")

N = I()
p = [float(x) for x in input().split()]

dp = FILL(0,N+1,N+1)
dp[0][0] = 1
dp[0][1] = 0
for i in range(N):
    for f in range(N+1):
        if f == 0:
            dp[i+1][f] = dp[i][f]*(1-p[i])
        else:
            dp[i+1][f] = dp[i][f]*(1-p[i]) + dp[i][f-1]*p[i]
ans = 0
for i in range(N+1):
    if i>N/2:
        ans += dp[N][i]
print(ans)

### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
P = list(map(float,input().split()))
dp = FILL2(0,N+3,N+3)
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] += dp[i][j]*P[i]
        dp[i+1][j] += dp[i][j]*(1-P[i])
print(sum(dp[N][N//2+1:]))
### BUGGY CODE ###

N, K, Q = map(int, input().split(' '))
score = [K for player in range(N)]

for question in range(Q):
    index = int(input())
    for i in range(N):
        if i != index - 1:
            score[i] = score[i] - 1

for result in score:
    if result > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split(' '))
score = [K for player in range(N)]
answers = [int(input()) - 1 for q in range(Q)]

for answer in answers:
    score[answer] = score[answer] + 1

score = [point - Q for point in score]

for result in score:
    if result > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

line = input().split(" ")
A = int(line[0])
B = int(line[1])
N = int(line[2])
max = 0
for x in reversed(range(N+1)):
    S = int(A * x / B) - A * int(x / B)
    
    if max<S:
        max = S
    if int(x/B) == 0:
        break
print(max)

### FIXED CODE ###

line = input().split(" ")
A = int(line[0])
B = int(line[1])
N = int(line[2])
max = 0
if B<N:
    K = B
    for i in range(-1, 2):
       if max< (int(A * (K + i) / B) - A * int((K + i) / B)):
           max = int(A * (K + i) / B) - A * int((K + i) / B)
else:
    K = N
    for i in range(-1, 1):
        if max< (int(A * (K + i) / B) - A * int((K + i) / B)):
            max = int(A * (K + i) / B) - A * int((K + i) / B)
print(max)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2 ** 30)

def fact(n):
    if n == 0: return 1
    return n * fact(n-1)


N, M=map(int,input().split())
if(abs(N%1000000007-M%1000000007)>1):
    i=0
else:
    i=fact(M%1000000007)*fact(N%1000000007)
if(N==M):
    i=i*2
ans=i%1000000007
print(ans)

### FIXED CODE ###

import sys
import math

N, M=map(int,input().split())
if(abs(N%1000000007-M%1000000007)>1):
    i=0
else:
    i=math.factorial(M%1000000007)*math.factorial(N%1000000007)
if(N==M):
    i=i*2
ans=i%1000000007
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
S = [[]] * N
for i in range(M):
	p, s = input().split()
	S[int(p)-1] = S[int(p)-1] + [s]

r,w = 0,0
for i in S:
	if 'AC' in i:
		r += 1
		w += i.index('AC')

print(r,w)

### FIXED CODE ###

N, M = map(int, input().split())
S = [0] * N
r,w = 0,0
for i in range(M):
	p, s = input().split()
	if S[int(p)-1] >= 0:
		if s == 'AC':
			r+=1
			w+=S[int(p)-1]
			S[int(p)-1] = -1
		else:
			S[int(p)-1] = S[int(p)-1] + 1
print(r,w)
### BUGGY CODE ###

N = int(input())
A = [int(_) for _ in input().split()]

A = list(set(A))
A.sort(reverse=True)

while True:
    if len(A) == 1:
        break
    A[0] = A[0] % A[1]
    if A[0] == 0:
        A.pop(0)
    A = list(set(A))
    A.sort(reverse=True)

print(A[0])


### FIXED CODE ###

import fractions
from functools import reduce

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

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

N = int(input())
A = [int(_) for _ in input().split()]

print(gcd_list(A))
### BUGGY CODE ###

import numpy as np
n = int(input())
A=list(map(int, input().split()))


bit= np.array([[0]*60 for i in range(n)])
for i in range(n):
    a=A[i]
    j=1
    if a!=0:    
        while a//2>0:
            if a%2==1:
                bit[i][60-j]=1
                j+=1
                a=a//2
            else:
                j+=1
                a=a//2
        bit[i][60-j]=1
           
l=np.sum(bit,axis=0)           
xor=([n]*60-l)*l
    
#for j in range(60):
    #for i in range(n):
        #l+=bit[i][j]
    #xor[j]=l*(n-l)
    
L=10**9+7
ans=xor[0]
for j in range(60-1):
    ans=((2*ans)+xor[j+1])%L
print(ans)    

### FIXED CODE ###

def main():
    """"ここに今までのコード"""
 
n = int(input())
A = [int(a) for a in input().split()]
mod=10**9+7
 
ans=0
for i in range(60):
    l=sum([a%2 for a in A])
    ans=(ans+l*(n-l)*(2**i))%mod
    A=[a//2 for a in A]
    
 
#ans=xor[0]
#for j in range(60-1):
#    ans=((2*ans)+xor[j+1])%mod
print(int(ans)) 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  matchfunc=lambda x: (x==b[b[x]-1]-1 and b[x]!=x+1)
  match=list(filter(matchfunc,range(N)))
  #print(match)
  for i in range(len(match)):
    c[match[i]]+=1
    b[match[i]]=a[match[i]][c[match[i]]]
  #for i in range(N):
    #if b[i]==i+1:
      #cnt+=0
    #elif i==b[b[i]-1]-1:
      #c[i]+=1
  #print('c='+str(c))
  #for i in range(N):
    #b[i]=a[i][c[i]]
  #print('b='+str(b))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()

print('-1')

### FIXED CODE ###

import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
#print(matches)
q = deque(range(n))
#print(q)
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    b = matches[a].pop()
    #print(a, b)
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.append(a)
        if matches[b]:
            q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
k = int(input())

sum_of_gcd = 0
for a in range(k):
    for b in range(k):
        for c in range(k):
            sum_of_gcd  += gcd((a + 1), (b + 1), (c +1))
print(sum_of_gcd)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())

sum_of_gcd = 0
dict_of_gcd = {}
for a in range(k):
    for b in range(k):
        for c in range(k):
            if a == b == c:
                sum_of_gcd  += a + 1
            else:
                sum_of_gcd  += gcd((a + 1), (b + 1), (c +1))
print(sum_of_gcd)
### BUGGY CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]#足場iまでの最小コスト
for i in range(1,N):
    m=dp[i-1]+abs(H[i]-H[i-1])
    for j in range(2,K+1):
        if i-j<0: break
        m=min(m,dp[i-j]+abs(H[i]-H[i-j]))
    dp.append(m)
print(dp[-1])

### FIXED CODE ###

N,K=map(int,input().split())
H=list(map(int,input().split()))
dp=[0]#足場iまでの最小コスト
for i in range(1,N):
    l=max(0,i-K)
    m=min([d+abs(H[i]-h) for d,h in zip(dp[l:i],H[l:i])])
    #m=min(map(lambda d,h:d+abs(H[i]-h),dp[l:i],H[l:i]))
    dp.append(m)
print(dp[-1])
### BUGGY CODE ###

N = int(input())

hantei = 0

while N != 0 or N < 1:
    hantei += N % 10
    N = N // 10

if hantei % 9 == 0:
    ans = "Yes"
else:
    ans = "No"

print(ans)


### FIXED CODE ###

N = input()

hantei = 0

for i in range(len(N)):
    hantei += int(N[i])

if hantei % 9 == 0:
    ans = "Yes"
else:
    ans = "No"

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

S = input()
len_S = len(S)
ans = 0

for i in range(0, len_S-4):
    for j in range(i+4, len_S+1):
        if int(S[i:j]) % 2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

n = input()

MOD = 2019
ans = 0
dp = [0]*MOD
dp[0] = 1
temp = 0

for i in range(len(n)):
    temp = (temp+int(n[-i-1])*int(pow(10, i, MOD))) % MOD
    dp[temp] += 1

for item in dp:
    if item > 1:
        ans += item*(item-1)//2

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

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)


### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
### BUGGY CODE ###

s = input()
cnt=0
while True:
    for i in range(len(s)//2):
        try: 
            if '10' in s:
                cnt+=2 * s.count('10')
                s=s.replace('10', '') 
        except:
            pass
        try: 
            if '01' in s:
                cnt+=2 * s.count('01')
                s=s.replace('01', '') 
        except:
            pass
    break
print(cnt)

### FIXED CODE ###

#120 C
S =input()
print(min(S.count('0'),S.count('1'))*2)
### BUGGY CODE ###

def union(group, new_mem):
    if (group[new_mem[0]-1] + group[new_mem[1]-1]) != 0 and (group[new_mem[0]-1] * group[new_mem[1]-1]) == 0:
        choice = max(group[new_mem[0]-1], group[new_mem[1]-1])
       
        for i in range(len(new_mem)):
            group[new_mem[i]-1] = choice
            
    elif group[new_mem[0]-1] + group[new_mem[1]-1] == 0: 
        for i in range(len(new_mem)):
            group[new_mem[i]-1] = min(new_mem[0], new_mem[1])
        
    elif (group[new_mem[0]-1] + group[new_mem[1]-1]) != 0 and (group[new_mem[0]-1] * group[new_mem[1]-1]) != 0:
        old = max(group[new_mem[0]-1], group[new_mem[1]-1])
        new = min(group[new_mem[0]-1], group[new_mem[1]-1])
        for i in range(len(group)):
            if group[i] == old:
                group[i] = new
                 
    return group

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

non_route = []
total = int(n*(n-1)/2)
non_route.append(total)

group = [0 for i in range(n)] 
for i in range(m-1,0,-1):
    group_for_calc = union(group, bridge[i]) 
    connected_group = list(set(group_for_calc)-set({0})) 
    count = 0
    for i in range(len(connected_group)):
        num = group_for_calc.count(connected_group[i])
        count += int(num*(num-1)/2)
    ans = total - count
    non_route.append(ans)

final = sorted(non_route)
for i in range(len(final)):
    print(final[i])

### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]
 
    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
    
n,m = map(int, input().split())
bridge = []
for i in range(m):
    a, b= map(int, input().split())
    bridge.append((a,b))

non_route = []
total = int(n*(n-1)/2)
non_route.append(total)

uft = UnionFind(n)

tmp = total

for i in range(m-1,0,-1):
    a = bridge[i][0] -1
    b = bridge[i][1] -1

    if uft.issame(a, b):
        non_route.append(non_route[-1])
        continue
    ra = uft.size(a)
    rb = uft.size(b)
    non_route.append(non_route[-1] - ra * rb)
    uft.merge(a, b)

final = sorted(non_route)
for i in range(len(final)):
    print(final[i])
### BUGGY CODE ###

N,K=map(int,input().split(' '))
x = list(map(int,input().split(' ')))
ans = 2*(10**8)
if N==K:
    if x[-1]<0:
        print(-x[0])
    elif x[0]>0:
        print(x[-1])
    else:
        print(min(x[-1]-2*x[0],2*x[-1]-x[0]))
    exit()
for i in range(N-K):
    tmp = x[i:i+K]
    if tmp[-1]<0:
        ans = min(ans,-tmp[0])
    elif tmp[0]>=0:
        ans = min(ans,tmp[-1])
    else:
        ans = min(ans,tmp[-1]-2*tmp[0],2*tmp[-1]-tmp[0])
print(ans)

### FIXED CODE ###

N,K=map(int,input().split(' '))
x = list(map(int,input().split(' ')))
ans = 2*(10**8)
if N==K:
    if x[-1]<0:
        print(-x[0])
    elif x[0]>0:
        print(x[-1])
    else:
        print(min(x[-1]-2*x[0],2*x[-1]-x[0]))
    exit()
for i in range(N-K+1):
    l,r=x[i],x[i+K-1]
    if l>0:
        ans = min(ans,r)
    elif r<0:
        ans = min(ans,-l)
    else:
        ans = min(ans,r-2*l,2*r-l)
print(ans)
### BUGGY CODE ###

S = list(str(input()))
S.reverse()
mod = 2019
rem = [0]*mod
num = 0
rem[num] += 1
d = 1
ans = 0
for s in S:
  num += int(s) * d
  num %= mod
  d *= 10
  rem[num] += 1
for r in rem:
  ans += r*(r-1)//2
print(ans)

### FIXED CODE ###

S = list(str(input()))
S.reverse()
mod = 2019
rem = [0]*mod
num = 0
rem[num] += 1
d = 1
ans = 0
for s in S:
  num += int(s) * d
  num %= mod
  d *= 10
  d %= mod
  rem[num] += 1
for r in rem:
  ans += r*(r-1)//2
print(ans)
### BUGGY CODE ###

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

VACANT = 'Vacant'
FEMALE = 'Female'
MALE = 'Male'


def check(n):
    print(n, flush=True)
    s = sys.stdin.buffer.readline().decode().rstrip()
    if s == VACANT:
        exit()
    return s


l = 0
h = N - 1
ls = check(l)
hs = check(h)
while abs(l - h) > 1:
    mid = (l + h) // 2
    ms = check(mid)
    if ((mid - l) % 2 == 0) == (ls == ms):
        l = mid
    else:
        h = mid


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

VACANT = 'Vacant'
FEMALE = 'Female'
MALE = 'Male'


def check(n):
    print(n, flush=True)
    s = sys.stdin.buffer.readline().decode().rstrip()
    if s == VACANT:
        exit()
    return s


l = 0
h = N
ls = check(l)
while abs(l - h) > 1:
    mid = (l + h) // 2
    ms = check(mid)
    if ((mid - l) % 2 == 0) == (ls == ms):
        l = mid
        ls = ms
    else:
        h = mid
check(h)
check(l)
### BUGGY CODE ###

def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    if a.count(10 ** 6) == n:
        print(0)
        exit()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


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

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline


def DFS(num,point):
    D[num]=point+Q[num]
    color[num]="gray"
    for i in M[num]:
        if color[i]=="white":
            DFS(i,D[num])
    color[num]="black"


n,q=map(int,input().split())

M=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    M[a] +=[b]
    M[b] +=[a]

Q=[0]*(n+1)
for i in range(q):
    p,x=map(int,input().split())
    Q[p] +=x

color=["white" for _ in range(n+1)]
D=[0]*(n+1)

DFS(1,0)
print(*D[1:])

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

print(*ans)