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

import copy

h, w = map(int, input().split())

grid = [[False] * (w + 2)]
for _ in range(h):
    grid.append([False] + [x == '#' for x in input()] + [False])
grid.append([False] * (w + 2))

cnt = 0
while True:
    flag = True
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            # print('#' if grid[i][j] else '.', end='')
            if grid[i][j] is False:
                flag = False
        # print()
    if flag:
        break

    new_grid = copy.deepcopy(grid)
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] is False:
                if grid[i + 1][j] or grid[i][j + 1] or grid[i - 1][j] or grid[i][j - 1]:
                    new_grid[i][j] = True
    grid = new_grid
    cnt += 1

print(cnt)


### FIXED CODE ###

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

print(cnt - 1)
### BUGGY CODE ###

n = int(input())
s = list(input())
s = [ord(i)-97 for i in s]

dic = {}
for i in range(26):
    dic[i] = []

for i in range(n):
    dic[s[i]].append(i)

for i in range(26):
    dic[i].append(float('inf'))

from bisect import bisect_left
q = int(input())
for i in range(q):
    x, y, z = input().split()
    if x == '1':
        y, z = int(y) - 1, ord(z) - 97
        p = bisect_left(dic[s[y]], y)
        dic[s[y]].pop(p)
        dic[z].insert(bisect_left(dic[z], y), y)
        s[y] = z
    else:
        res = 0
        y, z = int(y) - 1, int(z) - 1
        for i in range(26):
            p = dic[i][bisect_left(dic[i], y)]
            if p <= z:
                res += 1
        print(res)

### FIXED CODE ###

n = int(input())
s = list(input())

dic = {}
for i in range(26):
    dic[chr(i+97)] = []

for i in range(n):
    dic[s[i]].append(i)

for i in range(26):
    dic[chr(i+97)].append(float('inf'))

from bisect import bisect_left
q = int(input())
for i in range(q):
    x, y, z = input().split()
    if x == '1':
        y = int(y) - 1
        p = bisect_left(dic[s[y]], y)
        dic[s[y]].pop(p)
        dic[z].insert(bisect_left(dic[z], y), y)
        s[y] = z
    else:
        res = 0
        y, z = int(y) - 1, int(z) - 1
        for i in range(26):
            p = dic[chr(i+97)][bisect_left(dic[chr(i+97)], y)]
            if p <= z:
                res += 1
        print(res)
### BUGGY CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    count = 0
    kitai = [0]*n

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n - k + 1):

        count = sum(kitai[i:i+k])
 #       for w in range(i , i + k):
#            count += kitai[w]
#            count += tasu(p[w]) / p[w]
        ans = max(ans , count)

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def tasu(x):
    return x / 2 * (x + 1)

def kitaiti(n , k , p):

    ans = 0
    count = 0
    kitai = [0]*n
    kitaisum = [0]*n
    mod = 10**9+7

    for i in range(n):
        kitai[i] = tasu(p[i]) / p[i]

    for i in range(n):
        if i == 0:
            kitaisum[i] += kitai[i]
        else:
            kitaisum[i] += kitai[i] + kitaisum[i-1]

    for i in range(n - k + 1):

        ans = max(ans , (kitaisum[i + k - 1] - kitaisum[i-1]) if i != 0 else kitaisum[i + k - 1])

    return ans

def main():
    n , k = map(int , input().split())
    p = list(map(int,input().split()))
    print(kitaiti(n , k , p))

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

n,k,q=map(int,input().split())
a=[int(input()) for _ in range(q)]
a=tuple(a)
for i in range(1,n+1):
  if a.count(i)>q-k:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[]
for i in range(n):
  a.append(k-q)
for i in range(q):
  a[int(input())-1]+=1
for i in range(n):
  print('Yes' if a[i]>0 else 'No')
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
tot = []
for i in range(X):
   for j in range(Y):
      for k in range(Z):
         tot.append(a[i] + b[j] + c[k])
tot.sort()
for i in range(K):
   print(tot[-(i+1)])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
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)
tot = []
for i in range(X):
   for j in range(Y):
      for k in range(Z):
         if((i+1)*(j+1)*(k+1) <= K): tot.append(a[i] + b[j] + c[k])
         else: break
tot.sort(reverse = True)
for i in range(K):print(tot[i])
### BUGGY CODE ###

