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

from queue import Queue

N, M = [int(n) for n in input().split()]
graph = {n: [] for n in range(1, N+1)}
for m in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].append(B)
    graph[B].append(A)

starts_ = sorted(graph.keys(), key=lambda x: len(graph[x]))
starts = iter([starts_[n:n+3] for n in range(0, len(starts_), 3)])

result_path = []
for start in starts:
    q = Queue()
    #needs_start = graph[start]
    for s in start:
        q.put([s])
    while not q.empty():
        path = q.get()            
        for i, t in enumerate(graph[path[-1]]):
            if t in path:
                continue
            if len(set(graph[path[0]] + graph[t]) - set(path + [t])) == 0:
                result_path = path + [t]
                q = Queue()
                break
            else:
                if len(path + [t]) < N:
                    q.put(path+[t])
                break
                
    if len(result_path) > 0:
        break
print(len(result_path))
result = ""
for r in result_path:
    result += " {}".format(r)
print(result[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
def inpl(): return map(int, input().split())

N, M = inpl()
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

searched = [False] * (N+1)

m = 1
searched[m] = True

ans = []
def dfs(c):
    global ans
    searched[c] = True
    for d in G[c]:
        if not searched[d]:
            ans.append(c)
            dfs(d)
            break 
    else:
        ans.append(c)
    
dfs(1)
ans = ans[:0:-1]
dfs(1)

print(len(ans))
print(*ans)
### BUGGY CODE ###

import math
from functools import reduce

k = int(input())

ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            ans += reduce(math.gcd, [a, b, c])

print(ans)

### FIXED CODE ###

import math

K = int(input())
ans = 0

for i in range(1,K+1):
  for j in range(1,K+1):
    ij = math.gcd(i, j)
    for k in range(1,K+1):
      ans += math.gcd(ij, k)

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

N,M,Q = [int(i) for i in input().split()]
LR = [[int(i) for i in input().split()] for _ in range(M)]
QList = [[int(i) for i in input().split()] for _ in range(Q)]
count = {i:0 for i in range(1,Q+1)}
qnum = 0

for ql,qr in QList:
    qnum += 1
    for l,r in LR:
        if ql <= l and r <= qr:
            count[qnum] += 1
for i in count.values():
    print(i)

### FIXED CODE ###

import numpy as np

N,M,Q = [int(i) for i in input().split()]
T = [[0]*(N+1)]*(N+1)
T=np.array(T)

for _ in range(M):
    l, r = map(int, input().split())
    T[l][r] += 1

np.cumsum(T, axis=0, out=T)
np.cumsum(T, axis=1, out=T)
data = T.tolist()

for _ in range(Q):
    ql, qr = [int(i) for i in input().split()]
    answer = data[qr][qr] - data[qr][ql-1] +  data[ql-1][ql-1] - data[ql-1][qr]
    print(answer)
### BUGGY CODE ###

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

m = 10 ** 9 + 7

sum = 0

for i in range(n):
  for j in range(i+1, n):
    sum += a[i] * a[j]
    sum %= m

print(sum)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = 10 ** 9 + 7
s = sum(a) % m


sum = 0

for i in range(n):
  s -= a[i]
  if s < 0:
    s += m
  sum += a[i] * s
  sum %= m

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

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
A = set(list(map(int,readline().split())))

dic = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

# たとえば2と3を両方作れるときに、2を作るメリットはない。
if 2 in A and 3 in A:
  A.remove(2)
if 2 in A and 5 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 6 in A and 9 in A:
  A.remove(6)

# ある本数を使ったときに、作った桁数が大きいほうが有利
# 使った本数でダイクストラ

dp = [-1] * (N + 1)
dp[0] = 0
import heapq
# 使った本数, 作った数(最後に降順に並べ替える)
q = [(0,"")]
heapq.heapify(q)
while q:
  used, num = heapq.heappop(q)
  #print("used",used,"num",num)
  if used > N:
    continue
  #print("num",num)
  if num == "":
    num = 0
  else:
    num = int("".join(sorted(num,reverse = True)))
  if dp[used] > num:
    # すでに作った数より桁数が小さい
    continue
  dp[used] = num
  if used == N:
    continue
  for a in A:
    if num == 0:
      numstr = ""
    else:
      numstr = str(num)
    heapq.heappush(q,(used + dic[a],numstr + str(a)))

print(dp[N])

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
A = set(list(map(int,readline().split())))

dic = {1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

# ある本数で作れる数
candi = [[],[],[1],[7],[4],[2,3,5],[6,9],[8]]

# たとえば2と3を両方作れるときに、2を作るメリットはない。
if 2 in A and 3 in A:
  A.remove(2)
if 2 in A and 5 in A:
  A.remove(2)
if 3 in A and 5 in A:
  A.remove(3)
if 6 in A and 9 in A:
  A.remove(6)

for i in range(len(candi)):
  for j in range(len(candi[i])-1,-1,-1):
    if candi[i][j] not in A:
      del candi[i][j]

# マッチをある本数使って作れる桁数の最大値をdp
# そのときの使用文字も記録
# 最大値が同じときは、大小比較
dp = [-1] * (N + 1)
ans = [""] * (N + 1)
dp[0] = 0
def to_num(x):
  return int("".join(sorted(x, reverse = True)))
for i in range(len(candi)):
  if not candi[i]:
    continue
  num = str(candi[i][0]) # i文字使って作る文字
  # i文字使って作る
  for j in range(len(dp)):
    if dp[j] == -1:
      continue
    #print("j",j)
    if j + i > N:
      continue
    if dp[j + i] < dp[j] + 1:
      dp[j + i] = dp[j] + 1
      ans[j + i] = ans[j] + num
    elif dp[j + i] == dp[j] + 1:
      if to_num(ans[j + i]) < to_num(ans[j] + num):
        ans[j + i] = ans[j] + num
    #print(dp)
    #print(ans)

print(to_num(ans[N]))
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
dp = [[None] * 10**6 for _ in range(n)]

def solve(idx, cost):
    if dp[idx][cost] is not None:
        return dp[idx][cost]

    if idx == n - 1:
        return cost

    if idx == n - 2:
        return solve(idx + 1, cost + abs(h[idx] - h[idx+1]))

    c1 = solve(idx + 1, cost + abs(h[idx] - h[idx + 1]))
    c2 = solve(idx + 2, cost + abs(h[idx] - h[idx + 2]))

    dp[idx][cost] = min(c1, c2)
    return dp[idx][cost]

    # return min(c1, c2)

ans = solve(0, 0)

print(ans)

### FIXED CODE ###

n = int(input())
hs = list(map(int, input().split()))
dp = [0]*n

# cost1 = dp[i-1] + abs(dp[i-1]-dp[i])
# cost2 = dp[i-2] + abs(dp[i-2]-dp[i])
# dp[i] = min(cost1, cost2)

#for i in reversed(range(n)):
for i in range(n):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(hs[0]-hs[1])
    else:
        cost1 = dp[i-1] + abs(hs[i-1]-hs[i])
        cost2 = dp[i-2] + abs(hs[i-2]-hs[i])
        dp[i] = min(cost1, cost2)

print(dp[n-1])
### BUGGY CODE ###

K=int(input())
ans=set()
for i in range(1,10):
    ans.add(i)
def saiki(A):
    genzai_saigo=int(A[-1])
    ketasu=len(A)
    if ketasu>0:
        B="".join(A)
        ans.add(eval(B))
    if ketasu==10:
        return
    for i in [genzai_saigo-1,genzai_saigo,genzai_saigo+1]:
        if i < 0 or i>9:
            continue
        A.append(str(i))
        saiki(A)
        A.pop()
for i in range(1,10):
    saiki([str(i)])
kotae=list(ans)
kotae.sort()
print(kotae[K-1])

### FIXED CODE ###

K=int(input())
ans=set()
for i in range(1,10):
    ans.add(i)
def saiki(A):
    genzai_saigo=int(A[-1])
    ketasu=len(A)
    if ketasu>0:
        B="".join(A)
        ans.add(eval(B))
    if ketasu==10:
        return
    for i in [genzai_saigo-1,genzai_saigo,genzai_saigo+1]:
        if i < 0 or i>9:
            continue
        A.append(str(i))
        saiki(A)
        A.pop()
for i in range(1,10):
    saiki([str(i)])
kotae=list(ans)
kotae.sort()
print(kotae[K-1])
### BUGGY CODE ###

# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m = na()
    path = [[] for _ in range(n)]
    ans = [0 for i in range(n)]
    check = [1]+[0 for _ in range(n-1)]
    for _ in range(m):
        a,b = na()
        a -= 1
        b -= 1
        path[a] += [b]
        path[b] += [a]
    que = [0]
    while que != []:
        now = que.pop(0)
        for nxt in path[now]:
            if check[nxt] == 0:
                ans[nxt] = now
                check[nxt] = 1
                que.append(nxt)
    if sum(check) == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')
    return


if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8
import sys
from collections import deque

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    n,m = na()
    path = [[] for _ in range(n)]
    ans = [0] + [-1 for i in range(n-1)]
    sumcheck = 1
    for _ in range(m):
        a,b = na()
        a -= 1
        b -= 1
        path[a] += [b]
        path[b] += [a]
    d = deque([0])
    while len(d):
        now = d.popleft()
        for nxt in path[now]:
            if ans[nxt] == -1:
                ans[nxt] = now
                sumcheck += 1
                d.append(nxt)
    if sumcheck == n:
        print('Yes')
        for i in ans[1:]:
            print(i+1)
    else:
        print('No')
    return


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

from heapq import heappush, heappop


def solve(N, X, Y):
    ans = [0] * (N)

    G = [[] for _ in range(N + 1)]
    for i in range(1, N):
        G[i].append(i + 1)
        G[i + 1].append(i)
    G[X].append(Y)
    G[Y].append(X)

    def dfs(vertex):
        nears = [float('inf')] * (N + 1)
        depth = 0
        que = [[depth, vertex]]
        while que:
            d, v = heappop(que)
            if d < nears[v]:
                nears[v] = d
                for g in G[v]:
                    heappush(que, [d + 1, g])
        return nears

    for i in range(1, N):
        # dfs
        nears = dfs(i)
        # print(nears)
        for j in range(i + 1, N + 1):
            ans[nears[j]] += 1

    for i in ans[1:]:
        print(i)


if __name__ == '__main__':
    N, X, Y = map(int, input().split())
    solve(N, X, Y)


### FIXED CODE ###

# 解説を参考に作成


def solve(N, X, Y):
    ans = [0] * (N)

    for i in range(1, N):
        for j in range(i + 1, N + 1):
            k = min(abs(j - i), abs(X - i) + 1 + abs(Y - j))
            ans[k] += 1

    for i in ans[1:]:
        print(i)


if __name__ == '__main__':
    N, X, Y = map(int, input().split())
    solve(N, X, Y)
### BUGGY CODE ###

n = int(input())
s = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        ii = str(i)
        jj = str(j)
        if ii[0] == jj[-1] and ii[-1] == jj[0]:
            s+=1
print(s)

### FIXED CODE ###

n = int(input())
cif = [[0]*10 for i in range(10)]

for i in range(1, n+1):
    s = str(i)
    f = int(s[0])
    r = int(s[-1])
    cif[f][r] += 1
res = 0

for i in range(10):
    for j in range(10):
        res += cif[i][j]*cif[j][i]
print(res)
### BUGGY CODE ###

n=int(input())
S=list(input())
p=[]
for i in range(n):
    s=S[:i].count('W')+S[i+1:].count('E')
    p.append(s)

print(min(p))


### FIXED CODE ###

n=int(input())
S=list(input())
R=[0]
for i in range(n):
    R.append(R[i]+(S[i]=='W'))
print(min([R[i]+n-i-1-(R[-1]-R[i+1]) for i in range(n)] ))
### BUGGY CODE ###

n = int(input())
arr = [1] * (n + 1)
for i in range(2, n + 1):
    for j in range(i, n + 1, i):
        arr[j] += 1
ans = 0
for i, c in enumerate(arr):
    ans += i * c
print(ans)


### FIXED CODE ###

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    ans = n * (n + 1) // 2
    for i in range(2, n + 1):
        k = n // i
        ans += i * k * (k + 1) // 2
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
### BUGGY CODE ###


import heapq
import collections
import sys
N =  int(input())
input = sys.stdin.readline

nums = list(map(int,input().split(" ")))
keta = [0] * 61
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = [1]
MOD = 10 ** 9 + 7
for i in range(60):
    temp = jijou[i] * 2
    temp%= MOD
    jijou.append(temp)

for num in nums:
    s = format(num,"b")
    l = len(s)
    for i in range(0,l):
        keta[i] += int(s[l - i - 1 ])
ans = 0
for j,num in  enumerate(nums[:-1]):
    s = format(num, "b")
    l = len(s)
    for i in range(0,61): #i →  2 ** i 乗 桁目に対応
        if l <= i:
            ans += (keta[i] * jijou[i]) % MOD
        else:
            if s[l - i - 1 ] == "0":
                ans += (keta[i] * jijou[i]) % MOD
            else:
#              (N - j + 1) - (keta[i] + 1 ) → 0が経っているところの個数
                ans += (( (N - j + 1) - (keta[i] + 1)  ) * ( jijou[i]) ) % MOD
                keta[i] -= 1
        ans %= MOD
    ans %= MOD


print(ans)

### FIXED CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    P = list(map(int, args[1].split()))

    ret = 0
    for i in range(n-k+1):
        ret = max(ret, (sum(P[i:i+k])+k)/2)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, k = map(int, args[0].split())
    P = list(map(int, args[1].split()))

    S = [0]*(n+1)
    for i, p in enumerate(P):
        S[i+1] += S[i] + P[i]

    ret = 0
    for i in range(k, n+1):
        ret = max(ret, (S[i]-S[i-k]+k)/2)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0
for i in range(N-1,1,-1):
    for j in range(i-1,0,-1):
        temp = L[i] - L[j]
        k = j-1
        while L[k] > temp and k >= 0:
            cnt += 1
            k -= 1
print(cnt)


### FIXED CODE ###

def main():
    from bisect import bisect
    N = int(input())
    L = list(map(int,input().split()))
    L.sort()
    cnt = 0

    for i in range(N-1,1,-1):
        for j in range(i-1,0,-1):
            temp = L[i] - L[j]
            l = bisect(L,temp,lo=0,hi=j)
            cnt += j - l
    print(cnt)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,Q=map(int,input().split())
s=list(input())
l=[]
def times(l,s):
    first=l[0]-1
    last=l[1]
    ss=[]
    count=0
    #5,4
    for i in range(first,last):
        ss.append(s[i])
    #print(ss)
    for i in range(len(ss)-1):
        if ss[i]=='A':
            if ss[i+1]=='C':
                count+=1
        #print(ss)
    return count

for i in range(Q):
    a=list(map(int,input().split()))
    l.append(a)
#print(l)

    
for c in l:
    ans=times(c,s)
    print(ans)






### FIXED CODE ###

N,Q=map(int,input().split())
s=input()
#a=[]

l=[0]*(N)
for i in range(N-1):
    if s[i:i+2]=='AC':
        l[i+1]=l[i]+1
    else:
        l[i+1]=l[i]
#print(l)
ans=[]
for i in range(Q):
    first,last=map(int,input().split())
    ans.append(l[last-1]-l[first-1])

for i in ans:
    print(i)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans_list =[]
for i in range(n):
    ans_list.append(a_list.index(i+1)+1)
print(*ans_list)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
ans_list =[0]*n
for i in range(n):
    ans_list[a_list[i]-1] = i+1
print(*ans_list)
### BUGGY CODE ###

N,K=map(int,input().split())
h=[int(i) for i in input().split()]
dp=[10**9]*(N)
dp[0]=0
for i in range(1,N):
    for j in range(max(0,i-K),i):
        dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])
print(dp[-1])


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(N):
  tmp = []
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i-j] + abs(h[i] - h[i-j]), c[i])
print(c[-1])
### BUGGY CODE ###

