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

import sys
import copy

N = int(input())
b = [int(b) for b in input().split()]
h = {}

def f(b):
  key = "".join([str(x) for x in b])
  if key in h:
    return copy.copy(h[key])
  
  if len(b) == 1:
    h[key] = b if b[0] == 1 else []
    return copy.copy(h[key])
  
  for i in range(len(b)):
    i = len(b) - 1 - i
    if b[i] == i + 1:
      b_sub = copy.copy(b)
      b_i = b_sub.pop(i)
      a = f(b_sub)
      if len(a) != 0:
        a.append(b_i)
        h[key] = a
        return copy.copy(h[key])
  
  h[key] = []
  return copy.copy(h[key])

a = f(b)
if len(a) == 0:
  print(-1)
else:
  for i in range(N):
    print(a[i])

### FIXED CODE ###

import sys
import time
import copy

N = int(input())
b = [int(b) for b in input().split()]
h = {}

t1 = time.time()

def f(b):
  t2 = time.time()
  if t2 - t1 > 1.5:
    print(-1)
    sys.exit()
  
  key = "".join([str(x) for x in b])
  if key in h:
    return copy.copy(h[key])
  
  if len(b) == 1:
    h[key] = b if b[0] == 1 else []
    return copy.copy(h[key])
  
  for i in range(len(b)):
    i = len(b) - 1 - i
    if b[i] == i + 1:
      b_sub = copy.copy(b)
      b_i = b_sub.pop(i)
      a = f(b_sub)
      if len(a) != 0:
        a.append(b_i)
        h[key] = a
        return copy.copy(h[key])
  
  h[key] = []
  return copy.copy(h[key])

a = f(b)
if len(a) == 0:
  print(-1)
else:
  for i in range(N):
    print(a[i])
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
for i in range(N):
  for j in range(i + 1, N):
    for k in range(j + 1, N):
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i] and j - i != k - j:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

r = 0
g = 0
b = 0
for s in S:
  if s == "R":
    r += 1
  if s == "G":
    g += 1
  if s == "B":
    b += 1
ans = r * g * b

for i in range(N):
  for j in range(i + 1, N):
    k = 2 * j - i
    if k >= N:
      continue
    if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      ans -= 1
print(ans)
### BUGGY CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(ls,x):
    num = 0
    for i in ls:
      y = x-i
      num += n-bisect.bisect_left(ls,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx) < m:
      rx = mx
    elif hsnum(a,mx) > m:
      if hsnum(a,mx+1) < m:
        error = hsnum(a,mx)-m
        lx = mx
        break
      lx = mx + 1
    else:
      lx = mx
      break
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i+suma[n]-suma[j]
  print(ans-error*lx)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)<m:
    lx -= 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

s=input()
t=input()

cs={}
for i,c in enumerate(s):
    cs[c] = cs.get(c,[])+[i]

ct={}
for i,c in enumerate(t):
    ct[c] = ct.get(c,[])+[i]

print('Yes' if sorted(list(ct.values()),key=lambda x:x[0])==sorted(list(cs.values()),key=lambda x:x[0]) else 'No')

### FIXED CODE ###

import collections

s=input()
t=input()

cs = collections.Counter(s)
ct = collections.Counter(t)

print('Yes' if sorted(list(ct.values()))==sorted(list(cs.values())) else 'No')
### BUGGY CODE ###

class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=sorted([tuple(map(int,input().split())) for i in range(n)])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort()
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

### FIXED CODE ###

class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

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

# 木構造をリストで表現する
G = [[] for _ in range(N+1)]

AB = [[int(x) for x in input().split()] for _ in range(N-1)]

for a, b in AB:
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
PX = [[int(x) for x in input().split()] for _ in range(Q)]

P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

n,m = map(int,input().split())
list_a = list(map(int,input().split()))
#b_list = list(map(int,input().split()))
#print(" ".join(map(str,c_list)))

for i in range(m):
    list_a.sort(reverse = True)
    list_a[0] = list_a[0] //2
    """
    if list_a[0] % 2 != 0:
        list_a[0] = list_a[0] // 2 - 1
    else:
        list_a[0] = list_a[0] // 2
    """