N, P = map(int, input().split())
S = list(input())
mod = P
dp = [[0 for i in range(N-j)] for j in range(N)]
dp
for j in range(N):
    dp[j][0]=(int(S[j])%mod)
    for i in range(1,N-j):
        dp[j][i]=((dp[j][i-1]*10+int(S[j+i]))%mod)
ans = 0
for i in range(N):
    ans += dp[i].count(0)
    
print(ans)

### FIXED CODE ###

from collections import Counter

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

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))
### BUGGY CODE ###

import heapq
S = input()
cum = []
dict = {}
for i in range(len(S)):
    n = int(S[i:])
    cum.append(n % 2019)
    dict[n % 2019] = 0


for c in cum:
    dict[c] += 1
ans = 0
for k, v in dict.items():
    if k == 0:
        ans += v
    ans += v * (v-1) // 2

print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


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

import networkx as nx
n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
G.add_edges_from(zip(AB[::2], AB[1::2]))
print('Yes')
T = nx.bfs_tree(G, 1)
for i in range(2, n+1):
    print(*T.predecessors(i))

### FIXED CODE ###

from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')
### BUGGY CODE ###

from fractions import *
_,a=open(0)
*a,=map(int,a.split())
mod=10**9+7
b=1
for i in a:
    b*=i//gcd(b,i)
