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

from itertools import accumulate
from copy import deepcopy

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+1)

if k > 41:
    k = 41

for _ in range(k):
    b = [0]*(n+1)
    for i,j in enumerate(a):
        b[max(0,i-j)] += 1
        b[min(n,i+j+1)] -= 1
    a = list(accumulate(b))

print(*a[:-1])

### FIXED CODE ###

from itertools import accumulate
from copy import deepcopy

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0]*(n+1)

if k > 41:
    k = 41

for _ in range(k):
    b = [0]*(n+1)
    for i,j in enumerate(a):
        b[max(0,i-j)] += 1
        b[min(n,i+j+1)] -= 1
    a = list(accumulate(b))
    for i in range(n+1):
        if a[i] >= n:
            a[i] = n

print(*a[:-1])
### BUGGY CODE ###

MOD = 10**9 + 7
P = 97

def solve(N, S):
    A = [ord(c) - ord('a') + 2 for c in S]
    H = [0]
    pwr = 1
    for x in A:
        H.append(H[-1] + x * pwr)
        H[-1] %= MOD
        pwr = pwr * P % MOD

    def gethash(i, j):
        ha = H[j] - H[i]
        ha *= pow(pow(P, i, MOD), MOD-2, MOD)
        return ha % MOD

    def match(L):
        if L == 0: return True
        for i in xrange(N - L + 1):
            h1 = gethash(i, i+L)
            for j in xrange(i + L, N - L + 1):
                if h1 == gethash(j, j+L) and A[i:i+L] == A[j:j+L]:
                    return True

    #print map(doublematch, range(len(A)))
    lo, hi = 0, len(A) / 2
    while lo < hi:
        mi = (lo + hi + 1) / 2
        if match(mi):
            lo = mi
        else:
            hi = mi - 1
    return lo

print solve(int(raw_input()), raw_input())


### FIXED CODE ###

rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

MOD = 10**9 + 7
P = 97
def solve(N, S):
    A = [0]
    rawA = []
    #powers = []
    ha = 0
    #pwr = 1
    for c in S:
        x = ord(c) - ord('a') + 2
        rawA.append(x)
        #ha += x * pwr
        #ha %= MOD
        #powers.append(pwr)
        ha += x
        A.append(ha)
        #pwr *= P
        #pwr %= MOD
    #powers.append(pwr)

    def gethash(i, j):
        ha = A[j] - A[i]
        #ha *= pow(powers[i-1], MOD-2, MOD)
        ha %= MOD
        #print 'gh', i,j, ';', ha
        return ha

    # A
    #print 'g1',gethash(2, 2+5)
    #print 'g2', gethash(8, 8+5)
    
    def doublematch(L):
        if L == 0: return True
        for i in xrange(N - L + 1):
            for j in xrange(i + L, N - L + 1):
                if gethash(i, i+L) == gethash(j, j+L) and rawA[i:i+L] == rawA[j:j+L]:
                    return True

    #print map(doublematch, range(len(A)))
    lo, hi = 0, len(A) / 2
    while lo < hi:
        mi = (lo + hi + 1) / 2
        if doublematch(mi):
            lo = mi
        else:
            hi = mi - 1
    return lo

print solve(rri(), rr())
### BUGGY CODE ###

s=[int(i) for i in input()]
n=len(s)
updated=True
while updated:
    updated=False
    for i in range(len(s)-1):
        while i in range(len(s)-1) and s[i] != s[i+1]:
            del s[i]
            del s[i]
            updated=True

print(n-len(s))


### FIXED CODE ###

s=input()

stack=[]
for si in s:
    stack.append(si)
    if len(stack) >= 2 and stack[-1] != stack[-2]:
        del stack[-1]
        del stack[-1]
print(len(s)-len(stack))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import math
from collections import Counter

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)

def C(n, r):
    return P(n, r)//math.factorial(r)

N = int(input())
arr = [input() for i in range(N)]
mar_arr = [j for j in arr if j[0] == "M" or j[0] == "A" or j[0] == "R" or j[0] == "C" or j[0] == "H"]
ini_arr = [k[0] for k in mar_arr]
dic = Counter(ini_arr)
key_num = len(dic)
val_num = sum(v for v in dic.values())
if key_num < 3:
    print(0)