print(sum(list_a))

### FIXED CODE ###

import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
temp = 0
cnt = 0
fin = 0
loop = 0
debug = 0
temp2 = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
while debug < 10:
    loop = 0
    #temp2 = temp
    temp = 0
    lst_a.sort(reverse=True)
    while loop < n-1:
        lst_a[loop] //= 2
        cnt += 1
        temp = max(temp,lst_a[loop])
        if cnt == m:
            #print(lst_a)
            print(sum(lst_a))
            sys.exit()
        if temp > max(lst_a[loop],lst_a[loop + 1]):
            break
        if lst_a[loop + 1] > lst_a[loop]:
            loop += 1
        
        
        
"""        if lst_a[loop] >= max(lst_a[loop + 1],temp):
            lst_a[loop] //= 2
            temp = max(lst_a[loop],lst_a[loop+1])
            cnt += 1
            if cnt == m:
                print(sum(lst_a))
                sys.exit()
            if temp > lst_a[loop + 1]:
                break
            
            
        loop += 1
    
    #debug += 1
print(lst_a[99999])
# print(temp)
# print(cnt)
# print(lst_a)
# print(sum(lst_a))
"""
### BUGGY CODE ###

import sys

K = int(input())
a = 7
for i in range(K):
    if a % K == 0:
        print(i+1)
        sys.exit()
    a = 10 * a + 7
print(-1)

### FIXED CODE ###

K = int(input())
a = 7
for i in range(K):
    if a % K == 0:
        print(i+1)
        exit()
    a = (10 * a + 7) % K
print(-1)
### BUGGY CODE ###

s = int(input())
start = 1

x1, y1, x2, y2, x3, y3 = 0, 0, 0, 0, 0, 0

while True:
    if s >= 10e9:
        start = s//2

    for i in range(start, int(s**0.5)+1):
        if s % i == 0 and i <= 10e9 and s / i <= 10e9:
            x2 = i - x1
            y3 = s//i - y1
        break

    if x2 == 0 and y3 == 0:
        x1 += 1
        y1 += 1
        continue
    break

print(x1, y1, x2, y2, x3, y3)


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

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

su = s.count('1')
sun = int(s,2)


table = [0]*200001
table[1] = 1
for i in range(2,200001):
    table[i] = 1 + table[i % bin(i).count('1')]

def pow(n,e,mod):
    ret=1
    b=n
    while e > 0:
        if e % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        e = e//2
    return ret

for i in range(n):
    if s[i] == '0':
        print(1+table[(sun+pow(2,n-1-i,su+1))%(su+1)])
    else:
        if su-1 == 0:
            print(0)
        else:
            print(1+table[(sun-pow(2,n-1-i,su-1)+su-1)%(su-1)])


### FIXED CODE ###

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

su = s.count('1')
sun = int(s,2)

sun_plus = sun % (su + 1)
sun_minus = 0 if su - 1 == 0 else sun % (su - 1)


table = [0]*200001
table[1] = 1
for i in range(2,200001):
    table[i] = 1 + table[i % bin(i).count('1')]

def pow(n,e,mod):
    ret=1
    b=n
    while e > 0:
        if e % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        e = e//2
    return ret

for i in range(n):
    if s[i] == '0':
        print(1+table[(sun_plus+pow(2,n-1-i,su+1))%(su+1)])
    else:
        if su-1 == 0:
            print(0)
        else:
            print(1+table[(sun_minus-pow(2,n-1-i,su-1)+su-1)%(su-1)])
### BUGGY CODE ###

