Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int, input().split())
S = []
for i in range(H):
  S.append(input())

tate_value = [[0]*W for i in range(H)]
yoko_value = [[0]*W for i in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      yoko_value[i][j] = 0
    else:
      if j==0:
        left = 0
        right = W-1
        for k in range(0,W):
          if S[i][k] == '#':
            right = k-1
            break
        yoko_value[i][j] = right+1
      else:
        if S[i][j-1] == '.':
          yoko_value[i][j] = yoko_value[i][j-1]
        else:
          right = W-1
          for k in range(j,W):
            if S[i][k] == '#':
              right = k-1
              break
          yoko_value[i][j] = right-j+1

for j in range(W):
  for i in range(H):
    if S[i][j] == '#':
      tate_value[i][j] = 0
    else:
      if i==0:
        up = 0
        down = H-1
        for k in range(0,H):
          if S[k][j] == '#':
            down = k-1
            break
        tate_value[i][j] = down+1
      else:
        if S[i-1][j] == '.':
          tate_value[i][j] = tate_value[i-1][j]
        else:
          down = H-1
          for k in range(i,H):
            if S[k][j] == '#':
              down = k-1
              break
          tate_value[i][j] = down-i+1
max = 0
for i in range(H):
  for j in range(W):
    temp = yoko_value[i][j] + tate_value[i][j]-1
    if temp>max:
      max = temp
      
print(max)

Fixed submission:
H,W=map(int, input().split())
S = []
for i in range(H):
  S.append(input())

tate_value = [[0]*W for i in range(H)]
yoko_value = [[0]*W for i in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      yoko_value[i][j] = 0
    else:
      if j==0:
        left = 0
        right = W-1
        for k in range(0,W):
          if S[i][k] == '#':
            right = k-1
            break
        yoko_value[i][j] = right+1
      else:
        if S[i][j-1] == '.':
          yoko_value[i][j] = yoko_value[i][j-1]
        else:
          right = W-1
          for k in range(j,W):
            if S[i][k] == '#':
              right = k-1
              break
          yoko_value[i][j] = right-j+1

for j in range(W):
  for i in range(H):
    if S[i][j] == '#':
      tate_value[i][j] = 0
    else:
      if i==0:
        up = 0
        down = H-1
        for k in range(0,H):
          if S[k][j] == '#':
            down = k-1
            break
        tate_value[i][j] = down+1
      else:
        if S[i-1][j] == '.':
          tate_value[i][j] = tate_value[i-1][j]
        else:
          down = H-1
          for k in range(i,H):
            if S[k][j] == '#':
              down = k-1
              break
          tate_value[i][j] = down-i+1
          
max = 0
for i in range(H):
  for j in range(W):
    temp = yoko_value[i][j] + tate_value[i][j]-1
    if temp>max:
      max = temp
      
print(max)
Buggy python submission (verdict: Runtime Error):
import numpy as np

N,M=map(int, input().split())
A=list(map(int, input().split()))
B=[0]*M
C=[0]*M
for i in range(M):
  B[i],C[i] = map(int, input().split())

A = np.sort(A)
C_sort_index = np.argsort(C)[::-1]
C = np.sort(C)[::-1]

for i in range(N):
  if len(C)==0:
    break
  Cmax = C[0]
  if A[i] < Cmax:
    A[i] = Cmax
    index = C_sort_index[0]
    B[index] -= 1
    if B[index] == 0:
      B = np.delete(B,index)
      C = np.delete(C,0)
      C_sort_index = np.delete(C_sort_index,0)
print(sum(A))

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A = III()
B,C = Line(M)

a = []
for i in range(N):
  a.append([1,A[i]])
for i in range(M):
  a.append([B[i],C[i]])

a.sort(key=lambda x:x[1],reverse=True)
#a.sort(key=lambda x:-x[1])
counter = 0
ans = 0

for i in range(N+M):
  if counter + a[i][0] >= N:
    ans += a[i][1]*(N-counter)
    break
  else:
    counter += a[i][0]
    ans += a[i][1]*a[i][0]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int, input().split())
A=list(map(int, input().split()))
B=[0]*M
C=[0]*M
for i in range(M):
  B[i],C[i] = map(int, input().split())

A_sort = A.sort()

for i in range(N):
  if len(C)==0:
    break
  Cmax = max(C)
  if A[i]<Cmax:
    A[i] = Cmax
    index = max(enumerate(C), key=lambda x: x[1])[0]
    B[index] -= 1
    if B[index] == 0:
      B.pop(index)
      C.pop(index)
print(sum(A))

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A = III()
B,C = Line(M)

a = []
for i in range(N):
  a.append([1,A[i]])
for i in range(M):
  a.append([B[i],C[i]])

a.sort(key=lambda x:x[1],reverse=True)
#a.sort(key=lambda x:-x[1])
counter = 0
ans = 0

for i in range(N+M):
  if counter + a[i][0] >= N:
    ans += a[i][1]*(N-counter)
    break
  else:
    counter += a[i][0]
    ans += a[i][1]*a[i][0]

print(ans)
Buggy python submission (verdict: Runtime Error):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,K = II()
S = str(input())

num = 0
for i in range(N):
    if S[i]=='0' and S[i+1]=='1':
        num += 1
        place = i+1
    if num==K:
        break

if num<K:
    print(N)
    exit()

for i in range(place+1,N):
    if i==N-1 and S[i]=='1':
        print(N)
        exit()
    if S[i]=='0':
        break

place = i-1

ans = place+1

for i in range(1,N):
    if S[i-1]=='0' and S[i]=='1':
        val = N-1
        count = 0
        for j in range(place+2,N):
            val = j
            if S[j]=='1':
                count += 1
            if count==2:
                break
        if val-i+1>ans:
            ans = val-i+1
        place = val

print(ans)

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,K = II()
S = str(input())

num = 0
for i in range(N):
    if i==N-1:
        print(N)
        exit()
    if S[i]=='0' and S[i+1]=='1':
        num += 1
        place = i+1
    if num==K:
        break

if num<K:
    print(N)
    exit()

for i in range(place+1,N):
    if i==N-1 and S[i]=='1':
        print(N)
        exit()
    if S[i]=='0':
        break

place = i-1

ans = place+1

for i in range(1,N):
    if S[i-1]=='0' and S[i]=='1':
        val = N-1
        for j in range(place+2,N):
            val = j
            if j==N-1:
                break
            if S[j]=='1' and S[j+1]=='0':
                break
        if val-i+1>ans:
            ans = val-i+1
        place = val

print(ans)
Buggy python submission (verdict: Runtime Error):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

X,Y,Z,K = II()
A = III()
B = III()
C = III()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a = []
if X*Y*Z <= 10**6:
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)
    for i in range(K):
        print(a[i])