else:
    total = C(len(ini_arr), 3)
    for i in dic.values():
        if i == 2:
            total -= C(val_num - i, 1)
        elif i >= 3:
            total -= C(i, 2) * C(val_num - i, 1)  + C(i, 3)
    print(total)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

n = int(input())
t = [0] * n
for i in range(n):
    t[i] =input()[0]
t2 = [t.count(i) for i in ["M","A","R","C","H"]]
ans = 0
for i in range(5):
    for j in range(5):
        if j == i:
            break
        for k in range(5):
            if k == j:
                break
            ans += t2[i] * t2[j] * t2[k]
print(ans)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
ans = 100000000000000
for i in range(1,n):
  a = abs(sum(A[:i])-sum(A[i:]))
  ans = min(ans, a)
print(ans)

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
ans = 100000000000000
a = 0
b = sum(A)
for i in range(n-1):
  a += A[i]
  b -= A[i]
  c = abs(a-b)
  ans = min(ans, c)
print(ans)
### BUGGY CODE ###

n=int(input())

ans=0
for i in range(n):
  ans+=i
  
print(ans)

### FIXED CODE ###

n=int(input())

ans=n*(n-1)//2
  
print(int(ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1), (-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for dh, dw in directions:
        if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] != "#":
            if S[h+dh][w+dw] > S[h][w]:
                S[h+dh][w+dw] = S[h][w]
                q.append((h+dh, w+dw))
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "#":
            if S[h+wh][w+ww] > S[h][w] + 1:
                S[h+wh][w+ww] = S[h][w] + 1
                q.append((h+wh, w+ww))
 
if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]
 
from collections import deque
 
q = deque([(CH-1, CW-1)])
 
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2), 
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            S[i][j] = 10**7
S[CH-1][CW-1] = 0

while q:
    h, w = q.popleft()
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] != "#":
            if (wh, ww) in directions:
                if S[h+wh][w+ww] > S[h][w]:
                    S[h+wh][w+ww] = S[h][w]
                    q.appendleft((h+wh, w+ww))
            else:
                if S[h+wh][w+ww] > S[h][w] + 1:
                    S[h+wh][w+ww] = S[h][w] + 1
                    q.append((h+wh, w+ww))

if S[DH-1][DW-1] == 10**7:
    print(-1)
else:
    print(S[DH-1][DW-1])
### BUGGY CODE ###

from bisect import bisect_left as bl
from collections import deque
from fractions import gcd
#from math import factorial
from math import sqrt
from math import ceil
from itertools import permutations
from heapq import *
from collections import defaultdict
from copy import deepcopy

A,B,Q=map(int,input().split())
S=[]
T=[]
X=[]
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
def rl(X,a):
    ind=bl(X,a)
    if ind>=len(X):
        return ind-1
    return ind
def ll(X,a):
    ind=bl(X,a)-1
    if ind<0:
        return ind+1
    return ind
for i in range(Q):
    x=int(input())
    a=S[rl(S,x)]
    ad=min(abs(T[rl(T,a)]-a),abs(T[ll(T,a)]-a))
    a=abs(a-x)+ad
    #print("a:",a)

    b=S[ll(S,x)]
    bd=min(abs(T[rl(T,b)]-b),abs(T[ll(T,b)]-b))
    b=abs(b-x)+bd
    #print("b:",b)

    c=T[rl(T,x)]
    cd=min(abs(S[rl(S,c)]-c),abs(S[ll(S,c)]-c))
    c=abs(c-x)+cd
    #print("c:",c)

    d=T[ll(T,x)]
    dd=min(abs(S[rl(S,d)]-d),abs(S[ll(S,d)]-d))
    d=abs(d-x)+dd
    #print("d:",d)

    print(min(a,b,c,d))


### FIXED CODE ###

from bisect import bisect_left as bl
A,B,Q=map(int,input().split())
S=[]
T=[]
X=[]
INF=10**18
S.append(-INF)
T.append(-INF)
for i in range(A):
    S.append(int(input()))
for i in range(B):
    T.append(int(input()))
