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

N, M, K = map(int, input().split())
A = set([tuple(map(int, input().split())) for _ in range(M)])
C = set([tuple(map(int, input().split())) for _ in range(K)])
tmpX = set()

def mySearch(i):
  global tmpX
  # 友達を探す
  tmp = set()
  for a in A:
    if a[0] == i:
      # 既に調べた人を除外する
      if a[1] not in tmpX:
        tmp.add(a[1])
        #print('i:{}, tmp'.format(i), tmp)
    elif a[1] == i:
      if a[0] not in tmpX:
        tmp.add(a[0])
        #print('i:{}, tmp'.format(i), tmp)
  tmpX = tmpX | tmp
  #print('tmpX', tmpX)
  # 再帰
  for t in tmp:
    mySearch(t)

def main():
  global tmpX
  ans = [None]*N
  
  for i in range(N):
    tomo = set()# 友達リスト
    for a in A:
      if a[0] == i+1:
        tomo.add(a[1])
      elif a[1] == i+1:
        tomo.add(a[0])
        
    block = set()# ブロックリスト
    for c in C:
      if c[0] == i+1:
        block.add(c[1])
      elif c[1] == i+1:
        block.add(c[0])
    
    tmpX = set()
    mySearch(i+1)
    #print('tmpX',tmpX, tomo, block)
    ans[i] = len(tmpX - tomo - block - set([i+1]))
    #print('ans[{}]'.format(i), tmpX - tomo - block)
  print(*ans)
  
main()

### FIXED CODE ###

#!/usr/bin/env python3

class UnionFind():
        def __init__(self, n):
            self.parents = list(range(n))
            self.size = [1] * n
    
        def find(self, x):
            if self.parents[x] == x:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                if self.parents[x] > self.parents[y]:
                    x, y = y,x
                self.parents[y] = x
                self.size[x] += self.size[y]

def main():
    N, M, K = map(int, input().split())
    friend_adj = [[] for _ in range(N)]
    block_adj = [[] for _ in range(N)]
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        friend_adj[a].append(b)
        friend_adj[b].append(a)
        uf.union(a,b)
    for _ in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        if uf.find(c) == uf.find(d):
            friend_adj[c].append(d)
            friend_adj[d].append(c)

    ans = [uf.size[uf.find(i)]-1 for i in range(N)]

    for i in range(N):
        ans[i] -= len(friend_adj[i])        
        # for b in block_adj[i]:
        #     if uf.find(b) == uf.find(i):
        #         ans[i] -= 1
    print(*ans)
    
    
    

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

import sys
n,k = map(int,input().split())
m = n
c = 0
r = True
while r == True:
    if k >= 2*m:
        r = False
    elif k >= m:
        c += 1
        r = False
    else:
        c += 1
        m -= k

print(abs(n-(c*k)))

### FIXED CODE ###

n,k = map(int,input().split())
a = [n%k,abs(n%k-k)]
print(min(a))
### BUGGY CODE ###

import sys
from bisect import bisect_right, insort_left
N = int(sys.stdin.readline())
a_list = [int(sys.stdin.readline()) for _ in range(N)]


que = []

ans = 0
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        ans += 1
    else:
        idx = bisect_right(que, a-1)
        if idx == 0:
            insort_left(que, a)
            ans += 1
        else:
            que[idx-1] = a

print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_right, insort_left
from collections import deque
N = int(sys.stdin.readline())
a_list = [int(sys.stdin.readline()) for _ in range(N)]


que = []
que = deque(que)

ans = 0
min_num = float("inf")
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        min_num = a
        ans += 1
    else:
        idx = bisect_right(que, a-1)

        if idx == 0:
            que.appendleft(a)
            ans += 1
            min_num = a
        else:
            idx = bisect_right(que, a-1)
            que[idx-1] = a
            if idx -1 == 0:
                min_num = a
    #print(que, min_num)
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
	N = int(input())
	L = list(map(int, input().split()))
	L.sort()
	sum = 0
	for c in range(2, N):
		if L[c] < L[c - 1] + L[c - 2]:
			for b in range(c - 1, 0, -1):
				if L[c] < L[b] + L[b - 1]:
					for a in range(b - 1, -1, -1):
						if L[c] < L[b] + L[a]:
							sum += 1
						else:
							break
	print(sum)

### FIXED CODE ###

from bisect import bisect_left

if __name__ == "__main__":
	N = int(input())
	L = list(map(int, input().split()))
	L.sort()
	# print(L)
	sum = 0
	for a in range(N - 2):
		for b in range(a + 1, N - 1):
			key = L[a] + L[b]
			i = bisect_left(L, key)
			# print(a, b, i, i - b)
			sum += i - b - 1
	print(sum)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : 
    B = sorted(A[i:i+L])
    ans.append(B[0])
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