else:
    for i in range(X):
        for j in range(min(Y,math.ceil(5000/i))):
            for k in range(min(Z,math.ceil(5000/i/j))):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)   
    for i in range(K):
        print(a[i])

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

X,Y,Z,K = II()
A = III()
B = III()
C = III()

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a = []
if X*Y*Z <= 10**6:
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)
    for i in range(K):
        print(a[i])
else:
    for i in range(X):
        if i==0: jmax = Y
        else: jmax = min(Y,math.ceil(5000/i))
        for j in range(jmax):
            if i*j==0: kmax = Z
            else: kmax = min(Z,math.ceil(5000/i/j))
            for k in range(kmax):
                a.append(A[i]+B[j]+C[k])
    a.sort(reverse=True)   
    for i in range(K):
        print(a[i])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,M = II()
A,B = Line(N-1+M,2)

parent = [[] for _ in range(N)]
pt = [[] for _ in range(N)]

for i in range(N-1+M):
    parent[B[i]-1].append(A[i]-1)
    pt[A[i]-1].append(B[i]-1)

for i in range(N):
    if parent[i]==[]:
        root = i

ans = ['0']*N
q = [root]
while q:
    q_new = []
    for q1 in q:
        for v in pt[q1]:
            ans[v] = q1+1
            q_new.append(v)
    q = q_new