S.append(INF)
T.append(INF)
for i in range(Q):
    x=int(input())
    b,d=bl(S,x),bl(T,x)
    res=INF
    for s in [S[b-1],S[b]]:
        for t in [T[d-1],T[d]]:
            d1,d2=abs(s-x)+abs(t-s),abs(t-x)+abs(s-t)
            res=min(res,d1,d2)
    print(res)
### BUGGY CODE ###

import numpy as np
from functools import reduce
import math

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

a = int(input())
result = 0

for i in range(1, a+1):
  for j in range(1, a+1):
    for k in range(1, a+1):
      result += math.gcd(math.gcd(i, j),k)
      
print(result)


### FIXED CODE ###

from functools import reduce
import math

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

a = int(input())
result = 0

for i in range(1, a+1):
  for j in range(1, a+1):
    for k in range(1, a+1):
      result += math.gcd(math.gcd(i, j),k)
      
print(result)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

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

if K == 0:
    print (1)
    exit()

dp = [[0] * (K + 1) for _ in range(N + 1)]
for j in range(K + 1):
    dp[N][j] = 1
# dp[N][0] = 1
# print (dp[N])
for i in range(N - 1, -1, -1):
    for j in range(K + 1):
        if j <= A[i]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = dp[i + 1][j] - dp[i + 1][j - A[i] - 1]
    # print (i)
    # print (dp[i])
    for j in range(K):
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= MOD
    # print (dp[i])
    
print ((dp[0][K] - dp[0][K - 1]) % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7

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

if K == 0:
    print (1)
    exit()

dp = [[0] * (K + 1) for _ in range(N + 1)]
for j in range(K + 1):
    dp[N][j] = 1
# dp[N][0] = 1
# print (dp[N])
for i in range(N - 1, -1, -1):
    for j in range(K + 1):
        if j <= A[i]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = dp[i + 1][j] - dp[i + 1][j - A[i] - 1]
    # print (i)
    # print (dp[i])
    for j in range(K):
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= MOD
    # print (dp[i])
    
print ((dp[0][K] - dp[0][K - 1]) % MOD)
### BUGGY CODE ###

# import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

cost0 = deque()

cost0.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()
walk=[(1,0),(0,1),(-1,0),(0,-1)]
warp = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
# print(warp)

cost1 = deque()

while 0 < len(cost0):
	h,w,c=cost0.popleft()
	cost1.append((h,w,c))

	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				cost0.appendleft((h+i,w+j,Cost[h+i][w+j]))

	if len(cost0) == 0:

		while 0 < len(cost1):
			h,w,c=cost1.popleft()
			# print(h,w,c)
			for i,j in warp:
				# print(i,j)
				if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
					if S[h+i][w+j] == '.':
						if c + 1 < Cost[h+i][w+j]:
							Cost[h+i][w+j] = c + 1
							cost0.append((h+i,w+j,Cost[h+i][w+j]))


if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-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())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

n,k,q=map(int,input().split())
l=[int(input()) for i in range(q)]
d=dict(zip(range(n),[k]*n))

for i in l:
  for j in d.keys():
    if i==j:
      d[i-1]+=1

for i in d.values():
  if i-q>0:
    print('Yes')
  else:
    print('No')




### FIXED CODE ###

n,k,q=map(int,input().split())
l=[int(input()) for i in range(q)]
d=dict.fromkeys(range(n),k)

for i in l:
  d[i-1]+=1

for i in d.values():
  if i-q>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import sys
from collections import deque


def LI():
    return list(map(int, input().split()))


def LSH(h):
    return [list(input()) for _ in range(h)]


H, W = LI()
A = LSH(H)
MAP = [[0 for i in range(W)]for j in range(H)]
white = 0
for i in range(H):
    S = A[i]
    for j in range(W):
        if S[j] == "#":
            MAP[i][j] = "#"
        else:
            MAP[i][j] = "."
            white += 1
d = deque()
d.append([0, 0])
looked = [[0 for i in range(W)]for j in range(H)]
looked[0][0] = 1
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
count = -1

while d:
    h, w = d.popleft()
    for i in move:
        a = h+i[0]
        b = w+i[0]
        if not(0 <= a < H) or not(0 <= b < W) or looked[a][b] == 0 or MAP[a][b] == "#":
            continue
        if a == H-1 and b == W-1:
            count = looked[h][w]+1
            break
        d.append([a, b])
        looked[a][b] = looked[h][w]+1
    if count != -1:
        break