def main():
    N = int(input())
    *A, = map(int, input().split())
    ans = 0
    B = [0] * 61
    for k, a in enumerate(A):
        la = list(bin(a))[2:]
        j = 0
        for i in range(61-len(la), 61):
            B[i] += int(la[j])
            j += 1

    ans = 0
    mod = 10**9 + 7
    for i, b in enumerate(B):
        ans += b * (len(A)-b) * 2**(60-i) % mod
    print(ans % mod)

if __name__ == "__main__":
    main()


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
array = [0] * 60
for a in A:
    for j in range(len(bin(a))-2):
        array[j] += (a >> j) & 1
ans = 0
for i in range(60):
    ans += array[i] * (n-array[i]) * 2**i
print(ans % mod)
### BUGGY CODE ###

from collections import deque

def doubly_lined_list(n, A):
	Q = deque()

	for i in range(n):
		if A[i][0] == 'insert':
			Q.appendleft(A[i][1])
		elif A[i][0] == 'delete':
			try:
				Q.remove(A[i][1])
			except:
				pass
		elif A[i][0] == 'deleteFirst':
			Q.popleft()
		elif A[i][0] == 'deleteLast':
			Q.pop()

	print(' '.join(Q))

if __name__ == '__main__':
	n = int(input())
	A = []

	for i in range(n):
		A.append(input().split())

	doubly_lined_list(n, A)

