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

N,W=map(int,input().split())
dp=[0]*(W+1)
# dp[w] := 上限の容量wのときの価値の最大値

for i in range(1,N+1):
    w,v=map(int,input().split())
    for j in reversed(range(w,W+1)):
        dp[j]=max(dp[j-w]+v, dp[j])
    
print(dp[-1])

### FIXED CODE ###

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

for i in range(N):
    w, v = map(int, input().split())
    
    dp = [dp_pv[j] if w > j else max(dp_pv[j], dp_pv[j-w]+v) for j in range(W+1)]
    dp_pv = dp
    #print(dp)
    
print(dp[-1])
### BUGGY CODE ###

def bisect_left(L,x):
  lo=0
  hi=N
  while lo<hi:
    mid=(lo+hi)//2
    if L[mid]<x: lo=mid+1
    else: hi=mid
  return lo

N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    """
    lo=0
    hi=N
    x=a+b
    while lo<hi:
      mid=(lo+hi)//2
      if L[mid]<x: lo=mid+1
      else: hi=mid
    ans+=lo-(j+1) 
    """
    ans+=bisect_left(L,a+b)-(j+1)
print(ans)


### FIXED CODE ###

from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0

for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    ans+=bisect_left(L,a+b)-(j+1)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
num = list(map(int, input().split()))
cns = set(num)
f = []
for i in cns:
    f.append(num.count(i))
f.sort(reverse=True)
print(sum(f[K::]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
n,k = map(int, input().split())
num = list(map(int, input().split()))
cns = collections.Counter(num)
f = [cns[i] for i in cns]
f.sort(reverse=True)
print(sum(f[k::]))
### BUGGY CODE ###

def binarySearch(x, S):
    mid = len(S) / 2
    if mid < 2:
        return x in S
    if S[mid] == x:
        return True
    elif S[mid] > x:
        left = S[:mid]
        return binarySearch(x, left)
    else:
        right = S[mid + 1:]
        return binarySearch(x, right)

n = int(raw_input())
S = map(int, raw_input().split())
q = int(raw_input())
T = map(int, raw_input().split())
count = 0
for x in T:
    if binarySearch(x, S):
        count += 1
print count

### FIXED CODE ###

def binarySearch(x, S):
    left = 0
    right = len(S)
    while left < right:
        mid = (left + right) / 2
        if x == S[mid]:
            return mid
        elif x < S[mid]:
            right = mid
        else:
            left = mid + 1
    return -1

n = int(raw_input())
S = map(int, raw_input().split())
q = int(raw_input())
T = map(int, raw_input().split())
count = 0
for x in T:
    if binarySearch(x, S) >= 0:
        count += 1
print count
### BUGGY CODE ###

import collections
S=input()
src=[0]
for s in range(len(S)):
  src.append((int(S[-(s+1)])*(10**s)+src[s])%2019)
ans=0
s=collections.Counter(src)
s[0]-=1
for n in s.values():
  ans+=n*(n-1)//2
print(ans+s[0])

### FIXED CODE ###

S=input()
N=len(S)

a=0
t=1
d=[0]*2019
d[0]=1
for i in range(N):
  a+=int(S[N-1-i])*t
  a%=2019
  t*=10
  t%=2019
  d[a]+=1

ans=0
for n in d:
  ans += n*(n-1)//2
print(ans)
### BUGGY CODE ###

def main():
    import sys
    import time
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0

    for i in range(1,len(s)+1):
        m_ad = (int(s[-i]) * (10 ** (i - 1))) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]
    time.sleep(0.5)

    print(ans1 + ans2)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

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

from collections import deque

def solve():
    H, W = map(int, input().split())

    l = []
    for _ in range(H):
        l.append([0 if s=="." else 1 for s in input()])

    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if gw==sw and gh==sh:
                        continue
                    if l[gh][gw] or l[sh][sw]:
                        continue

                    q = deque([(sh, sw)])
                    dist = [[10**12]*W for _ in range(H)]
                    dist[sh][sw] = 0
                    while q:
                        h, w = q.popleft()
                        for h1, w1 in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
                            if not (0<=h1<H and 0<=w1<W):continue
                            if l[h1][w1]:continue
                            if dist[h1][w1] > dist[h][w] + 1:
                                dist[h1][w1] = dist[h][w] + 1
                                q.append((h1, w1))
                    ans = max(ans, dist[gh][gw])
    print(ans)

solve()

### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

import math

N = int(input())
a = sorted(list(map(int,input().split())))

count = 0
while(a!=[]):
    temp = a[-1]
    a.pop(-1)
    b=2**math.floor(math.log2(temp))
    if a ==[]:
        break
    if 2*b-temp in a:
        count += 1
        a.pop(a.index(2*b-temp))
    
print(count)



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = {}
for i in range(len(a)):
    if a[i] in b:
        b[a[i]] += 1
    else:
        b[a[i]] = 1
twins = []
now = 1
while now <= a[-1]:
    now *= 2
    twins.append(now)
for i in range(len(a) - 1, -1, -1):
    tmpa = 0
    if  b[a[i]] == 0:
        continue
    for j in range(len(twins) - 1, -1, -1):
        if twins[j] <= a[i]:
            break
        tmpa = twins[j] - a[i]
    if tmpa == a[i]:
        if b[tmpa] >= 2:
            b[tmpa] -= 2
    elif tmpa in b and b[tmpa] != 0:
        b[tmpa] -= 1
        b[a[i]] -= 1
countb = 0
for i in b:
    countb += b[i]
print((n - countb) // 2)
### BUGGY CODE ###

n= int(input())
s_list= list(input())
count=0
rr,bb,gg=0,0,0
for i in range(0,n):
    if s_list[i]=="R":
        rr=rr+1
    elif s_list[i]=="G":
        gg=gg+1
    else:
        bb=bb+1
sum=rr*gg*bb

for p in range(0,n-2):
    for q in range(p+1,n-1):
        for r in range(q+1,n):
            if s_list[r]!=s_list[p] and s_list[r]!=s_list[q] and s_list[p]!=s_list[q] and r-q==q-p:
                count = count+1


print(sum-count)

### FIXED CODE ###

n= int(input())
s_list= list(input())
count=0
rr,bb,gg=0,0,0
for i in range(0,n):
    if s_list[i]=="R":
        rr=rr+1
    elif s_list[i]=="G":
        gg=gg+1
    else:
        bb=bb+1
sum=rr*gg*bb

for p in range(0,n-2):
    for q in range(p+1,n-1):
        if s_list[p] == s_list[q]:
            continue
        elif 2*q-p<n and s_list[2*q-p]!=s_list[p] and s_list[2*q-p]!=s_list[q]:
            count= count+1
print(sum-count)
### BUGGY CODE ###

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))

