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


import queue as que



def main():
    h, w = map(int, input().split())

    ahw = [input() for _ in range(h)]

    board = [[0]*w for _ in range(h)]

    q = que.Queue(h*w)
    q.put((-1,-1))
#    q = [(-1,-1)]
    
    for hi in range(h):
        for wi in range(w):
            if ahw[hi][wi] == '#':

                board[hi][wi] = 1
                
                q.put( (hi,wi) )

#    print(q)
#    print(board)
    if q.full():
        print(0)
        return 
    

    def exec(h_,w_):
        if board[h_][w_] == 0:
            q.put((h_,w_))
            board[h_][w_] = 1
   
           
    ans = 0
    while not q.empty():
        t = q.get()
#        print(t)
        th = t[0]; tw = t[1]

        if th == tw and tw == -1:
            if q.empty():
                break

            q.put((-1,-1))
            ans += 1
            continue

        if 0<th:
            exec(th-1, tw)
        if th+1 <h:
            exec(th+1, tw)
        if 0<tw:
            exec(th, tw-1)
        if tw +1 <w:
            exec(th, tw+1)

    print(ans-1)

main()

### FIXED CODE ###


# 遅い…？
import queue as que

from collections import deque 

def main():
    h, w = map(int, input().split())

    ahw = [input() for _ in range(h)]

    board = [[0]*w for _ in range(h)]

    q = deque()
    q.append((-1,-1))
#    q = [(-1,-1)]
    
    for hi in range(h):
        for wi in range(w):
            if ahw[hi][wi] == '#':

                board[hi][wi] = 1
                
                q.append((hi,wi) )

#    print(q)
#    print(board)
    if len(q) == h*w+1:
        print(0)
        return 
    

    def exec(h_,w_):
        if board[h_][w_] == 0:
            q.append((h_,w_))
            board[h_][w_] = 1
   
           
    ans = 0
    while q:
        t = q.popleft()
#        print(t)
        th = t[0]; tw = t[1]

        if th == tw and tw == -1:
            if not q:
                break

            q.append((-1,-1))
            ans += 1
            continue

        if 0<th:
            exec(th-1, tw)
        if th+1 <h:
            exec(th+1, tw)
        if 0<tw:
            exec(th, tw-1)
        if tw +1 <w:
            exec(th, tw+1)

    print(ans-1)

main()
### BUGGY CODE ###

s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = ABC*3 + AB
        AB *= 3#AB + C and AB + B and AB + C
        AB += A[1] # AB + B
        A[1] = A[1]*3 + A[0]
        A[0] *= 3

print(ABC%D) 


### FIXED CODE ###

s = input()

A = [1,0]
AB = 0
ABC = 0
D = 10**9 + 7
for c in s:
    if c == 'A':
        A[1] += A[0]
    elif c == 'B':
        AB += A[1]
    elif c == 'C':
        ABC += AB
    elif c == '?':
        ABC = (((ABC%D) *3)%D + (AB)%D)%D
        AB = (((AB%D) *3)%D + (A[1])%D)%D
        A[1] = (((A[1]%D)*3)%D + A[0]%D)%D
        A[0] = ((A[0]%D) * 3)%D

print(ABC%D)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))[::-1]

cnt = 0
for i in range(n - 1):
	k = 1
	for j in range(i + 1,n):
		if k == A[i] + A[j]:
			cnt += 1
		k += 1

print(cnt)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))[::-1]

import collections

L = [i + A[i] for i in range(n)]
R = [j - A[j] for j in range(n)]

cL = collections.Counter(L)
cR = collections.Counter(R)

cnt = 0

MAX = 200000
for x in range(MAX):
	cnt += cL[x] * cR[x]

print(cnt)
### BUGGY CODE ###

import itertools
import numpy as np
from sys import stdin

H, W, K = map(int, stdin.readline().split())
A = np.int32([[int(x) for x in stdin.readline().strip()] for _ in range(H)])

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    if len(pivots) > ans:
        continue

    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue

    n_block = blocks.shape[0]
    n_cut = n_block - 1
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_cut += 1
            sums = adds
            if n_cut >= ans:
                break

    ans = min(ans, n_cut)

print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
array = list(map(int,input().split()))
all_gcd = [0]*N

def calc_gcd(idx,array):
  gcd_arr = []
  for i in range(idx):
    if gcd_arr == []:
      gcd_arr.append(array[i])
    else:
      gcd_arr.append(gcd(gcd_arr[-1],array[i]))
  for j in range(idx+1,N,1):
    if gcd_arr == []:
      gcd_arr.append(array[j])
    else:
      gcd_arr.append(gcd(gcd_arr[-1],array[j]))
  return(gcd_arr[-1])

for k in range(N):
  all_gcd[k] = calc_gcd(k,array)

print(max(all_gcd))

### FIXED CODE ###