for i in range(N):
    print(ans[i])

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,M = II()
A,B = Line(N-1+M,2)

parent = [[] for _ in range(N)]
parent_num = [0]*N
pt = [[] for _ in range(N)]

for i in range(N-1+M):
    parent[B[i]-1].append(A[i]-1)
    parent_num[B[i]-1] += 1
    pt[A[i]-1].append(B[i]-1)

for i in range(N):
    if parent[i]==[]:
        root = i

ans = ['0']*N
q = [root]
while q:
    q_new = []
    for q1 in q:
        for v in pt[q1]:
            if parent_num[v]==1:
                ans[v] = q1+1
                q_new.append(v)
            parent_num[v] -= 1
    q = q_new

for i in range(N):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N = I()
A = III()

A.sort()
used = [False]*N
ans = 0

for i in range(N)[::-1]:
    s = math.floor(math.log2(2*A[i]))
    p = bisect_left(A, 2**s-A[i])
    if p<=N-1 and A[p]==2**s-A[i] and p!=i and used[p]==False and used[i]==False:
        ans += 1
        used[p],used[i] = True, True

print(ans)

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N = I()
A = III()
A.sort()

val = []
num = []
before = 0
for a in A:
    if a != before:
        val.append(a)
        num.append(1)
        before = a
    else:
        num[-1] += 1

ans = 0

for i in range(N)[::-1]:
    s = math.floor(math.log(2*A[i],2))
    p = bisect_left(val,2**s-A[i])
    if A[i]==2**s-A[i]:
        if num[p]>=2:
            ans += 1
            num[p] -= 2
    else:
        j = bisect_left(val,A[i])
        if p<=len(val)-1:
            if val[p]==2**s-A[i] and num[j] and num[p]:
                ans += 1
                num[j] -= 1
                num[p] -= 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()

ans = 1
a = M//N 
for i in range(2,a+1):
  if M%i==0 and i*N<=M:
    ans = i
print(ans)

Fixed submission:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.sort()
  return divisors

ans = 1
kouho = make_divisors(M)
for i in kouho:
  if M%i==0 and i*N<=M:
    ans = i
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

r = math.floor(math.log2(L+1))
M = 0
edge = []
for i in range(r):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(r)[::-1]:
    if L-2**i >= 2**r:
        edge.append([i,r,L-2**i])
        M += 1
        L -= 2**i

print(r+1,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

N = math.floor(math.log2(L))+1
M = 0
edge = []
for i in range(N-1):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(N-1)[::-1]:
    if L-2**i >= 2**(N-1):
        edge.append([i,N-1,L-2**i])
        M += 1
        L -= 2**i

print(N,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])

Buggy python submission (verdict: Runtime Error):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

r = math.floor(math.log2(L+1))
M = 0
edge = []
for i in range(r):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(r)[::-1]:
    if L-2**i >= 2**r:
        edge.append([i,r,L-2**i])
        M += 1
        L -= 2**i

