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

import queue

N, M = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(M)]
S, T = list(map(int, input().split()))

V = [[0, 0, 0] for _ in range(N + 1)]
R = {}

for u, v in uv:
  if u not in R:
    R[u] = [v]
  else:
    R[u].append(v)
q = queue.Queue()
put = q.put
get = q.get

put([S, 0, 2])
ans = -1
while not q.empty():
  t = get()
  if t[0] == T and t[2] == 2:
    ans = t[1]
    break
  k = (t[2] + 1) % 3
  m = t[1]
  if t[2] == 2:
    m += 1
  if t[0] not in R: continue
  for i in R[t[0]]:
    if V[i][k] == 0:
      V[i][k] = 1
      put([i, m, k])

print(ans)

### FIXED CODE ###

import queue

N, M = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(M)]
S, T = list(map(int, input().split()))

V = [[0, 0, 0] for _ in range(N + 1)]
R = {}

for u, v in uv:
  if u not in R:
    R[u] = [v]
  else:
    R[u].append(v)
q = queue.Queue()
put = q.put
get = q.get

put([S, 0, 2])
ans = -1
while not q.empty():
  t = get()
  if t[0] == T and t[2] == 2:
    ans = t[1]
    break
  k = (t[2] + 1) % 3
  m = t[1]
  if t[2] == 2:
    m += 1
  if t[0] not in R: continue
  for i in R[t[0]]:
    if V[i][k] == 0:
      V[i][k] = 1
      put([i, m, k])

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

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if (N * h * n) >= (4 * h * n - N * (h + n)) > 0:
            if (N * h * n) % (4 * h * n - N * (h + n)) == 0:
                w = (N * h * n) // (4 * h * n - N * (h + n))
                print (h, n, w)
                exit()


### FIXED CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        if (N * h * n) >= (4 * h * n - N * (h + n)) > 0:
            if (N * h * n) % (4 * h * n - N * (h + n)) == 0:
                w = (N * h * n) // (4 * h * n - N * (h + n))
                print (h, n, w)
                exit()
### BUGGY CODE ###

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

s = input()
n = len(s)
q = int(input())
front = ""
back = ""
sgn = 0
for _ in range(q):
	query = input().split()
	if query[0] == "1":
		sgn ^= 1
	else:
		f, c = int(query[1])-1, query[2]
		if f ^ sgn == 0:
			front += c
		else:
			back += c
if not sgn:
	print(front[::-1] + s + back)
else:
	print(back[::-1] + s[::-1] + front)

### FIXED CODE ###

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

s = input()
#n = len(s)
q = int(input())
front = ""
back = ""
sgn = 0
for _ in range(q):
	query = input().split()
	if query[0] == "1":
		sgn ^= 1
	else:
		f, c = int(query[1])-1, query[2]
		if f ^ sgn == 0:
			front += c
		else:
			back += c
if not sgn:
	print(front[::-1] + s + back)
else:
	print(back[::-1] + s[::-1] + front)
### BUGGY CODE ###

N, Q = map(int,input().split())
S= input()
ac_pos_list = []
start = 0
ret = 0
ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(len(S)-1)]

for i in range(Q):
    l,r = map(int,input().split())
    l = l-1
    r = r-1
    ans = sum(ac_tf_list[l:r])
    print(ans)

### FIXED CODE ###

N, Q = map(int,input().split())
S= input()
lr_list = [list(map(int,input().split())) for _ in range(Q)]

# ac_tf_list = [1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
t = [0]*N
for i in range(N-1):
    if S[i:i+2]=='AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for i in range(Q):
    l = lr_list[i][0]-1
    r = lr_list[i][1]-1
    print(t[r]-t[l])
### BUGGY CODE ###