if count == -1:
    print(count)
    sys.exit()

print(white-count)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
MASUlist = [input() for _ in range(H)]
MASU = [[0 for i in range(W)]for j in range(H)]
white = 0
for i in range(H):
    S = MASUlist[i]
    for j in range(W):
        if S[j] == "#":
            MASU[i][j] = 1
        else:
            MASU[i][j] = 0
            white += 1
MASU[H-1][W-1] = 2
d = deque()
d.append([0, 0])
dx_dy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
looked = [[0 for i in range(W)]for j in range(H)]
looked[0][0] = 1

while d:
    x = d.popleft()
    lookx = x[0]
    looky = x[1]
    for i in dx_dy:
        a = lookx+i[0]
        b = looky+i[1]
        if not(0 <= a < H) or not(0 <= b < W) or MASU[a][b] == 1 or looked[a][b] != 0:
            continue
        d.append([a, b])
        looked[a][b] = looked[lookx][looky]+1

ans = looked[H-1][W-1]
if ans == 0:
    print(-1)
else:
    print(white-ans)
### BUGGY CODE ###

S = input()

Q = int(input())

for i in range(Q):
  *T, = map(str,input().split())
  if int(T[0]) == 1:
    S = S[::-1]
  elif int(T[1]) == 1:
    S = T[2]+S
  else:
    S = S+T[2]
    
print(S) 

### FIXED CODE ###

from collections import deque

S = deque(input())

Q = int(input())

c = False
for i in range(Q):
  *T, = map(str,input().split())
  if len(T) == 1:
    c = not c  
  elif (int(T[1]) == 1 and not c) or (int(T[1]) == 2 and c):
    S.appendleft(T[2])
  else:
    S.append(T[2])

print("".join(S) if not c else "".join(list(reversed(S))))
### BUGGY CODE ###

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

ac = []
wa = {}

for _ in range(M):
    p_i, s_i = input().split()
    if s_i == "AC":
        ac.append(p_i)
        ac = list(set(ac))
    elif s_i == "WA":
        if p_i not in ac:
            if p_i not in wa.keys():
                wa[p_i] = 1
            else:
                wa[p_i] += 1
                
ac = set(ac)
wa = {p_i: count for p_i, count in wa.items() if p_i in ac}

print(len(ac), sum(wa.values()))

### FIXED CODE ###

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

ac = 0
wa = 0
ac_status = [0 for i in range(N)]
wa_status = [0 for i in range(N)]

for _ in range(M):
    p_i, s_i = input().split()
    if s_i == "AC" and ac_status[int(p_i) - 1] == 0:
        ac += 1
        ac_status[int(p_i) - 1] += 1
        wa += wa_status[int(p_i) - 1]
    if s_i == "WA":
        wa_status[int(p_i) - 1] += 1

print(ac, wa)
### BUGGY CODE ###

s = input()
q = int(input())

for _ in range(q):
    Q = list(map(str, input().split()))
    if Q[0] == "1":
        s = s[::-1]
    else:
        if Q[1] == "1":
            s = Q[2] + s
        else:
            s = s + Q[2]

print("".join(s))

### FIXED CODE ###

s = input()
q = int(input())
count = 0
a = []
b = []

for _ in range(q):
    Q = list(map(str, input().split()))
    if Q[0] == "1":
        count += 1
    else:
        if (int(Q[1])+count)%2 == 1:
            a.append(Q[2])
        else:
            b.append(Q[2])
    
        
a = "".join(a[::-1])
b = "".join(b)
s = a + s + b
if count%2 == 1 and count != 0:
    s = s[::-1]
print("".join(s))
### BUGGY CODE ###

import fractions

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


rev = [modpow(i, mod - 2) % mod for i in range(10 ** 6 + 1)]
N = int(input())
A = list(map(int, input().split(" ")))
lcm = 1
for a in A:
    lcm = lcm * a * rev[fractions.gcd(lcm, a)]
print(lcm % mod)

ans = 0
for a in A:
    ans += (lcm * rev[a]) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