### FIXED CODE ###

import sys
from collections import deque

def doubly_lined_list():
	n = int(input())
	Q = deque()

	for i in range(n):
		line = sys.stdin.readline()
		command = line.split()[0]

		if command == 'insert':
			Q.appendleft(line.split()[1])
		elif command == 'delete':
			try:
				Q.remove(line.split()[1])
			except:
				pass
		elif command == 'deleteFirst':
			Q.popleft()
		elif command == 'deleteLast':
			Q.pop()

	print(' '.join(Q))

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

from math import floor

A, B = map(int, input().split())

res = -1
for price in range(1, 10**7):
    if floor(price*0.08) == A and floor(price*0.1) == B:
        res = price
        break

print(res)


### FIXED CODE ###

from math import floor

A, B = map(int, input().split())

res = -1
for price in range(1, 10**6):
    if floor(price*0.08) == A and floor(price*0.1) == B:
        res = price
        break

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
vmap = dict()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

def dfs(prev, n):
    if prev < n:
        if (prev, n) in vmap:
            return 0 
        else:
            vmap[(prev, n)] = 1
    else:
        if (n, prev) in vmap:
            return 0 
        else:
            vmap[(n, prev)] = 1
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            print(n+1, v+1)
    if child_num % 2 == 0:
        return 1
    else:
        print(n+1, prev+1)
        return 0