print(sum(b//i%mod for i in a)%mod) 

### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

n,w = map(int,input().split())
box = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i in range(1,n+1):
  for j in range(w+1):
    if j >= box[i-1][0]:
      dp[i][j] = max(dp[i-1][j-box[i-1][0]] + box[i-1][1] ,dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[n][w])

### FIXED CODE ###

n,w = map(int,input().split())
box = []
for i in range(n):
  W,V = map(int,input().split())
  box.append([W,V])
dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i in range(1,n+1):
  for j in range(w+1):
    if j >= box[i-1][0]:
      dp[i][j] = max(dp[i-1][j-box[i-1][0]] + box[i-1][1] ,dp[i-1][j])
    else:
      dp[i][j] = dp[i-1][j]
print(dp[n][w])
### BUGGY CODE ###

def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    S = input().strip()
    Sn = np.array([int(x) for x in S])
    N = len(S)
    ans = 0
    T = Sn.cumsum()
    if N < 4:
        print(0)
        exit()
    for i in range(N-3):
        # print('i = {}'.format(i))
        NT = len(T)
        for j in range(3, NT):
            # print('  j = {}'.format(j))
            if T[j] % 3 == 0:
                if int(S[i:i+j+1]) % 2019 == 0:
                    # print(S[i:i+j+1])
                    ans += 1

        T = T[1:] - T[0]

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import Counter
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    S = [int(x) for x in input().strip()]
    N = len(S)
    ans = 0
    l = [0] * (N + 1)
    p = 1
    cumsum = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        l[i] = (S[i] * p) % 2019
        p *= 10
        p %= 2019
    for i in range(N-1, -1, -1):
        cumsum[i] = (l[i] + cumsum[i+1]) % 2019
    cumsum = Counter(cumsum)
    for i in range(0, 2019):
        ans += (cumsum[i] * (cumsum[i] - 1)) // 2

    print(ans)

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

import sys
input = sys.stdin.readline

def main():
	N = int(input())
	a = list(map(int,input().split()))
	ball = []
	ballNum = 0
	f = [0]*N

	for i in reversed(range(N)):
		if (sum(filter(lambda x: x % (i+1) == 0, f)) % 2) != (a[i] % 2):
			f[i] = 1
			ball.append(i+1)
			ballNum +=1

	print(ballNum)
	print(*ball)

if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sumN(n,N,f):
	total = 0
	i = n
	while i < N:
		total += f[i]
		i += n+1

	if total % 2:
		return 1
	else:
		return 0

def main():
	N = int(input())
	a = list(map(int,input().split()))
	ball = []
	ballNum = 0
	f = [0]*N

	for i in reversed(range(1,N)):
		if sumN(i,N,f) != (a[i] % 2):
			f[i] = 1
			ball.append(i+1)
			ballNum +=1

	if (sum(f) % 2) != (a[0] % 2):
		f[0] = 1
		ball.append(1)
		ballNum +=1

	print(ballNum)
	print(*ball)

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

from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    a=inplm(n)
    aa=[-1 for _ in range(10**5)]
    index=0
    for i in range(n):
        for j in range(10**5):
            if a[i]>aa[j]:
                aa[j]=a[i]
                if index<j:
                    index=j
                break
    print(index+1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if index == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(LIS(a))

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

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

class Member:
    def __init__(self, answer, point):
        self.answer = answer
        self.point = point
    def judge(self):
        if self.point <= 0:
            return 'No'
        else:
            return 'Yes'
        
members = [Member(a.count(i+1), k)
                  for i in range(n)]


for member in members:
    member.point = member.point - q + member.answer
    print(member.judge())

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]
p = [k for i in range(n)]
def judge(x):
    if p[x] - q <= 0:
        return 'No'
    else:
        return 'Yes'
for i in range(q):
    p[a[i] - 1] += 1
b = [judge(i) for i in range(n)]
print('\n'.join(b))
### BUGGY CODE ###

N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
ans=H[K-1]-H[0]
for i in range(N-K+1):
  A=H[i:i+K]
  if ans>A[K-1]-A[0]:
    ans=A[K-1]-A[0]
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
H=[]
for i in range(N):
  H.append(int(input()))
H.sort()
print(min(H[i+K-1]-H[i] for i in range(N-K+1)))
### BUGGY CODE ###

#C
L, R = list(map(int, input().split()))
if (R - L) == 2019:
    result = 0
else:
    result = 2018
    for i in range(L,R+1):
        for s in range(i+1,R+1):
            x = (i*s)%2019
            if x == 0:
                result = 0
            if result > x:
                result = x
print(result)

### FIXED CODE ###

#C
import sys
L, R = list(map(int, input().split()))
if (R - L) == 2019:
    result = 0
else:
    result = 2018
    for i in range(L,R+1):
        for s in range(i+1,R+1):
            x = (i*s)%2019
            if x == 0:
                result = 0
                print(0)
                sys.exit()
            elif result > x:
                result = x
print(result)
### BUGGY CODE ###

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

ans = 0
for i in range(2000):
    if ans != 0:
        break
    else:
        for j in range(2000-i):
            for k in range(2000-(i + j)):
                if (i + k + j)== n and (10000*i + 5000*j + 1000*k) == y:
                    print(i,j,k)
                    ans +=1
                else:
                    continue
                
if ans == 0:
    print('-1','-1','-1')

### FIXED CODE ###

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

ans = 0
for i in range(2001):
    if ans != 0:
        break
    else:
        for j in range(2001-i):
            if (10000*i + 5000*j + 1000*(n-(i + j))) == y and ((n-(i + j)) >=0):       
                print(i,j,n-(i + j))
                ans +=1
            else:
                continue
                
if ans == 0:
    print('-1','-1','-1')
### BUGGY CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
li = list(map(lambda x:(x+1)/2,li))
wk = 0
kai = []
nn = n-k+1

for y in range(nn):
    wk = 0
    for x in range(y,k+y):
        wk = wk + li[x]
    kai.append(wk)
 
print(max(kai))

### FIXED CODE ###

n,k = map(int,input().split())
li = list(map(int,input().split()))
li = list(map(lambda x:(x+1)/2,li))

wk = 0
nn = n-k

for i in range(0,k):
    wk += li[i]
kwk = wk
for j in range(nn):
    wk = wk - li[j]
    wk = wk + li[j+k]
    kwk = max(wk,kwk)
 
print(kwk)
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)

parent = {i:-1 for i in range(1,n+1)}
parent[1] = 0
q = [1]
while len(q):
    u = q[0]
    q.pop(0)
    for v in graph[u]:
        if parent[v] == -1:
            q.append(v)
            parent[v] = u

if -1 in list(parent.values()):
    print("No")
    exit()
print("Yes")
for i in range(2,n+1):
    print(parent[i])







### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)

parent = {i:-1 for i in range(1,n+1)}
parent[1] = 0
q = [1]
while len(q):
    u = q.pop(0)
    for v in graph[u]:
        if parent[v] == -1:
            q.append(v)
            parent[v] = u

if -1 in list(parent.values()):
    print("No")
    exit()
print("Yes")
for i in range(2,n+1):
    print(parent[i])
### BUGGY CODE ###

import collections


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(m):
        b, c = map(int, input().split())
        A = A + [c] * b
        if i % 100 == 99:
            A = sorted(A, reverse=True)[0:n]
    print(sum(sorted(A, reverse=True)[0:n]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    bc = [list(map(int, input().split())) for _ in range(m)]
    A.sort()
    bc.sort(key=lambda x: x[1], reverse=True)
    i, j = 0, 0

    while i < n and j < m:
        if A[i] >= bc[j][1]:
            break
        A[i] = bc[j][1]
        i += 1
        bc[j][0] -= 1
        if bc[j][0] == 0:
            j += 1
    print(sum(A))


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

N, K = map(int, input().split())
P = list(map(int, input().split()))
kitai = [(0.5*i*(i+1))/i for i in range(1, 1001)]

ans = 0
ans_list=[]
for i in range(0, N-K+1):
    temp = P[i:i+K]
    temp2 = sum(temp)
    if ans < temp2:
        ans = temp2
        ans_list = temp

ans = 0
for al in ans_list:
    ans += kitai[al-1]
print(ans)


### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
P = list(map(int, input().split()))

kitai = [None]*(1001)
for i in range(1, 1001):
    kitai[i] = (0.5*i*(i+1))/i

ruiseki = P.copy()
ruiseki[K-1] = sum(ruiseki[0:K])
for i in range(K, N):
    ruiseki[i] = ruiseki[i-1]+P[i]-P[i-K]

ind = np.array(ruiseki).argmax()
temp = P[ind-K+1:ind+1]
ans = 0
for t in temp:
    ans+=kitai[t]
print(ans)
### BUGGY CODE ###

import sys

def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  cur = N
  for i in range(N):
    j = i + 1
    s = A[i]
    while j < N:
      if s & A[j] == 0:
        cur += 1
        s += A[j]
        j += 1
      else:
        break
  print(cur)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  
  a = 0
  s = A[0]
  cur = 0
  right = 1
  for left in range(N):
    while right < N and s & A[right] == 0:
      s += A[right]
      right += 1
    cur += right - left
    s -= A[left]

  print(cur)


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

from collections import*
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=deque([a:=~w+a*w+b])
d[a]=1
while q:
 s=q.popleft()
 for x in 0,1,2,3:
  for z in range(k):
   y=0,z+1,0,~z;i,j=s//w+y[x],s%w+y[~x];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = 0
def nibutan(d):
    if len(d)==n:
        global ans
        x = y = 0
        for i in range(n):
            if d[i]==1:
                x += v[i]
                y += c[i]
        ans = max(ans,x-y)
    else:
        nibutan(d+[1])
        nibutan(d+[0])
nibutan([])
print(ans)



### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split()))
x = y = 0
for i in range(n):
    if v[i]>c[i]:
        x += v[i]
        y += c[i]
print(x-y)
### BUGGY CODE ###

import sys
import copy
n=int(input())
maxmatch=n*(n-1)
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
day=0

match=[0]*(n+1)
jyunban=[i for i in range(n)]
jyunban_n=[]

while match[n]<maxmatch:
  jyunban_n.clear()
  day+=1
  check=[True]*(n+1)
  for i in jyunban:
    if match[i]==n-1 or check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs]:
        if  a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
          match[i]+=1
          match[vs]+=1
          match[n]+=2
          check[i]=False
          check[vs]=False
          check[n]=False
          jyunban_n.append(i)
          jyunban_n.append(vs)
      
    if len(jyunban)==0:
      if check[n]:
        print(-1)
        sys.exit()
  jyunban=copy.copy(jyunban_n)
        
print(day)


### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

N = int(input())
P = [float(i) for i in input().split()]

dp = [[0.0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1.0

for i, p in enumerate(P, 1):
    for j in range(N + 1):
        dp[i][j] = p * dp[i - 1][j - 1] + (1 - p) * dp[i - 1][j]

print(sum(dp[N][-(-N // 2):]))

### FIXED CODE ###

N = int(input())
P = [float(i) for i in input().split()]

dp = [[0.0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1.0

for i, p in enumerate(P, 1):
    for j in range(N + 1):
        dp[i][j] = p * dp[i - 1][j - 1] + (1 - p) * dp[i - 1][j]

print(sum(dp[N][-(-N // 2):]))