memo = [0] * (N+1)
memo[0]=1
for i in range(0,M-1):
    if A[i+1] - A[i] == 1:
        print(0)
        sys.exit()
if not 1 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        memo[i] = (memo[i - 1] + memo[i - 2]) % lim
print(memo[-1])


### FIXED CODE ###

#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A = set([int(input()) for _ in range(M)])
memo = [0] * (N+1)
memo[0]=1

if not 1 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        memo[i] = (memo[i - 1] + memo[i - 2]) % lim
print(memo[-1])
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())
ans = 0
for i in range(1, N):
    temp = len(make_divisors(N-i))
    #print(make_divisors(N-i), temp)
    ans += temp
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N):
    ans += (N-1)//i
    #print(N//i)
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf")]*n
dp[0] = 0
for i in range(0,n-1):
  for j in range(1,k+1):
    if (i-j)>=-1:
      dp[i+1]=min(dp[i+1],dp[i+1-j]+abs(h[i+1]-h[i+1-j]))
print(dp[-1])

### FIXED CODE ###

def solve():
  n,k = map(int,input().split())
  h = list(map(int,input().split()))
  dp = [float("inf")]*n
  dp[0] = 0
  for i in range(0,n-1):
    for j in range(1,k+1):
      if (i-j)>=-1:
        dp[i+1]=min(dp[i+1],dp[i+1-j]+abs(h[i+1]-h[i+1-j]))
  print(dp[-1])
solve()
### BUGGY CODE ###

N,K= map(int, input().split())
S=[int(x) for x in list(str(input()))]

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[now]
        cnt=1

if cnt!=0:
    nums.append(cnt)

if len(nums)%2==0:
    nums.append(0)

Add=2*K+1
ans=0

for i in range(0,len(nums),2):
    tmp=0
    left=i
    right=min(i+Add,len(nums))
    for j in range(left,right):
        tmp=tmp+nums[j]
        
    ans=max(ans,tmp)