import heapq
def SME(start,end):
    count = 0
    ANS = [heapq.heappush(A,[x,i]) for i,x in enumerate(Whole)]
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.9998
ANS = SME(0, N)
for i in ANS[L-1:-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 ###

import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, e, s, t = MAP()
s-= 1
t-= 1    
G1 = [[]for i in range(n)]
G2 = [[]for i in range(n)]       

for i in range(e):
    fr, to, w1, w2 = MAP()
    G1[fr-1].append((w1, to -1))
    G1[to-1].append((w1, fr -1))
    G2[fr-1].append((w2, to -1))
    G2[to-1].append((w2, fr -1))


def djkstra(s,G):
    n = len(G)
    visited = [False]*n     
    d = [INF]*n
    que = []
    heapq.heapify(que)
    d[s] = 0
    visited[s] = True
    heapq.heappush(que, (0,s))

    while(len(que)>0):
        vs = heapq.heappop(que)
        distance = vs[0]
        vertex = vs[1]
        d[vertex] = min(d[vertex],distance)
        visited[vertex] = True
        for Gs in G[vertex]:
            if not visited[Gs[1]]:
                heapq.heappush(que,(d[vertex]+Gs[0], Gs[1]))
    return d

d_yen = djkstra(s,G1)
d_snuuk = djkstra(t,G2)

d_sum = [0]*n

for i in range(n):
    d_sum[i] = d_yen[i] + d_snuuk[i]

d_sum.reverse()
d_ans = [0]*n
d_ans[0] = d_sum[0]
for i in range(1,n):
    d_ans[i] = min(d_ans[i-1],d_sum[i])

for i in range(n-1,-1,-1):
    print(10**15 - d_ans[i])



### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n, e, s, t = MAP()
s-= 1
t-= 1    
G1 = [[]for i in range(n)]
G2 = [[]for i in range(n)]       

for i in range(e):
    fr, to, w1, w2 = MAP()
    G1[fr-1].append((w1, to -1))
    G1[to-1].append((w1, fr -1))
    G2[fr-1].append((w2, to -1))
    G2[to-1].append((w2, fr -1))


def djkstra(s,G):
    visited = [False]*n     #その頂点を確定したかどうか
    d = [INF]*n
    que = []
    heapq.heapify(que)
    heapq.heappush(que, (0,s))

    while(len(que)>0):
        vs = heapq.heappop(que)
        distance = vs[0]
        vertex = vs[1]
        if visited[vertex]:
            continue
        d[vertex] = distance
        visited[vertex] = True
        for Gs in G[vertex]:
            if d[Gs[1]] <= distance+Gs[0]:
                continue
            heapq.heappush(que,(distance+Gs[0], Gs[1]))
    
    return d

d_yen = djkstra(s,G1)
d_snuuk = djkstra(t,G2)

d_sum = [0]*n

for i in range(n):
    d_sum[i] = d_yen[i] + d_snuuk[i]

d_sum.reverse()
d_ans = [0]*n
d_ans[0] = d_sum[0]
for i in range(1,n):
    d_ans[i] = min(d_ans[i-1],d_sum[i])

for i in range(n-1,-1,-1):
    print(10**15 - d_ans[i])
### BUGGY CODE ###

n=int(input())

c=1
for i in range(1,n+1):
    c=c*i
print(c%(10**9+7))

### FIXED CODE ###

import math

n=int(input())

c=1*math.factorial(n)
print(c%(10**9+7))
### BUGGY CODE ###

s = input()
cnt = 0
while 'ABC' in s:
    cnt += s.count('ABC')
    s = s.replace('ABC', 'BCA')
print(cnt)

### FIXED CODE ###

"""Binary Indexed Tree (Fenwick Tree)"""
class BIT:
    def __init__(self, n):
        self.n = n
        
        #BIT木データ
        self.data = [0]*(n+1)
        
        #元配列
        self.el = [0]*(n+1)
    
    """A1~Aiまでの累積和"""
    def Sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            
            #LSB(Least Significant Bit)の獲得:i&(-i)
            i -= i & (-i) 
        return s
    
    """Ai += x"""
    def Add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    """Ai ~ Ajまでの累積和"""
    def Get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.Sum(j) - self.Sum(i)
    
s = input()
s = s.replace('BC', 'D')
mode = 0
res = 0
for i in range(len(s)):
    if s[i] == 'B' or s[i]=='C':
        mode = 0
    elif s[i] == 'A':
        mode += 1
    else:
        res += mode
print(res)
### BUGGY CODE ###

from collections import deque

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

edges = {}
ins = [0 for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    ins[b-1] += 1

# print(root.pop())

root = -1
for i in range(n):
    if ins[i] == 0:
        root = i+1
        break
que = deque()
que.append(root)
parent = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
    else:
        nex = []
    for n in nex:
        parent[n-1] = p
        que.append(n)
    if len(que) == 0:
        break

for p in parent:
    print(p)



### FIXED CODE ###

from collections import deque

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

edges = {}
ins = [0 for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    ins[b-1] += 1

# print(root.pop())

root = -1
for i in range(n):
    if ins[i] == 0:
        root = i+1
        break
que = deque()
que.append(root)
parent = [0 for i in range(n)]
pbuf = [[] for i in range(n)]
counts = [0 for i in range(n)]
while True:
    p = que.popleft()
    if p in edges:
        nex = edges[p]
        edges.pop(p)
    else:
        nex = []
    for n in nex:
        counts[n-1] += 1
        if counts[n-1] == ins[n-1]:
            parent[n-1] = p
            que.append(n)
    if len(que) == 0:
        break

for p in parent:
    print(p)
### BUGGY CODE ###

#2
n = int(input())
m=0
for i in range(1,n+1) :
    for j in range(1,i+1) :
        if j**2==i :
            m=i    
print(m)

### FIXED CODE ###

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

X=int(input())

Xkon=X**0.2
if(Xkon==int(Xkon)):
    print(str(0)+" "+str(int(-Xkon)))
    #break
else:
    n=1
    while n<10**5:
        A=X+(n**5)
        check=(A**0.2)
        if(check==int(check)):
            AnsA=check
            AnsB=n
            print(str(int(AnsB)+" "+str(int(-AnsA))))
            break
        else:
            n=n+1
    m=-(10**5)
    while m<0:
        A=X+(m**5)
        check=(A**0.2)
        # print(type(check))
        if(type(check)!=complex):
            if(check==int(check)):
                AnsA=-check
                AnsB=-m
                print(str(int(AnsB))+" "+str(int(AnsA)))
                break
            else:
                pass
        else:
            m=m+1

### FIXED CODE ###

X=int(input())

for A in range(-1000,1000):
    for B in range (-1000,1000):
        if(A**5-B**5==X):
            print(A,B)
            break
    else:
        continue
    break
### BUGGY CODE ###

import numpy as np
n,l=int(input()),list(map(float,input().split()))
dp=np.full([n+1,n+1],0.0)
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[n][(n+1)//2:]))


### FIXED CODE ###

n,l=int(input()),list(map(float,input().split()))
dp=[[0.0]*(n+1) for _ in range(n+1)]
dp[0][0]=1.0
for i in range(1,n+1):
    for j in range(i+1):
        if j==0:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])
        else:
            dp[i][j]=dp[i-1][j]*(1.0-l[i-1])+dp[i-1][j-1]*l[i-1]
print(sum(dp[n][((n+1)//2):]))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def bfs(H, W, black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d


def main():
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]

    black_cells = deque()
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                black_cells.append((h, w))
                dist[h][w] = 0
    print(bfs(H, W, black_cells, dist))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
def input(): return sys.stdin.readline().rstrip()


def bfs(H, W, black_cells, dist):
    d = 0
    while black_cells:
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d


def main():
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]

    black_cells = deque()
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                black_cells.append((h, w))
                dist[h][w] = 0
    print(bfs(H, W, black_cells, dist))


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

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

cnt = 0

while True:
    has_divided = False
    for i in range(N):
        if not has_divided and a[i] % 2 == 0:
            a[i] = a[i] // 2
            has_divided = True
        else:
            a[i] *= 3
    if has_divided:
        cnt += 1
    else:
        break
print(cnt)


### FIXED CODE ###

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

cnt = 0

for i in range(N):
    while True:
        if a[i] % 2 == 0:
            a[i] //= 2
            cnt += 1
        else:
            break
print(cnt)