from fractions import gcd
N = int(input())
array = list(map(int,input().split()))
all_gcd = [0]*N
#calc from start to end
gcd_L = [array[0]]
for i in range(N-1):
  gcd_L.append(gcd(gcd_L[-1],array[i+1]))
  
#calc from end to start
gcd_R = [array[-1]]
for j in range(N-1,0,-1):
  gcd_R.append(gcd(gcd_R[-1],array[j-1]))
  
gcd_arr = []
  
for idx in range(N):
  if idx==0:
    gcd_arr.append(gcd_R[-2])
  elif idx==N-1:
    gcd_arr.append(gcd_L[-2])
  else:
    gcd_arr.append(gcd(gcd_L[idx-1],gcd_R[N-1-idx-1]))
print(max(gcd_arr))
### BUGGY CODE ###

import sys

s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())
query = [sys.stdin.readline().rstrip().split() for i in range(q)]
top = 1
s = list(s)
for i in range(q):
    que = query[i]
    if que[0] == '1':
        top *= -1
    else:
        if que[1] == '1':
            if top > 0:
                s.insert(0, que[2])
                # s = ''.join([que[2], s])
                # s = que[2] + s
            else:
                s.append(que[2])
                # s = ''.join([s, que[2]])
                # s = s + que[2]
        else:
            if top > 0:
                s.append(que[2])
                # s = ''.join([s, que[2]])
                # s = s + que[2]
            else:
                s.insert(0, que[2])
                # s = ''.join([que[2], s])
                # s = que[2] + s

s = ''.join(s)
if top < 0:
    s = s[::-1]
print(s)

### FIXED CODE ###

import sys

s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())
query = [sys.stdin.readline().rstrip().split() for i in range(q)]
top = 1
s = list(s)
s_front = []
s_back = []
for i in range(q):
    que = query[i]
    if que[0] == '1':
        top *= -1
    else:
        if que[1] == '1':
            if top > 0:
                s_front.append(que[2])
                # s = ''.join([que[2], s])
                # s = que[2] + s
            else:
                s_back.append(que[2])
                # s = ''.join([s, que[2]])
                # s = s + que[2]
        else:
            if top > 0:
                s_back.append(que[2])
                # s = ''.join([s, que[2]])
                # s = s + que[2]
            else:
                s_front.append(que[2])
                # s = ''.join([que[2], s])
                # s = que[2] + s
s_front.reverse()
s_front.extend(s)
s_front.extend(s_back)
s = s_front
s = ''.join(s)
if top < 0:
    s = s[::-1]
print(s)
### BUGGY CODE ###

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

## Aは昇順Fは降順に並び替える
A.sort()
F.sort(reverse=True)

## 成績(A × F)の目標をxにしたときに何回修行が必要かを求める関数
def target(x):
    train_count = 0
    for i in range(N):
        a = A[i]
        targ_a = x // F[i] # 目標を達成した時の消費コストA
        if targ_a < a:
            train_count += a - targ_a
    return train_count <= K

## 二分探索(リストを半分ずつ削って達成可能な目標を探す)
left = -1                            # 一番左
right = A[-1] * F[0]                 # 一番右(Aの最大値 × Fの最大値)
while right > left+1:                # 一番右が一番左より大きい間（一致したら終了）
    middle = (left + right) // 2     # 真ん中
    if target(middle):               # 目標を真ん中にして達成可能なら
        right = middle               # 一番右を真ん中にする（残りの右側は無駄に時間かかってるから切り捨てる）
    else:                            # 達成できないなら(K回を超えてしまうとき）
        left = middle                # 一番左を真ん中にする（残りの左側は達成不可だから切り捨てる）
print(right)

### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)
### BUGGY CODE ###

from fractions import Fraction

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


def cmb(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    ans = 1
    if r > n-r:
        r = n-r
    for i in range(r):
        ans = (ans * Fraction(n-i, r-i)) % (10**9+7)
    return ans.numerator


for i in range(1, k+1):
    a = cmb(k-1, i-1)
    b = cmb(n-k+1, i)
    ab = a*b % (10**9+7)
    print(ab)


### FIXED CODE ###

# k-1Ci-1 * n-k+1Ci
mod = 10**9+7
n, k = map(int, input().split())
ans = n-k+1
print(ans)
for i in range(1, k):
    ans = ans*(k-i)*(n-k-i+1)//(i*(i+1))
    print(ans % mod)
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()

    print(0)
    s0 = input()
    if s0 == 'Vacant':
        exit()

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

        if ( mid % 2 == 0 and s == s0 ) or ( mid % 2 == 1 and s != s0 ):
            ng = mid
        else:
            ok = mid

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    N = INT()

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

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

        if ( mid % 2 == 0 and s == s0 ) or ( mid % 2 == 1 and s != s0 ):
            ng = mid
        else:
            ok = mid

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

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

g = {}
steps = 3
for v in range(1,N*steps+1):
    g[v] = []

for _ in range(M):
    u,v = map(int, input().split())

    for idx in range(steps):
        g[u + N*idx].append(v + N*((idx+1) % steps))

S,T = map(int, input().split())

visiting = [(S,0)]
visited = {}
while visiting:
    v,d = visiting.pop(0)
    if v in visited:
        continue
    visited[v] = d
    if v == T:
        break

    for v2 in g.get(v,()):
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,d+1))
if T in visited:
    print(visited[T] // steps)
else:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
E = {}
for v in range(1,N*3+1):
    E[v] = []
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)
S, T = map(int, input().split())
dist = [-1 for _ in range(3*N)]
dist[S-1] = 0