n,m,k=map(int,input().split())
fr=[input() for i in range(m)]
bl=[input() for i in range(k)]
relfr=[set() for i in range(n)]
relbl=[set() for i in range(n)]
for l in fr:
  a,b=map(int,l.split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for l in bl:
  a,b=map(int,l.split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
cand={0}
searched=set()
gr=set()
all_gr={i for i in range(n)}
ans=[0]*n
c=0
while True:
  while True:
    now=cand.pop()
    gr.add(now)
    c+=1
    for point in relfr[now].difference(gr,cand):
      cand.add(point)
    if len(cand)==0:
      break
  for i in gr:
    ans[i]=len(gr)-len(relfr[i])-len(relbl[i].intersection(gr))-1
    searched.add(i)
  all_gr-=searched
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,m,k=map(int,input().split())
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for i in range(k):
  a,b=map(int,input().split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
blsiz=[0 for i in range(n)]
ans=[0]*n
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(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 isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
uf=UnionFind(n)
for i in range(n):
  for j in relfr[i]:
    uf.Unite(i,j)
for i in range(n):
  for j in relbl[i]:
    if uf.isSameGroup(i,j):
      blsiz[i]+=1
for i in range(n):
  ans[i]=uf.Count(i)-len(relfr[i])-blsiz[i]-1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

def gcd(a, b):
  if(b % a == 0):
    return a
  elif(a % b == 0):
    return b
  else:
    ans = 1
    i = 2
    while a!= 1:
      if(a % i == 0):
        while a % i == 0:
          a/= i
        while b % i == 0:
          b/= i
          ans*= i
        i+= 1
    return ans
          

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])
  
gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(d[i+ 1])

print(ggcd(gcds))

### FIXED CODE ###

def gcd(a, b):
  if(a == b):
    return a
  elif(a % b == 0):
    return b
  elif(b % a == 0):
    return a
  elif(a == 1 or b == 1):
    return 1
  elif(a > b):
    return gcd(a- a// b* b, b)
  elif(a < b):
    return gcd(a, b- b// a* a)

def ggcd(lista):
  if(len(lista) == 1):
    return lista.pop()
  else:
    l = lista.pop()
    for i in range(1, len(lista)):
      l = gcd(l, lista.pop())
    return l

N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
d = []
gcds = set()
x.sort()

for i in range(N):
  d.append(x[i+ 1]- x[i])

gcds.add(d[0])

for i in range(N- 1):
  if(d[i+ 1] != d[i]):
    gcds.add(d[i+ 1])

print(ggcd(gcds))
### BUGGY CODE ###

if __name__ == '__main__':
    mod = 10 ** 9 + 7
    n, m = map(int, input().split())

    pow_ = [0] * 31
    divisor = 2
    power = 0
    while m % divisor == 0:
        m //= divisor
        power += 1
    if power > 0:
        pow_[power] += 1

    divisor = 3
    while m > 1:
        power = 0
        while m % divisor == 0:
            m //= divisor
            power += 1
        if power > 0:
            pow_[power] += 1
        divisor += 2

    # print(pow_)

    ans = 1
    t = 1
    d = 1
    for power, cnt in enumerate(pow_[1:], 1):
        # 1 <= power <= 30
        t = t * (n - 1 + power) % mod
        d = d * pow(power, mod - 2, mod) % mod
        # print(power, cnt, ans, t, d)
        ans = ans * pow(t * d % mod, cnt, mod) % mod
        # for _ in range(cnt):
        #     ans = ans * t * d % mod
    print(ans)


### FIXED CODE ###

MOD = 10 ** 9 + 7


def prime_factorization(n):
    i = 2
    res = []
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        i += 1
    if n > 1:
        res.append(1)
    return res


def comb(a, b):
    b = min(b, a - b)
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b == 1:
        return a
    else:
        return (a % MOD) * pow(b, MOD - 2, MOD) % MOD * comb(a - 1, b - 1) % MOD


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

ans = 1
for power in prime_factorization(M):
    ans *= comb(N - 1 + power, power)
    ans %= MOD

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

from collections import Counter
from math import factorial

N = int(input())
A = [int(i) for i in input().split()]
cnt_list = Counter(A)
ans_dict = {}

for i in range(N):        
    if not ans_dict.get(A[i]):
        ans = 0
        for num, cnt in cnt_list.items():
            if num == A[i]:
                cnt = cnt-1
            ans += factorial(cnt) // factorial(2) // factorial(cnt - 2) if cnt > 1 else 0
        ans_dict[A[i]] = ans
    print(ans_dict[A[i]])

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
cnt_list = Counter(A)

total = sum([cnt*(cnt-1)//2 if cnt > 1 else 0 for cnt in cnt_list.values()])
print(*[total-cnt_list[a]+1 for a in A], sep='\n')
### BUGGY CODE ###

def key_func(n):
    return n[0]

n,m = map(int, input().split(" "))
a_b = []
for i in range(n):
    a_b.append(list(map(int,input().split(" "))))

money = 0

while m > 0:
    ind = a_b.index(min(a_b,key=key_func))
    i = min(m,a_b[ind][1])
    money = money + a_b[ind][0]*i
    m = m - i
    del a_b[ind]

print(money)

### FIXED CODE ###

def key_func(n):
    return n[0]

n,m = map(int, input().split(" "))
a_b = []
for i in range(n):
    a_b.append(list(map(int,input().split(" "))))

a_b.sort(key=key_func)

money = 0

for item in a_b:
    i = min(m,item[1])
    money = money + item[0]*i
    m = m - i
    if m <= 0:
        break

print(money)
### BUGGY CODE ###

n, m = map(int, input().split(" "))
max = 1
for i in range((int)(m/n), 1, -1):
  if m % i == 0:
    max = i
    break
print(max)
  

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n, m = map(int, input().split(" "))
max = 1
#print(make_divisors(m))
for i in make_divisors(m):
  if i > m/n:
    break
  else:
    max = i
print(max)
### BUGGY CODE ###

MOD = 2019
L, R = map(int, input().split())

ans = float('inf')
for i in range(L,R):
    for j in range(i+1,R+1):
        ans = min(ans,(i*j)%MOD)
        if ans == 0:
            break
print(ans)

### FIXED CODE ###

MOD = 2019
L, R = map(int, input().split())

if R - L > 2019:
    print(0)
    exit()

ans = float('inf')
for i in range(L,R):
    for j in range(i+1,R+1):
        ans = min(ans,(i*j)%MOD)
print(ans)
### BUGGY CODE ###

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

# i=1 では必ず成り立つので i>=2 から調べる
s = 1
for i in range(1, N):
  flag = True
  for j in range(i):
    if P[j] < P[i]:
      flag = False
      break
  
  if flag: s += 1
    
print(s)

### FIXED CODE ###

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

# 各時点での最小値を求める
m = [0]*(N)
m[0] = p[0]
for i in range(N-1):
  m[i+1] = min(m[i], p[i+1])

ans = 1
for i in range(1, N):
  if m[i-1] > p[i]: ans += 1
    
print(ans)
### BUGGY CODE ###

n = int(input())
list = list(map(int, input().split(" ")))
c = 0

for x in range(n):
    for y in range(n):
        if x != y and list[x] == list[y]:
            c += 1

if c == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n = int(input())
a = len(set(map(int, input().split(" "))))
if n == a:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import functools
import fractions
n = int(input())
values = list(map(int, input().split()))
m = 1

for i in range(n):
    a = values[:]
    a.pop(i)
    gcd = functools.reduce(fractions.gcd, a)
    if m < gcd:
        m = gcd


print(m)


### FIXED CODE ###

n = int(input())
v = list(map(int, input().split()))
m = 1
gf = []
gp = []


def gcd(x, y):
    if x < y:
        x += y
        y = x - y
        x -= y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x


gf.append(v[0])
for i in range(n-1):
    gf.append(gcd(gf[i], v[i+1]))

gp.append(v[n-1])
for i in range(n-1):
    gp.append(gcd(gp[i], v[n-2-i]))

m = gp[n-2]

for i in range(n-1):
    b = gcd(gf[i], gp[n-3-i])
    if m < b:
        m = b
if m < gf[n-2]:
    m = gf[n-2]

print(m)
### BUGGY CODE ###

n=int(input())
a_=list(map(int,input().split()))
a=[[i,ai] for i,ai in enumerate(a_)]
ans=0
for i,ai in a:
  c=len([[j,aj]for j,aj in a if j>i and ai+i==j-aj])
  ans+=c
print(ans)


### FIXED CODE ###

def main(n,a_):
  from collections import defaultdict
  lr=[[i+ai,i-ai] for i,ai in enumerate(a_)]
  rs=defaultdict(lambda:0)
  ls=defaultdict(lambda:0)
  ans=0
  for l,r in lr:
    rs[r]+=1
    ls[l]+=1
  for k in rs.keys():
    ans+=rs[k]*ls[k]
  print(ans)
if __name__=='__main__':
  n=int(input())
  a_=list(map(int,input().split()))
  #n=200000
  #a_=[3 for _ in range(n)]
  main(n,a_)
### BUGGY CODE ###

n = int(input())
l = [input() for i in range(n)]

mylist = []
for s in l:
    s_list = [ c for c in s]
    mylist.append("".join(sorted(s_list)))

ans=0
for i in range(len(mylist)):
    ans += mylist.count(mylist[0]) - 1
    del mylist[0]

print(ans)

### FIXED CODE ###

n = int(input())
i = 0
sortedSet = {}
while i < n:
    temp = ''.join(sorted(input()))

    if temp in sortedSet:
        sortedSet[temp]+=1
    else:
        sortedSet[temp]=1
    i += 1

result = 0
for v in sortedSet.values():
    result = int(result + v*(v-1)/2)

print(result)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc123/tasks/abc123_d

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = LIST()

# A.sort(reverse=True); B.sort(reverse=True); C.sort(reverse=True)

E = []
for a in A:
    for b in B:
        E.append(a+b)
# E.sort(reverse=True)

ans = []

for c in C:
    for e in E:
        ans.append(c+e)
ans.sort(reverse=True)

for i, a in enumerate(ans):
    if i < K:
        print(a)
    else:
        break

### FIXED CODE ###

# https://atcoder.jp/contests/abc123/tasks/abc123_d

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = LIST()

# A.sort(reverse=True); B.sort(reverse=True); C.sort(reverse=True)

E = []
for a in A:
    for b in B:
        E.append(a+b)
E.sort(reverse=True)

ans = []

for c in C[:K]:
    for e in E[:K]:
        ans.append(c+e)
ans.sort(reverse=True)

for i, a in enumerate(ans):
    if i < K:
        print(a)
    else:
        break
### BUGGY CODE ###

import bisect

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

if 0 in X:
  K=K-1
ans=[]
Right=[]
Left=[]
  
for x in X:
  if x>0:
    Right.append(x)
  else:
    Left=[abs(x)]+Left

Right=[0]+Right
Left=[0]+Left
    
for i in range(K+1):
  if i<=len(Right)-1 and K-i<=len(Left)-1:
    ans.append(min(Right[i],Left[K-i])*2+max(Right[i],Left[K-i]))

if K==0:
  ans.append(0)

print(min(ans))

### FIXED CODE ###

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

ans=[]

for i in range(N-K+1):
  xl=X[i]
  xr=X[i+K-1]
  ans.append(min(abs(xl)+abs(xr-xl),abs(xr)+abs(xl-xr)))

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

import sys

while True:
	a = sys.stdin.readlines()
	for i in range(len(a)):
		b = a[i].split()
		m =int(b[0])
		f =int(b[1])
		r =int(b[2])
		if m*f < 0 and r!=-1:
			print "F"
		elif m==-1 and f==-1 and r==-1:
			break
		else:
			if m+f >= 80:
				print "A"
			elif 80 > m+f >=65:
				print "B"
			elif 65 > m+f >=50:
				print "C"
			elif 50 > m+f >=30 and r < 50:
				print "D"
			elif 50 > m+f >=30 and r >= 50:	
				print "C"
			elif 30 > m+f:
				print "F"

### FIXED CODE ###

import sys

a = sys.stdin.readlines()
for i in range(len(a)):
	b = a[i].split()
	m =int(b[0])
	f =int(b[1])
	r =int(b[2])
	if m*f < 0 :
		print "F"
	elif m==-1 and f==-1 and r==-1:
		break
	else:
		if m+f >= 80:
			print "A"
		elif 80 > m+f >=65:
			print "B"
		elif 65 > m+f >=50:
			print "C"
		elif 50 > m+f >=30 and r < 50:
			print "D"
		elif 50 > m+f >=30 and r >= 50:	
			print "C"
		elif 30 > m+f:
			print "F"
### BUGGY CODE ###

N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(1 , M+1) :
    a = int(input())
    brake.append(a)

for i in range(1, N+1) :
    if i in brake :
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
         
print(stair[N])





### FIXED CODE ###

N , M = (int(a) for a in input().split())
stair = [1]*(N+1)
for i in range(1 , M+1) :
    a = int(input())
    stair[a] = 0
 
for i in range(2, N+1) :
    stair[i] *= (stair[i-1] + stair[i-2]) % (10**9+7)
         
print(stair[N])
### BUGGY CODE ###

import sys


class mydeque:
    class cell:
        def __init__(self,x,y = None,z = None):
            self.data = x
            self.next = y
            self.prev = z

    def __init__(self):
        head = mydeque.cell(None)
        head.next = head
        head.prev = head
        self.size = 0
        self.head = head

    def push_front(self,x):
        h = self.head
        q = h.next
        p = mydeque.cell(x,q,h)
        h.next = p
        q.prev = p
        self.size += 1

    def push_back(self,x):
        h = self.head
        p = h.prev
        q = mydeque.cell(x,h,p)
        h.prev = q
        p.next = q
        self.size += 1

    def delete_top(self):
        h = self.head
        top = h.next
        nexttop = top.next
        h.next = nexttop
        nexttop.prev = h
        del top
        self.size -= 1

    def delete_last(self):
        h = self.head
        last = h.prev
        prevlast = last.prev
        h.prev = prevlast
        prevlast.next = h
        del last
        self.size -= 1

    def delete_find(self,target):
        h = self.head
        now_data = h.next
        while now_data != self.head:
            if now_data.data == target:
                next_now = now_data.next
                prev_now = now_data.prev
                next_now.prev = prev_now
                prev_now.next = next_now
                del now_data
                self.size -= 1
                break
            now_data = now_data.next

    def allprint(self):
        h = self.head.next
        for i in range(self.size):
            if i == self.size - 1:
                print(h.data)
            else:
                print(h.data, end=" ")
                h = h.next

# with open("input.txt","r") as f:
queue = int(input())
length = 0
myd = mydeque()
for q in range(queue):
    command = [n for n in input().strip("\n").split(' ')]
    if command[0] == "insert":
        myd.push_front(command[1])
    elif command[0] == "delete":
        myd.delete_find(command[1])
    elif command[0] == "deleteFirst":
        myd.delete_top()
    else:
        myd.delete_last()
myd.allprint()

### FIXED CODE ###

from collections import deque
query = int(input())
l = deque()
for _ in range(query):
    command = input().strip()
    if command == "deleteFirst":
        try:
            l.popleft()
        except:
            pass
    elif command == "deleteLast":
        try:
            l.pop()
        except:
            pass
    else:
        command, value = command.split(" ")
        if command == "insert":
            l.appendleft(int(value))
        elif command == "delete":
            try:
                l.remove(int(value))
            except:
                pass
print(*l)
### BUGGY CODE ###

n = int(input())
s = ['']*n
for i in range(n):
    s[i] = ''.join(sorted(input()))
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
dic = {}
for i in range(n):
    tmp = ''.join(sorted(input()))
    if tmp in dic:
        dic[tmp] = dic[tmp]+1
    else:
        dic.setdefault(tmp, 0)
ans = 0
for i in dic:
    ans += 1/2 * dic[i] * (dic[i]+1)
print(int(ans))
### BUGGY CODE ###

import numpy as np

n, k = map(int, input().split())
arr = np.concatenate(
    [np.array(list(map(int, input().split()))), np.zeros(k, dtype=int)])

INF = 1 << 60

# dp初期化
dp = np.full(n + k, INF, dtype=int)
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        dp[i + j] = min(dp[i + j], dp[i] + np.abs(arr[i + j] - arr[i]))

print(dp[n - 1])

### FIXED CODE ###

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

# dp初期化
dp = [float("inf")] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i - k, 0), i))

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

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

a = sorted(a)
ans = N
for i in range(N-1, -1, -1) :
    psum = 0
    for j in range(i, -1, -1) :
        if psum+a[j] < K :
            psum += a[j]
        else :
            ans = min(ans, j)

print(ans)

### FIXED CODE ###

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

a = sorted(a)
ans = N
psum = 0
for i in range(N-1, -1, -1) :
    if psum+a[i] < K :
        psum += a[i]
    else :
        ans = min(ans, i)

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

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

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

for i in range(n):
    for j in range(0,n+1):
        if j == 0:
            dp[i+1][0] = dp[i][0]*(1-a[i])
        elif j == n:
            dp[i+1][-1] = dp[i][-2]*a[i]
        else:
            dp[i+1][j] = dp[i][j-1]*a[i] + dp[i][j]*(1-a[i])
    

print(sum(dp[-1][(n+1)//2:]))





### FIXED CODE ###

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist 小数はfloat
    return list(map(float,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()

a = l()

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

for i in range(n):
    for j in range(0,n+1):
        if j == 0:
            dp[i+1][0] = dp[i][0]*(1-a[i])
        elif j == n:
            dp[i+1][-1] = dp[i][-2]*a[i]
        else:
            dp[i+1][j] = dp[i][j-1]*a[i] + dp[i][j]*(1-a[i])
    

print(sum(dp[-1][(n+1)//2:]))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]

print(*b)


### FIXED CODE ###

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

if n%2==0 :
    print(*(a[1::2][::-1]+a[0::2]))
else:
    print(*(a[0::2][::-1]+a[1::2]))