print(ans)


### FIXED CODE ###

N,K= map(int, input().split())
S=[int(x) for x in list(str(input()))]

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[now]
        cnt=1

if cnt!=0:
    nums.append(cnt)

if len(nums)%2==0:
    nums.append(0)

Add=2*K+1
ans=0
left=0
right=0
tmp=0
for i in range(0,len(nums),2):
    
    nextleft=i
    nextright=min(i+Add,len(nums))
    while nextleft>left:
        tmp=tmp-nums[left]
        left+=1

    while nextright>right:
        tmp=tmp+nums[right]
        right+=1
        

    ans=max(ans,tmp)

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

X = int(input())
A = 0
B = 0

while True:
  ans = A**5-B**5
  if ans == X:
    break
  elif ans < X:
    B -= 1
  elif ans > X:
    B += 1
    A += 1
print("{} {}".format(A,B))

### FIXED CODE ###

X = int(input())
A = 0
B = int(-X**(1/5))

while True:
  ans = A**5-B**5
  if ans == X:
    break
  elif ans < X:
    A += 1
  elif ans > X:
    B += 1
print("{} {}".format(A,B))
### BUGGY CODE ###

S=list(input())
count=0
a=2*10**5+1
while count!=a:
    a=count
    for i in range(len(S)-1):
        if S[i]=="B" and S[i+1]=="W":
            S[i]="W"
            S[i+1]="B"
            count+=1

print(count)

### FIXED CODE ###

S=input()
count=0
ans=0
for i in range(len(S)):
    if S[i]=="W":
        ans+=count
    else:
        count+=1
print(ans)
### BUGGY CODE ###

n=int(input())
gg=[input() for _ in [0]*n]
graph=[[] for _ in [0]*n]


inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]

for i in range(n):
    dist[i][i]=0
    for j in range(n):
        if gg[i][j]=="1":
            graph[i].append(j)
            dist[i][j]=1
            dist[j][i]=1
q=[0]
dp=[0]*n
dp[0]=1


flag=True
while q:
    i=q.pop()
    for j in graph[i]:
        if dp[j]==0:
            dp[j]=dp[i]*(-1)
            q.append(j)
        elif dp[j]==dp[i]:
            flag=False
            break
    if flag==False:
        break

        

if flag==False:
    print(-1)
else:
    for k in range(n):
        for i in range(n):
            for j in range(n):dist[i][j]=min(dist[i][j],(dist[i][k]+dist[k][j]))
    print(max([max([i for i in j]) for j in dist])+1)


### FIXED CODE ###

n=int(input())
gg=[input() for _ in [0]*n]
graph=[[] for _ in [0]*n]


inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]

for i in range(n):
    dist[i][i]=0
    for j in range(n):
        if gg[i][j]=="1":
            graph[i].append(j)
            dist[i][j]=1
            dist[j][i]=1
q=[0]
dp=[0]*n
dp[0]=1


flag=True
while q:
    i=q.pop()
    for j in graph[i]:
        if dp[j]==0:
            dp[j]=dp[i]*(-1)
            q.append(j)
        elif dp[j]==dp[i]:
            flag=False
            break
    if flag==False:
        break

        

if flag==False:
    print(-1)
else:
    for k in range(n):
        for i in range(n):
            for j in range(n):dist[i][j]=min(dist[i][j],(dist[i][k]+dist[k][j]))
    print(max([max([i for i in j]) for j in dist])+1)
### BUGGY CODE ###

import numpy as np
n = int(input())
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)

a_num = np.zeros(n)
b_num = np.zeros(n)

left = 0
right = 0
while left <= n-1 and right <= n-1:
    if a[left] < b[right]:
        a_num[left:] += 1
        right += 1
    else:
        left += 1

left = 0
right = 0
while left <= n-1 and right <= n-1:
    if b[left] < c[right]:
        b_num[left:] += 1
        right += 1
    else:
        left += 1

ans = 0
for i in a_num:
    i = int(i)
    ans += sum(b_num[:i])
print(int(ans))

### FIXED CODE ###

from bisect import bisect_left, bisect_right
n = int(input())
a = sorted(list(map(int, input().split())))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))

ans = 0
for i in b:
    x = bisect_left(a, i)
    y = n - bisect_right(c, i)
    ans += x * y
print(ans)
### BUGGY CODE ###