for i in range(q) :
  t = list(map(str,input().split()))
  if t[0] == '1' :
    s = s[::-1]
  if t[0] == '2' :
    f = t[1] ; c = t[2]
    if f == '1' :
      s = c + s
    else :
      s = s + c
      
print(s)


### FIXED CODE ###

from collections import deque

ss = input()
q = int(input())
s = deque()

for i in range(len(ss)) :
  s.append(ss[i])

r = 0
for i in range(q) :
  t = list(map(str,input().split()))
  if t[0] == '1' :
    r += 1
  if t[0] == '2' :
    f = t[1] ; c = t[2]
    if r%2 == 0 :
      if f == '1' :
        s.appendleft(c)
      else :
        s.append(c)
    else :
      if f == '2' :
        s.appendleft(c)
      else :
        s.append(c)
        
if r%2 == 1 :
  s.reverse()
  
print(*s,sep='')
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
x=0
for i in range(m):
  if t[i] in d:
    d.remove(t[i])
  else:
    x=1
    break
if x==0:print('YES')
else:print('NO')

### FIXED CODE ###

from collections import Counter
n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
D=Counter(d);T=Counter(t)
x=0
for i in list(set(t)):
  if D[i]<T[i]:
    x=1
    break
if x==0:print('YES')
else:print('NO')
### BUGGY CODE ###

from math import ceil

# 入力
N = int(input())
A = [int(input()) for i in range(N)]

MOD = 998244353


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