mod = 10 ** 9 + 7
N = int(input().strip())
A = list(map(int, input().strip().split(" ")))

lcm = 1
for a in A:
    lcm = a // fractions.gcd(a, lcm) * lcm

ans = 0
for a in A:
    ans += lcm // a

print(ans % mod)
### BUGGY CODE ###

def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  
  def memorize(f):
    table={}
    def func(*args):
        if not args in table:
            table[args]=f(*args)
        return table[args]
    return func

  @memorize
  def sushi(c1,c2,c3):    
      tmp=c1+c2+c3
      if tmp==0:
        return 0
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()
        

### FIXED CODE ###

def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  a=c1+c2+c3+1
  b=c2+c3+1
  c=c3+1
  
  dp=[[[0]*a for _ in range(b)] for _ in  range(c)]
  
  for i in range(c):
    for j in range(b-i):
      for k in range(a-i-j):
        tmp=i+j+k
        if tmp==0:
          continue
        else:
          dp[i][j][k]=n/tmp
          if i>0:
            dp[i][j][k]+=i*dp[i-1][j+1][k]/tmp
          if j>0:
            dp[i][j][k]+=j*dp[i][j-1][k+1]/tmp
          if k>0:
            dp[i][j][k]+=k*dp[i][j][k-1]/tmp
  print(dp[c3][c2][c1])
             
if __name__=='__main__':
  main()
### BUGGY CODE ###

import numpy as np
n = int(input())
a = [int(i) for i in input().split()] 

a = np.array(a)
ls = a
def func(ind):
    tmp = list(range(2*ind-1, n, ind))
    s = ls[tmp].sum()
    return s%2

st = int(n/2)
for ind in range(st, 0, -1):
    if a[ind-1] == func(ind):
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        
print(sum(ls))
ans = np.where(ls==1)[0]+1
for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()] 
ls = a

st = int(n/2)
ans =  [i+st+1 for i, n in enumerate(a[st:]) if n ==1] 
for ind in range(st, 0, -1):
    tmp = [ls[i] for i in range(2*ind-1, n, ind)]
    s = sum(tmp)%2
    if a[ind-1] == s:
        ls[ind-1] = 0
    else:
        ls[ind-1] = 1
        ans.append(ind)
        
print(sum(ls))
print(' '.join(map(str, ans)))
### BUGGY CODE ###

import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

index={moji:[] for moji in alphabetlist}
for i in range(N):
    index[s[i]].append(i)

dp=[[] for i in range(0,N)]

for i in range(0,N):
    if index[t[0]]:
        if i>=index[t[0]][0]:
            dp[i]=[t[0]]

for i in range(1,M):
    x=t[i]
    if index[x]:
        for j in range(N-1,index[x][0]-1,-1):
            next=index[x][bisect.bisect_right(index[x],j)-1]-1
            if next>=0:
                if len(dp[j])<1+len(dp[next]):
                    xxx=copy.copy(dp[next])
                    xxx.append(t[i])
                    dp[j]=xxx
            else:
                if dp[j]==[]:
                    dp[j]=[t[i]]

print(''.join(dp[N-1]))

### FIXED CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

ans=[]
i=N
j=M
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))
### BUGGY CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)
ans = ""
dp = [[0]*(lt+1) for i in range(ls+1)]

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

x = lt
y = ls

while x-1>=0 and y-1>=0:
    if dp[y][x] == dp[y][x-1]:
        x -= 1
    elif dp[y][x] == dp[y-1][x]:
        y -= 1
    else:
        ans = s[y-1] + ans
        x -= 1
        y -= 1

print(ans)

### FIXED CODE ###

s = input()
t = input()
N = len(s)
M = len(t)

dp = [[0]*(N+1) for i in range(M+1)]

for i in range(1,M+1):
  for j in range(1,N+1):
    if s[j-1] == t[i-1]:
      dp[i][j] = dp[i-1][j-1]+1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
L = dp[-1][-1]
i = M
j = N
ans = [""]*L
cur = L-1
while i>=0 and j>=0:
  if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
    ans[cur] = s[j-1]
    i -= 1
    j -= 1
    cur -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    j -= 1
print("".join(ans))