from math import gcd
from copy import copy
a, b = map(int, input().split())

def div(x):
    ret = []
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)
    
    return ret

def judge_prime(x):
    cnt = 0
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            cnt += 1
    if cnt == 1:
        return True
    return False

div_a = div(a)
div_b = div(b)

data = list(set(div_a) & set(div_b))

ans = 0
for x in data:
    if judge_prime(x):
        ans += 1
print(ans)

### FIXED CODE ###

from math import gcd
from copy import copy
a, b = map(int, input().split())

def div(x):
    ret = []
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)
    
    return ret

def judge_prime(x):
    cnt = 0
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            cnt += 1
        if cnt >= 2:
            return False
    return True

div_a = div(a)
div_b = div(b)

data = list(set(div_a) & set(div_b))

ans = 0
for x in data:
    if judge_prime(x):
        ans += 1
print(ans)
### BUGGY CODE ###

import math

n,k = input().split()
p = input().split()

n = int(n)
k = int(k)
p = [int(s) for s in p]

#print(p)

ex =0
xs=[]

for i in range(n-k+1):
    ext = 0
    for f in range(k):
        xs = list(range(1,p[i+f]+1))
        #print(i,f, p[i+f],xs,sum(xs))
        xs = [s*1/p[i+f] for s in xs]
        #print(xs)
        ext +=sum(xs)
        #print(ext)
        
    if ext>ex:
        ex = ext
print('{:.12f}'.format(ex))

### FIXED CODE ###

import math

n,k = input().split()
p = input().split()

n = int(n)
k = int(k)
#p = [int(s) for s in p]

#print(p)

ex =0
ext = []
ext2 = []
for f in range(n):
    pi = int(p[f])
    xs =(pi+1)/2
    ext.append(xs)

ext2.append(ext[0])
for i in range(1,n):
    ext2.append(ext2[i-1]+ext[i])

ex = ext2[k-1]
for j in range(1,n-k+1):
    ext3 =ext2[j+k-1]-ext2[j-1]
    if ext3 > ex: ex = ext3

print('{:.12f}'.format(ex))
### BUGGY CODE ###

s=input()
b=0
m=len(s)
c=[0 for i in range(2019)]
c[0]=c[0]+1
a=""
e=0
for i in range(m-1,-1,-1):
    a=str(a)
    a=s[i]+a
    a=int(a)
    d=a%2019
    c[d]=c[d]+1
for i in c:
    e+=i*(i-1)//2
print(e)


### FIXED CODE ###

s=input()
b=0
m=len(s)
c=[0 for i in range(2019)]
c[0]=c[0]+1
a=""
e=0
f=1
s= ''.join(list(reversed(s)))
for i in s:
    e+=int(i)*f
    g=e%2019
    c[g]+=1
    f*=10
    f%=2019