S = sum(A)
# 赤色の整数の和がiとなるような塗り方の個数
dp = [ModInt(0) for _ in range(S + 1)]
dp[0] = ModInt(1)
# 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
dp2 = [ModInt(0) for _ in range(S // 2 + 1)]
dp2[0] = ModInt(1)

# 動的計画法により、dp, dp2を求める
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = dp[i] * 2 + dp[i - a]
    for i in range(a - 1, -1, -1):
        dp[i] = dp[i] * 2
    for i in range(S // 2, a - 1, -1):
        dp2[i] = dp2[i] + dp2[i - a]

# 全ての塗り方の個数から、条件を満たさない塗り方の個数を差し引いて解を求める
ans = 3**N - 3 * sum(dp[ceil(S / 2):]) + (
    3 * dp2[S // 2] if S % 2 == 0 else
    0
)

# 出力
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

M = 998244353

S = sum(A)
dp = [0 for _ in range(S + 1)]
dp[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = (2 * dp[i] + dp[i - a]) % M
    for i in range(a - 1, -1, -1):
        dp[i] = (2 * dp[i]) % M
dp2 = [0 for _ in range(S + 1)]
dp2[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp2[i] = (dp2[i] + dp2[i - a]) % M
s = 0
for i in range((S + 1) // 2, S + 1):
    s = (s + dp[i]) % M
ans = (3**N - 3 * s) % M
if S % 2 == 0:
    ans = (3**N - 3 * s + 3 * dp2[S // 2]) % M
print(ans)
### BUGGY CODE ###

import copy
from collections import deque
h,w=map(int,input().split())
p=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
b=copy.deepcopy(p)
ans=0
#s0,s1=map(lambda x:int(x)-1,input().split())
#g0,g1=map(lambda x:int(x)-1,input().split())
for i in range(1,h+1):
    for j in range(1,w+1):
        for k in range(1,h+1):
            for z in range(1,w+1):
                p=copy.deepcopy(b)
                if p[i][j]=='.' and p[k][z]=='.':
                    s0,s1=i,j
                    g0,g1=k,z
                    p[s0][s1]=0
                    d=[(1,0),(-1,0),(0,1),(0,-1)]
                    q=deque([[s0,s1]])
                    while q:
                        x,y=q.popleft()
                        for dx,dy in d:
                            if p[x+dx][y+dy]==".":
                                p[x+dx][y+dy]=p[x][y]+1
                                q.append([x+dx,y+dy])
                    if ans<=p[g0][g1]:
                        ans=p[g0][g1]
print(ans)


### FIXED CODE ###

import _pickle as cPickle

from collections import deque
h,w=map(int,input().split())
p=[list("#"*(w+2))]+[list("#"+input()+"#") for i in range(h)]+[list("#"*(w+2))]
b=cPickle.loads(cPickle.dumps(p, -1))
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        p=cPickle.loads(cPickle.dumps(b, -1))
        if p[i][j]=='.':
            s0=i
            s1=j
            p[s0][s1]=0
            d=[(1,0),(-1,0),(0,1),(0,-1)]
            q=deque([[s0,s1]])
            while q:
                x,y=q.popleft()
                for dx,dy in d:
                    if p[x+dx][y+dy]==".":
                        p[x+dx][y+dy]=p[x][y]+1
                        q.append([x+dx,y+dy])
                        if ans<p[x+dx][y+dy]:
                            ans=p[x+dx][y+dy]
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

N, K = [int(x) for x in input().strip().split()]
highest = 0
lowest = 10 ** 9
high = [0] * N
low = [0] * N
q = deque([])
ans = 10 ** 9
pre = -1
H = sorted([int(input()) for _ in range(N)])
for n, ne in enumerate(H):
    q.append(ne)
    if len(q) > K:
        pre = q.popleft()
    if ne > highest:
        highest = ne
    if ne < lowest:
        lowest = ne
    if pre == highest:
        highest = max(q)
    if pre == lowest:
        lowest = min(q)
    high[n] = highest
    low[n] = lowest
    if n >= K - 1:
        ans = min(ans, highest - lowest)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = [int(x) for x in input().strip().split()]
H = sorted([int(input()) for _ in range(N)])
ans = 10 ** 9
for n in range(N - (K - 1)):
    ans = min(ans, H[n+K-1] - H[n])

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

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

ans = 1
for a in A:
    ans *= a
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

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

x = 10**18
ans = 1
for a in A:
    if ans != -1:
        ans *= a
    if ans > x:
        ans = -1
    if a == 0:
        ans = 0
        break
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
L = lr()
L.sort()
answer = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        candidate = L[j+1:]
        index = bisect_left(candidate, (L[i]+L[j]))
        answer += index

print(answer)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)
### BUGGY CODE ###


N=int(input())

s=0
for i in range(1,N):
    s+=i

print(s)

### FIXED CODE ###


N=int(input())

n=N-1

s=n*(n+1)//2

print(s)
### BUGGY CODE ###

import collections
import copy
n = input()
li = list(map(int,input().split()))
for i in range(len(li)):
    ans = 0
    li2 = copy.copy(li)
    li2[i] = 0
    c = collections.Counter(li2)
    c_key = list(c.values())
    for j in c_key:
        ans += ((j * (j-1)) // 2)
    print(ans)

### FIXED CODE ###

import collections
temp = 0
n = input()
li = list(map(int,input().split()))
c = collections.Counter(li)
c_items = list(c.items())
for j in c_items:
    temp += ((j[1] * (j[1]-1)) // 2)
for i in li:
    print(temp - (c[i]-1))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
num=0
for i in range(0,n):
    for j in range(max(i+1,a[i]+1),n):
        if a[i]+a[j]==j-i:
            num=num+1
print(num)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
tempi=[0]*n
tempj=[0]*n
for i in range(n):
  tempi[i]=a[i]+i+1
for i in range(n):
  tempj[i]=-a[i]+i+1
import collections
tempid=collections.Counter(tempi)
tempjd=collections.Counter(tempj)
for k in tempid.keys():
  a=tempid[k]
  b=tempjd[k]
  ans=ans+a*b
print(ans)
### BUGGY CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    for i in range(4):
        for j in range(1,k+1):
            nx = x+dx[i]*j
            ny = y+dy[i]*j
            if(not 0<=nx<h):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]<=cost+1):
                continue
            costgrid[nx][ny]=min(costgrid[nx][ny],cost+1)
            heapq.heappush(q,(cost+1,nx,ny))
            if nx==gx and ny==gy:
                ans=min(costgrid[nx][ny],ans)
                q=[]

if ans!=INF:
    print(ans)
else:
    print(-1)



### FIXED CODE ###

h,w,k = map(int, input().split())
sx,sy,gx,gy = map(int, input().split())
sx-=1
sy-=1
gx-=1
gy-=1

grid = ['' for _ in range(h)]

for i in range(h):
    grid[i] = input()
INF = 1001001001  
costgrid = [[INF]*w for _ in range(h)]

import heapq

q = []
q.append((0,sx,sy))

dx = (0,1,0,-1)
dy = (1,0,-1,0)
ans=INF
while q:
    cost,x,y = heapq.heappop(q)
    for i in range(4):
        for j in range(1,k+1):
            nx = x+dx[i]*j
            ny = y+dy[i]*j
            if(not 0<=nx<h):
                break
            if(not 0<=ny<w):
                break
            if(grid[nx][ny]=='@'):
                break
            if(costgrid[nx][ny]<=cost):
                break
            if(costgrid[nx][ny]>cost+1):
                costgrid[nx][ny]=cost+1
                heapq.heappush(q,(cost+1,nx,ny))
                if nx==gx and ny==gy:
                    ans=min(costgrid[nx][ny],ans)
                    q=[]

if ans!=INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	r,c,k=MI()
	G=[[0]*(c+1) for _ in range(r+1)]
	dp=[[[0]*4 for i in range(c+1)] for j in range(r+1)]
	for _ in range(k):
		rrr,ccc,v=MI()
		G[rrr][ccc]=v
	#print(G)

	#print(dp)

	for rr in range(1,r+1):
		for cc in range(1,c+1):
			if G[rr][cc]==0:
				for i in range(4):
					dp[rr][cc][i]=max(dp[rr][cc-1][i],dp[rr-1][cc][3])
			else:
				dp[rr][cc][0]=max(dp[rr-1][cc][3],dp[rr][cc-1][0])
				dp[rr][cc][1]=max(dp[rr][cc][0]+G[rr][cc],dp[rr][cc-1][1])
				dp[rr][cc][2]=max(dp[rr][cc-1][1]+G[rr][cc],dp[rr][cc-1][2],dp[rr][cc][1])
				dp[rr][cc][3]=max(dp[rr][cc-1][2]+G[rr][cc],dp[rr][cc-1][3],dp[rr][cc][2])
	#print(dp)
	print(dp[-1][-1][-1])















if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	r,c,k=MI()
	G=[[0]*(c+1) for _ in range(r+1)]
	dp=[[[0]*(c+1) for i in range(r+1)] for j in range(4)]
	for _ in range(k):
		rrr,ccc,v=MI()
		G[rrr][ccc]=v
	#print(G)

	#print(dp)

	for rr in range(1,r+1):
		for cc in range(1,c+1):
			if G[rr][cc]==0:
				for i in range(4):
					dp[i][rr][cc]=max(dp[i][rr][cc-1],dp[3][rr-1][cc])
			else:
				dp[0][rr][cc]=max(dp[3][rr-1][cc],dp[0][rr][cc-1])
				dp[1][rr][cc]=max(dp[0][rr][cc]+G[rr][cc],dp[1][rr][cc-1])
				dp[2][rr][cc]=max(dp[1][rr][cc-1]+G[rr][cc],dp[2][rr][cc-1],dp[1][rr][cc])
				dp[3][rr][cc]=max(dp[2][rr][cc-1]+G[rr][cc],dp[3][rr][cc-1],dp[2][rr][cc])
	#print(dp)
	print(dp[-1][-1][-1])















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

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1
#print(sushi)

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[-1.0 for _ in range(N+1)] for _ in range(sushi[2]+sushi[1]+1)] for _ in range(sushi[2]+1)] # 型推論で時間がかからないように-1ではなく-1.0とする。

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return res

print(rec(sushi[2],sushi[1],sushi[0]))


### FIXED CODE ###

# 再帰関数を使うとTLEになるので、3重ループにしてみる。
from collections import defaultdict

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)] # 型推論で時間がかからないように0ではなく0.0とする。

for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if i+j+k > N or i+j+k == 0:
        continue
      if i>0:
        dp[i][j][k] += i * dp[i-1][j+1][k]
      if j>0:
        dp[i][j][k] += j * dp[i][j-1][k+1]
      if k>0:
        dp[i][j][k] += k * dp[i][j][k-1]
      dp[i][j][k] += N
      dp[i][j][k] /= (i+j+k)

print(dp[sushi[2]][sushi[1]][sushi[0]])
### BUGGY CODE ###

N, Y = map(int, input().split())
ans = [-1,  -1,  -1]
for x in range(N+1):
    for y in range(N+1):
        for z in range(N+1):
            if 10000*x + 5000*y + 1000*z == Y and (x+y+z) == N:
                ans = [x, y, z]
                break
print(*ans)

### FIXED CODE ###

N, Y = map(int, input().split())
ans = [-1,  -1,  -1]
for x in range(N+1):
    for y in range(N+1):
        z = N - (x+y)
        if 10000*x + 5000*y + 1000*z == Y and (0<= z <= N):
            ans = [x, y, z]
            break
print(*ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def LI():return list(map(int,input().split()))
def yes():print("YES")
def no():print("NO")
import time
t1=time.time()
n,k=LI()
a=LI()

if k>=n:
    ans=[n]*n
    print(*ans)
    exit()


for _ in range(k):
    b=[0]*n
    for i in range(n):
        q=a[i]
        for j in range(i-q,i+q+1):
            if 0<=j<=n-1:
                b[j]+=1
    a=b[:]
    t2=time.time()
    if t2-t1>1800:
        print(*a)
        exit()
print(*a)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import time
t1=time.time()
def LI():return list(map(int,input().split()))
n,k=LI()
a=LI()

for _ in range(k):
    tab=[0]*(n)
    for i in range(n):
        q=a[i]
        if 0<=i-q:
            tab[i-q]+=1
        else:
            tab[0]+=1
        if i+q+1<=n-1:
            tab[i+q+1]-=1
        else:
            pass
    b=[tab[0]]
    for i in range(n-1):
        b.append(tab[i+1]+b[-1])
    a=b[:]
    if time.time()-t1>1.5:
        print(*a)
        exit()
print(*a)