print(r+1,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

L = I()

N = math.floor(math.log2(L))+1
M = 0
edge = []
for i in range(N-1):
    edge.append([i,i+1,0])
    edge.append([i,i+1,2**i])
    M += 2
for i in range(N-1)[::-1]:
    if L-2**i >= 2**(N-1):
        edge.append([i,N-1,L-2**i])
        M += 1
        L -= 2**i

print(N,M)
for e in edge:
    print(e[0]+1, e[1]+1, e[2])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

S = str(input())
N = len(S)

h_all = 0
for i in range(N):
    if S[i]=='?':
        h_all += 1

a = 0
b = 0
h = 0
numAB = 0
numAH = 0
numHB = 0
numHH = 0
dp = [0]*N

for i in range(N):
    if S[i]=='A':
        if i>=1:
            dp[i] = dp[i-1]
        a += 1
    elif S[i]=='B':
        if i>=1:
            dp[i] = dp[i-1]
        numAB += a
        numHB += h
        b += 1
    elif S[i]=='?':
        if i>=1:
            if h_all>=1:
                dp[i] = (dp[i-1]+numAB*3**(h_all-1)) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numAH*3**(h_all-2)) %mod
                dp[i] = (dp[i]+numHB*3**(h_all-2)) %mod
            if h_all>=3:
                dp[i] = (dp[i]+numHH*3**(h_all-3))%mod
        numAH += a
        numHH += h
        h += 1
    else:
        if i>=1:
            dp[i] = (dp[i-1]+numAB*3**h_all) %mod
            if h_all>=1:
                dp[i] = (dp[i]+numAH*3**(h_all-1)) %mod
                dp[i] = (dp[i]+numHB*3**(h_all-1)) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numHH*3**(h_all-2))%mod

print(dp[N-1])

Fixed submission:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

S = str(input())
N = len(S)

h_all = 0
for i in range(N):
    if S[i]=='?':
        h_all += 1

a = 0
b = 0
h = 0
numAB = 0
numAH = 0
numHB = 0
numHH = 0
dp = [0]*N

beki3 = pow(3,h_all-3,mod) if h_all>=4 else 1
beki2 = beki3*3 % mod if h_all>=3 else 1
beki1 = beki2*3 %mod if h_all>=2 else 1
beki0 = beki1*3 %mod if h_all>=1 else 1

for i in range(N):
    if S[i]=='A':
        if i>=1:
            dp[i] = dp[i-1]
        a += 1
    elif S[i]=='B':
        if i>=1:
            dp[i] = dp[i-1]
        numAB += a
        numHB += h
        b += 1
    elif S[i]=='?':
        if i>=1:
            if h_all>=1:
                dp[i] = (dp[i-1]+numAB*beki1) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numAH*beki2) %mod
                dp[i] = (dp[i]+numHB*beki2) %mod
            if h_all>=3:
                dp[i] = (dp[i]+numHH*beki3)%mod
        numAH += a
        numHH += h
        h += 1
    else:
        if i>=1:
            dp[i] = (dp[i-1]+numAB*beki0) %mod
            if h_all>=1:
                dp[i] = (dp[i]+numAH*beki1) %mod
                dp[i] = (dp[i]+numHB*beki1) %mod
            if h_all>=2:
                dp[i] = (dp[i]+numHH*beki2)%mod

print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def check(i,s,s0):
    if i%2 == 0:
        if s == s0:
            return True
        else:
            return False
    else:
        if s != s0:
            return True
        else:
            return False

N = I()
print(0,flush=True)
s0 = str(input())
if s0 == 'Vacant':
    exit()

ok = N-1
ng = 0
while True:
    mid = (ok+ng)//2
    print(mid,flush=True)
    s = str(input())
    if s == 'Vacant':
        exit()
    flag = check(mid,s,s0)
    if flag:
        ng = mid
    else:
        ok = mid

Fixed submission:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def check(i,s,s0):
    if i%2 == 0:
        if s == s0:
            return True
        else:
            return False
    else:
        if s != s0:
            return True
        else:
            return False

N = I()
print(0)
sys.stdout.flush()
s0 = str(input())
if s0 == 'Vacant':
    exit()

print(N-1)
sys.stdout.flush()
s1 = str(input())
if s1 == 'Vacant':
    exit()

ok = N-1
ng = 0
while True:
    mid = (ok+ng)//2
    print(mid)
    sys.stdout.flush()
    s = str(input())
    if s == 'Vacant':
        exit()
    flag = check(mid,s,s0)
    if flag:
        ng = mid
    else:
        ok = mid