dfs(-1, max(0, n - 2))

### FIXED CODE ###

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

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

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

### FIXED CODE ###

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

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i,j):
    if i>=n:
        return 0

    weight=wv[i][0]
    value =wv[i][1]

    if j<weight: # can't push this item
        val = solve(i+1,j)
    else:# push or not push
        val =  max(solve(i+1,j-weight)+value, solve(i+1,j))

    return val

print(solve(0,w))

### FIXED CODE ###

n,w = map(int, input().split())
wv = []
for _ in range(n):
    data = list(map(int,input().split()))
    wv.append(data)

dp = [[0 for i in range(w+1)] for j in range(n+1)]

for item in range(n):
    now_w=wv[item][0]
    now_v=wv[item][1]

    for weight in range(w+1):
        ans1=dp[item][weight]
        ans2=-1
        if weight - now_w >= 0:
            ans2=dp[item][weight-now_w]+now_v
        dp[item+1][weight] = max(ans1,ans2)

print(dp[n][w])
### BUGGY CODE ###

a,b,n = map(int, input().split())
ans = 0
N = [x for x in range(1,n+1) if (a*x)%b < a*(x%b)]

yuka = lambda a,b: (a-(a%b))/b

for x in N:
  score = yuka(a*x,b) - a*yuka(x,b)
  ans = max(ans,score)

print(int(ans))

### FIXED CODE ###

a,b,n = map(int, input().split())
yuka = lambda a,b: (a-(a%b))//b

x = min(n,b-1)
score = yuka(a*(x%b),b)
ans = score

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

def E(x):
    ans = (x+1)/2
    return ans

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

p = list(map(int,input().split()))
counter_li = []
for i in range(len(p)-k+1):
    temp = 0
    for j in range(k):
        temp+=p[i+j]
    counter_li.append(temp)

print(max(counter_li)/2+k/2)


### FIXED CODE ###

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

p = list(map(int,input().split()))
counter_li = []
first = 0
for i in range(k):
    first+=p[i]
counter_li.append(first)
for i in range(1,len(p)-k+1):
    counter_li.append(counter_li[i-1]+ p[i+k-1] - p[i-1])
print(max(counter_li)/2+k/2)
### BUGGY CODE ###

from statistics import median

n = int(input())
x = list(map(int, input().split()))

for i in range(n):
    x_median = x[0:i] + x[i+1:]
    print(median(x_median))

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
xsort = sorted(x)
x1, x2 = xsort[n//2-1], xsort[n//2]

for i in range(n):
    if x[i] <= x1:
        print(x2)
    else:
        print(x1)