e = sum(i * (i - 1) // 2 for i in c)
print(e)
### BUGGY CODE ###

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

cnt = 1

for i in range(1, N):
  for j in range(i-1, -1, -1):
    if P[i] > P[j]:
      break
  else:
    cnt += 1


print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
min_p = P[0]
cnt = 0

for p in P:
  if p <= min_p:
    min_p = p
    cnt += 1

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

N = input()                                                                                         
c = input()

N = int(N)                                                                                          
                                                                                                    
dp = []                                                                                             
                                                                                                    
for i in range(N + 1):                                                                                  
    dp.append(max(c[:i].count('W'), c[i:].count('R')))                                              
                                                                                                    
print(min(dp))


### FIXED CODE ###

N = input()                                                                                         
c = input()                                                                                         
                                                                                                    
N = int(N)                                                                                          
                                                                                                    
n_r = c.count('R')                                                                                  
print(c[n_r:].count('R'))
### BUGGY CODE ###

s=input()
top=bool()
n=int(input())
for i in range(n):
  q=list(map(str,input().split()))
  if q[0]=='1':
    top=not top
  else:
    if (q[1]=="1") ^ top:
      s=q[2]+s
    else:
      s=s+q[2]
if top:
  print(*list(reversed(list(s))),sep='')
else:
  print(s)


### FIXED CODE ###

s=list(input())
top=bool()
t=[]
u=[]
n=int(input())
for i in range(n):
  q=list(map(str,input().split()))
  if q[0]=='1':
    top=not top
  else:
    if (q[1]=="1") ^ top:
      t.append(q[2])
    else:
      u.append(q[2])
s=list(reversed(t))+s+u
if top:
  print(*list(reversed(s)),sep='')
else:
  print(*s,sep='')
### BUGGY CODE ###

m,n = list(map(int, input().split()))
MOD=10**9+7
if abs(m-n) > 1:
    print(0)
    exit()

def fact(x, mod):
    ans=1
    for i in range(2, x+1):
        ans*=i%mod
    return ans

if m>n:
    n,m = m,n
    
f = fact(m,MOD)
if m==n:
    print(f * f * 2 % MOD)
else:
    print(f * f * n % MOD)

### FIXED CODE ###

m,n = list(map(int, input().split()))
MOD=10**9+7
if abs(m-n) > 1:
    print(0)
    exit()

def fact(x):
    ans=1
    for i in range(2, x+1):
        ans=ans%MOD*i
    return ans

if m>n:
    n,m = m,n
    
f = fact(m)
if m==n:
    print(f * f * 2 % MOD)
else:
    print(f * f * n % MOD)
### BUGGY CODE ###

def pred(i, lst, offset):
  for cmpd in lst[offset:i+1]:
    if lst[i] > cmpd:
      return False
  return True

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

sum = 0
offset = 0
for i in range(n):
  if pred(i, p, offset):
    sum += 1
    offset = i

print(sum)

### FIXED CODE ###

def pred(i, lst, offset):
  for cmpd in lst[offset:i+1]:
    if lst[i] > cmpd:
      return False
  return True

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

sum = 0
minimum = n + 1
for i in range(n):
  if p[i] < minimum:
    sum += 1
    minimum = p[i]

#sum = 0
#offset = 0
#for i in range(n):
#  if pred(i, p, offset):
#    sum += 1
#    offset = i

print(sum)
### BUGGY CODE ###

import copy
N = int(input())
a = [input() for i in range(N)]
b = copy.deepcopy(a)
for i in range(len(a)):
    del b[i]
    print(max(b))
    b = copy.deepcopy(a)

### FIXED CODE ###

N = int(input())
a = [int(input()) for i in range(N)]
A = max(a)
b = sorted(a)[-2]
if a.count(A) > 1:
    for i in range(len(a)):
        print(A)
else:
    for i in range(len(a)):
        if a[i] == A:
            print(b)
        else:
            print(A)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
for i in range(61):
    bit = 1 << i
    count = 0
    for j in range(N):
        if bit & A[j]:
            count += 1
    ans += 2**i * count * (N-count) % mod
print(ans % mod)


### FIXED CODE ###

mod = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
ans = 0
loop_count = len(format(max(A), "b"))

for i in range(loop_count):
    tmp = 0
    for ai in A:
        if ((1 << i) & ai) > 0:
            tmp += 1
    ans += (1 << i) * tmp * (N - tmp) % mod
print(ans % mod)
### BUGGY CODE ###

n, k = map(int, input().split())
currAbsValue = abs(n-k)
while currAbsValue < n:
    n = currAbsValue
    currAbsValue = abs(n-k)
    if n == currAbsValue:
        break
print(n)

### FIXED CODE ###

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


minV = (n%k) if (n%k) < (k-n%k) else (k-n%k)
print(minV)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputList()
    
    ans = [0]*N
    B=[]
    ans_str = ""
    for i in range(N, 0, -1):
        cons = 0
        for j in range(i, N+1, i):
            if ans[j-1] == 1:
                cons += 1
        if A[i-1] == 1 and cons % 2 == 0:
            ans[i-1] = 1
            B.append(i)
            continue
        if A[i-1] == 0 and cons % 2 == 1:
            ans[i-1] = 1
            B.append(i)
            continue
            
    print(len(B))
    for i in B:
        ans_str = ans_str + str(i) + " "
    print(ans_str)
    #print(*B)
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
N=INT()
A=LIST()
 
# その位置にボールを入れるかを保持するA2
A2=[0]*N
B=[]
# 後ろから決めていく
for i in range(N-1, -1, -1):
    cur=i+1
    cnt=0
    # curの倍数を全部見に行く
    for j in range(cur*2, N+1, cur):
        cnt^=A2[j-1]
    # ボールを入れるべきかどうか
    if A[i]!=cnt:
        B.append(cur)
        A2[i]=1
 
print(len(B))
print(*B)