q = []
q.append(S)
while q:
    n = q.pop(0)
    if n == T:
        break
    for t in E[n]:
        if dist[t-1] < 0:
            dist[t-1] = dist[n-1] + 1
            q.append(t)
print(-1 if dist[T-1] < 0 else dist[T-1] // 3)
### BUGGY CODE ###

from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

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

def adj(s, e):
    queue = deque([])
    colors = [Color.WHITE for i in range(n)]

    queue.append(s)
    colors[s] = Color.GRAY

    while len(queue) > 0:
        u = queue.popleft()
        for v in adj_list[u]:
            if colors[v] == Color.WHITE:
                colors[v] = Color.GRAY
                queue.append(v)
                if v == e: return True
        colors[u] = Color.BLACK
    return False

q = int(input())
for i in range(q):
    s, e = list(map(int, input().split(' ')))
    if adj(s, e):
        print('yes')
    else:
        print('no')


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(100000)

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

# 深さ優先
# 全ての点をたどって連結しているもの同士を同じ色に設定する
colors = []

def adj_dfs(r, c):
    global colors
    stack = deque([])
    stack.append(r)
    colors[r] = c
    while len(stack) != 0:
        u = stack.pop()
        for v in adj_list[u]:
            if colors[v] == None:
                colors[v] = c
                stack.append(v)

def assign_color():
    global colors
    id = 1
    colors = [None for i in range(n)]
    for u in range(n):
        if colors[u] == None:
            id += 1
            adj_dfs(u, id)

assign_color()

q = int(input())
for i in range(q):
    s, e = list(map(int, input().split(' ')))
    if colors[s] == colors[e]:
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ans = []
for _ in range(q):
    l, r = map(int, input().split())
    ans.append(s[l-1:r].count("AC"))

for _ans in ans:
    print(_ans)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
numofac = [0]*len(s)
cnt = 0
for i in range(1, len(s)):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
    numofac[i] = cnt

for _ in range(q):
    l, r = map(int, input().split())
    print(numofac[r-1]-numofac[l-1])
### BUGGY CODE ###

N = int(input())
S = list(map(int,input()))
ans = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      flg = False
      flg2 = False
      for x in range(N):
        if flg2:
          break
        if not flg:
          if S[x] == i:
            flg = True
        else:
          if S[x] == j:
            flg2 = True
            if k in S[x+1:]:
              ans +=1
print(ans)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

K, S = [int(i) for i in input().split()]

counter = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if x + y + z == S:
                counter += 1

print(counter)

### FIXED CODE ###

K, S = [int(i) for i in input().split()]

counter = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z and z <= K:
            counter += 1
print(counter)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
min_a = min(A)
for i in range(M):
    B, C = map(int, input().split())
    if min_a < C:
        C = [C for i in range(B)]
        A.extend(C)
A = sorted(A, reverse=True)
print(sum(A[:N]))


### FIXED CODE ###

from collections import Counter
N, M = map(int, input().split())
A = list(map(int, input().split()))
count_a = Counter(A)
A = [(v, k) for k, v in count_a.items()]
for i in range(M):
    B, C = map(int, input().split())
    A.append((B, C))
A = sorted(A, reverse=True, key=lambda x: x[1])
ans = 0
for k, v in A:
    N = N - k
    if N <= 0:
        ans += k*v+N*v
        break
    ans += k*v
print(ans)
### BUGGY CODE ###

from heapq import *
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
B_C = [list(map(int, input().split())) for i in range(M)]
B_C.sort(key = lambda x : x[1])
for i in range(M):
    cnt = 0
    while cnt < B_C[i][0]:
        x = heappop(A)
        if x < B_C[i][1]:
            heappush(A, B_C[i][1])
        else:
            heappush(A, x)
            break
        cnt += 1
print(sum(A))

### FIXED CODE ###

from heapq import *
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapify(A)
B_C = [list(map(int, input().split())) for i in range(M)]
B_C.sort(key = lambda x : x[1], reverse = True)
for i in range(M):
    cnt = 0
    while cnt < B_C[i][0]:
        x = heappop(A)
        if x < B_C[i][1]:
            heappush(A, B_C[i][1])
        else:
            heappush(A, x)
            break
        cnt += 1
print(sum(A))
### BUGGY CODE ###

n, m = (int(each) for each in input().split())
h = [int(each) for each in input().split()]
pathlist = list()
for i in range(m):
    pathlist.append(set([int(each) for each in input().split()]))

score = 0
for deck in range(1, n+1):
    # それぞれの展望台につながっている展望台の高さのリストを出力
    listhofheights = [h[(path - set([deck])).pop()-1] for path in pathlist if deck in path]
    if len(listhofheights) == 0:
        score += 1
    elif max(listhofheights) < h[deck-1]:
        score += 1
    # print('deck', deck,':' , [h[(path - set([deck])).pop()-1] for path in pathlist if deck in path])
print(score)

### FIXED CODE ###

n, m = (int(each) for each in input().split())
h = [int(each) for each in input().split()]
pathlist = list()
for i in range(m):
    pathlist.append([int(each) for each in input().split()])
score = 0

decklist = set(range(1, n+1))
for path in pathlist:
    # もし道のうち前者が高ければ
    if h[path[0]-1] >= h[path[1]-1]:
        # print('remove:', path[1])
        decklist.discard(path[1])
    # 後者が高ければ
    if h[path[0]-1] <= h[path[1]-1]:
        # print('remove:', path[0])
        decklist.discard(path[0])
print(len(decklist))
### BUGGY CODE ###

n,k=map(int,input().split())
lst=list(map(int,input().split()))
ans=float("inf")
for i in range(n-k+1):
    tmp=lst[i:i+k]
    left=tmp[0]
    right=tmp[-1]
    if left==0 and right==0:
        print(0)
        exit()
    if left<0 and right<=0:
        ans=min(ans,abs(left))
    elif left<0 and right>0:
        if abs(left)>abs(right):
            ans=min(ans,abs(left)+right*2)
        else:
            ans=min(ans,abs(left)*2+right)
    else:
        ans=min(ans,right)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
lst=list(map(int,input().split()))
ans=float("inf")
for i in range(n-k+1):
    left=lst[i]
    right=lst[i+k-1]
    if left==0 and right==0:
        print(0)
        exit()
    if left<0 and right<=0:
        ans=min(ans,abs(left))
    elif left<0 and right>0:
        if abs(left)>abs(right):
            ans=min(ans,abs(left)+right*2)
        else:
            ans=min(ans,abs(left)*2+right)
    else:
        ans=min(ans,right)
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
print(sum([1 if i%x==0 else 0 for i in range(a, b+1)]))

### FIXED CODE ###

a, b, x = map(int, input().split())
print(int(b//x) - int((a-1)//x))
### BUGGY CODE ###

import bisect

[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    tmp = a.pop(-1)
    bisect.insort(a, int(tmp / 2))
print(sum(a))

### FIXED CODE ###

import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))
### BUGGY CODE ###

def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr
N=int(input())
fac=[factor(i+1) for i in range(N)]
A=list(map(int,input().split()))
ball=[0]*N
res=[]
for i in reversed(range(N)):
    y=0
    if ball[i]!=A[i]:
        y=1
        ball[i]=(ball[i]+1)%2
        res.append(i+1)
        for k in fac[i]:
            ball[k-1]=(ball[k-1]+1)%2
print(len(res))
print(*res,sep=' ')

### FIXED CODE ###

def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr
N=int(input())
fac=[factor(i+1) for i in range(N)]
A=list(map(int,input().split()))
ball=[0]*N
res=[]
for i in reversed(range(N)):
    y=0
    if ball[i]!=A[i]:
        y=1
        ball[i]=(ball[i]+1)%2
        res.append(i+1)
        for k in fac[i]:
            ball[k-1]=(ball[k-1]+1)%2
print(len(res))
print(*res,sep=' ')
### BUGGY CODE ###

import math
from functools import reduce

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

K = int(input())
ans = 0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(i,j,k)
            
print(ans)

### FIXED CODE ###

import math
from functools import reduce

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

K = int(input())
ans = 0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += gcd(i,j,k)
            
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = []
ans = 10**10
for i in range(N):
    tmp = int(input())
    h.append(tmp)
h = sorted(h)
for i in range(N-K+1):
    tmp2 = h[i:i+K]
    ans = min((max(tmp2)-min(tmp2)),ans)
print(str(ans))

### FIXED CODE ###

N,K = map(int,input().split())
h = []
ans = 10**10
for i in range(N):
  tmp = int(input())
  h.append(tmp)
h = sorted(h)
for i in range(N-K+1):
  h2 = h[i]
  h3 = h[i+K-1]
  ans = min(h3 - h2,ans)
print(str(ans))