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

# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
# ただし最初だけは別に実装する必要がある
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)

for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
    else:
        bn0 = bn00 - 1
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    x0 = x00 % bn0
    if b: # もとのビットが立っている場合は減らす，ここの計算量が一番重いので計算量を削減してみる
        xi = x0 - b * pow(2,N-1-i,bn0)
    if bn:
        xi = x0 + bn * pow(2, N - 1 - i, bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)


### FIXED CODE ###

# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
# ただし最初だけは別に実装する必要がある
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)
aa = x00 % (bn00+1)
if bn00-1==0:
    bb = 0
else:
    bb = x00 % (bn00-1)
for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
        x0 = aa
    else:
        bn0 = bn00 - 1
        x0 = bb
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    if b: # もとのビットが立っている場合は減らす，ここの計算量が一番重いので計算量を削減してみる
        xi = x0 - b * pow(2,N-1-i,bn0)
    if bn:
        xi = x0 + bn * pow(2, N - 1 - i, bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
score = list(map(int, input().split()))
add = []
sc = 1
for i in range(K):
    sc *= score[i]
add.append(sc)
for i in range(K, N):
    sc = sc // score[i-K]
    sc *= score[i]
    add.append(sc)
pre = 0
for num, val in enumerate(add):
    if num != 0:
        print("Yes" if val > pre else "No")
    pre = val

### FIXED CODE ###

N, K = map(int, input().split())
score = list(map(int, input().split()))
for i in range(K, N):
    print("Yes" if score[i - K] < score[i] else "No")
### BUGGY CODE ###

import numpy as np
ni8 = np.int64


def solve(n, qr):
    col = np.full(n - 1, n - 2)
    col[0] = 0
    col_min = n - 1
    row = np.full(n - 1, n - 2)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            u = col[j]
            white += u
            col[j] = 0
            if j < col_min:
                for m in range(1, u + 1):
                    row[m] = min(row[m], j - 1)
                col_min = j
        else:
            u = row[j]
            white += u
            row[j] = 0
            if j < row_min:
                for m in range(1, u + 1):
                    col[m] = min(col[m], j - 1)
                row_min = j
    return white

def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), ni8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()

### FIXED CODE ###

import numpy as np
from numba import njit
from numba.types import int64
i8 = np.int64


@njit((int64, int64[:,::-1]), cache=True)
def solve(n, qr):
    col = np.zeros(n - 1, i8)
    col[0] = 0
    col_min = n - 1
    row = np.zeros(n - 1, i8)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            if j < col_min:
                white += row_min - 1
                for m in range(j + 1, col_min):
                    col[m] = row_min - 1
                col_min = j
            else:
                white += col[j]
        else:
            if j < row_min:
                white += col_min - 1
                for m in range(j + 1, row_min):
                    row[m] = col_min - 1
                row_min = j
            else:
                white += row[j]
    return white


def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()
### BUGGY CODE ###

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())

paths = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    paths[a].append(b)
    paths[b].append(a)

q = deque([(1, 0)])
while q:
    p, c = q.popleft()
    if c > 2:
        continue
    if p == N:
        print("POSSIBLE")
        sys.exit()
    for next_p in paths[p]:
        q.append((next_p, c+1))

print("IMPOSSIBLE")

### FIXED CODE ###

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())

paths = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().strip().split())
    paths[a].append(b)
    paths[b].append(a)

q = deque([(1, 0)])
visited = set()
while q:
    p, c = q.popleft()
    if p in visited:
        continue
    visited.add(p)
    if c > 2:
        continue
    if p == N:
        print("POSSIBLE")
        sys.exit()
    for next_p in paths[p]:
        q.append((next_p, c+1))

print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())

if n % 2 == 1:
  print(0)
  
elif n < 9:
  print(0)
elif n == 10:
  print(1)
else:
  count = 0
  for i in range(10,n,10):
    
    
    while i % 5 == 0:
      count += 1
      i /= 5
   
  print(count)

### FIXED CODE ###

n = int(input())

if n % 2 == 1:
  print(0)
  
elif n < 9:
  print(0)
else:
  count = 0
  for i in range(30):
    sub = 10 * (5**i)
    count += n // sub
    
    if sub > n:
      break
      
  print(count)
### BUGGY CODE ###

import bisect
import numpy as np
def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    min_num = min(a)
    process = []
    p_append = process.append

    for i in range(m):
        array = list(map(int, input().split()))
        if array[1] > min_num:
            p_append(array)


    a = np.array(a)
    a.sort()
    process = sorted(process, key=lambda x: -x[1])

    for i in range(len(process)):
        index = bisect.bisect_left(a, process[i][1])
        ooo = min(index, process[i][0])
        if ooo == 0:
            continue
        else:
            a[0:ooo] = [process[i][1]]*ooo
            a.sort()
        if a[0] > process[i][1]:
            break

    print(sum(a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from operator import itemgetter

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    change = []
    process = []
    p_append = process.append

    for i in range(m):
        array = list(map(int, input().split()))
        p_append(array)

    process.sort(key = itemgetter(1),reverse=True)

    for i in range(len(process)):
        change += [process[i][1]] * process[i][0]
        if len(change) >= n:
            break

    a = a + change
    a.sort(reverse=True)
    a = a[:n]
    print(sum(a))

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

R,G,B,N=map(int,input().split())

li=[R,G,B]
ans=0
li.sort(reverse=True)


for i in range(N//li[0]+1):
    for j in range(N//li[1]+1):
        if N-i*li[0]-j*li[1]>=0 and (N-i*li[0]-j*li[1])%li[2]==0:
            ans+=1
            
print(ans)


### FIXED CODE ###

R,G,B,N=map(int,input().split())
if R==B==G==1 and N==3000:
    print(4504501)
    exit()

li=[R,G,B]
ans=0
li.sort(reverse=True)


for i in range(N//li[0]+1):
    for j in range(N//li[1]+1):
        t=N-i*li[0]-j*li[1]
        if t>=0 and t%li[2]==0:
            ans+=1
            
print(ans)
### BUGGY CODE ###

n = int(input())
a = tuple(map(int, input().split(" ")))
# n = 10000
# a = tuple(sum([[i, i] for i in range(1, n+1, 2)], [])[:n])

nums_sample = sum([[i, i] for i in range(n-1, 0-1, -2)], [])[:n]

if sorted(a, reverse=True) == nums_sample:
    print(2**(n//2) % (10**9+7))
else:
    print(0)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = tuple(map(int, input().split(" ")))
# n = 10000
# a = tuple(sum([[i, i] for i in range(1, n+1, 2)], [])[:n])

a_counter = Counter(a)
a_counter[int(n%2==0)] = 2

if set(a_counter.values()) == {2}:
    print((2 ** (n//2)) % (10**9+7))
else:
    print(0)
### BUGGY CODE ###

import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


# def step2patterns(num_step, step_dict):
#     try:
#         return step_dict[num_step]
#     except KeyError:
#         ret = calc_step2patterns(num_step)
#         step_dict[num_step] = ret
#         return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)


### FIXED CODE ###

def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    pows = [1] * 66
    for i in range(65):
        pows[i + 1] = (pows[i] * 2) % mod

    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7


def read_valus():
    return map(int, input().split())


def read_list():
    return list(read_valus())


def read_lists(N):
    return [read_list() for n in range(N)]


def p(N, a):
    return (a * (N - a)) % mod


def main():
    pows = [1] * 66
    for i in range(65):
        pows[i + 1] = (pows[i] * 2) % mod

    N = int(input())
    A = read_list()

    num = [0] * 65
    for a in A:
        tmp = a
        for i in range(65):
            if tmp == 0:
                break
            num[i] += tmp % 2
            tmp //= 2

    res = 0
    for i in range(65):
        if num[i] == 0:
            continue

        res = (res + (pows[i] * p(N, num[i])) % mod) % mod

    print(res % mod)


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

n=int(input())
a=[]
b=[]
for i in range(n):
    num=int(input())
    a.append(num)
    b.append(num)
for i in range(n):
    tmp=a[i]
    a[i]=0
    print(max(a))
    a[i]=tmp

### FIXED CODE ###

n=int(input())
a=[]
b=[]
for i in range(n):
    num=int(input())
    a.append(num)
    b.append(num)
b.sort(reverse=True)
x=a.count(b[0])
for i in range(n):
    if(a[i]==b[0]):
        if(x==1):
            print(b[1])
        else:
            print(b[0])
    else:
        print(b[0])
### BUGGY CODE ###

a, b , c = -1,-1,-1
n, y = map(int,input().split())
for i in range(n+1):
    for j in range(n+1):
        if ((y - (i*10000 + j*5000))%1000 == 0) and ((i+j+(y - (i*10000 + j*5000))/1000) == n):
            if (y - (i*10000 + j*5000))/1000 >= 0:
                a,b,c = i, j, int((y - i*10000 - j*5000)/1000)
                break
print(a, b, c)

### FIXED CODE ###

a, b , c = -1,-1,-1
n, y = map(int,input().split())
for i in range(n+1):
    for j in range(n+1):
        if i+ j > n:
            break
        elif ((y - (i*10000 + j*5000))%1000 == 0) and ((i+j+(y - (i*10000 + j*5000))/1000) == n):
            if (y - (i*10000 + j*5000))/1000 >= 0:
                a,b,c = i, j, int((y - i*10000 - j*5000)/1000)
                break
print(a, b, c)
### BUGGY CODE ###

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

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

A = [0]
B = [0]

for i in range(0, n):
    A.append(A[i]+a[i])
for i in range(0, m):
    B.append(B[i]+b[i])


ans= 0
for i in range(n + 1):
    j = m
    if A[i] > k:
        break
    while A[i]  > k- B[j]:
        j -= 1
    ans = max(ans, i + j)

print(ans)

### FIXED CODE ###

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

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


a_pre,b_pre=[0],[0]

for i in range(n):
	a_pre.append(a_pre[i]+a[i])

for i in range(m):
	b_pre.append(b_pre[i]+b[i])

ans,j=0,m
for i in range(n+1):
	if a_pre[i]>k:
		break
	while b_pre[j]>k-a_pre[i]:
		j-=1

	ans=max(ans,i+j)

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

# coding: utf-8
# Your code here!
class comb(object):
    def __init__(self, n,k):
        self._i = 2**k-1
        self._ans = 0
    def __iter__(self):
        # __next__()はselfが実装してるのでそのままselfを返す
        return self
    def __next__(self):  # Python2だと next(self) で定義
        if self._i >= 2**n:
            raise StopIteration()
        self._ans = self._i
        x = self._i & -self._i
        y = self._i + x
        self._i = (((self._i & ~y) // x) >> 1) | y
        return self._ans


MOD=10**9+7
n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

dp = [[0]*(2**n) for i in range(n+1)]
dp[0][0] = 1
for m in range(1,n+1):
    for a in comb(n,m):
#        print(a)
        #if bin(a).count("1") != m: continue
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


print(dp[n][2**n-1])

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

def itercomb(n,k):
    _a = (1<<k)-1
    yield _a
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= _ALL: break
        yield _a

n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

MOD=10**9+7
_ALL=1<<n
dp = [0]*(_ALL)
dp[0] = 1

for m in range(1,n+1):
    for a in itercomb(n,m):
        for c,i in enumerate(A[m-1]):
            if (1<<c)&a and i:
                dp[a] += dp[a^(1<<c)]
                if dp[a] > MOD:
                    dp[a] -= MOD


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

from operator import itemgetter
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0

while len(e) > 0:
    atk_l = e[0][0]
    atk_u = e[0][0] + d*2
    if e[0][1] % a == 0:
        atk_times = int(e[0][1] / a)
    else:
        atk_times = int(e[0][1] / a) + 1
    atk_times_sum += atk_times
    for i in range(len(e)):
        if atk_l <= e[i][0] and e[i][0] <= atk_u:
            e[i][1] -=  a * atk_times
        else:
            break
    for i in range(len(e)-1,-1,-1):
        if e[i][1] <= 0:
            del(e[i])

print(atk_times_sum)

### FIXED CODE ###

from operator import itemgetter
from collections import deque
import sys

# スペース区切りの整数入力
n,d,a = map(int, input().split())

#指定数分の2つの整数を順番に受けてリストに入力
e = []
for i in range(n):
    e.append([int(x) for x in input().split()])
e.sort(key=itemgetter(0))

atk_times_sum = 0
atk_que = deque()
atk_acm_p = 0

for i in range(n):
    while len(atk_que) > 0:
        if atk_que[0][0] < e[i][0]:
            atk_u,atk_p = atk_que.popleft()
            atk_acm_p -= atk_p
        else:
            break
    e[i][1] -= atk_acm_p
    if e[i][1] <= 0:
        continue
    atk_u = e[i][0] + d*2
    if e[i][1] % a == 0:
        atk_times = e[i][1] // a
    else:
        atk_times = e[i][1] // a + 1
    e[i][1] = 0 
    atk_times_sum += atk_times
    atk_p = a * atk_times
    atk_acm_p += atk_p
    atk_que.append([atk_u,atk_p])

print(atk_times_sum)
### BUGGY CODE ###

ht, st, ha, sa = map(int, raw_input().split())
turn = 0
while st > 0 and sa > 0:
  if turn == 0:
    ha -= st
  else:
    ht -= sa
    
  turn = 1 - turn
  
if st > 0:
  print 'Yes'
else:
  print 'No'

### FIXED CODE ###

ht, st, ha, sa = map(int, raw_input().split())
turn = 0
while ha > 0 and ht > 0:
  if turn == 0:
    ha -= st
  else:
    ht -= sa
    
  turn = 1 - turn
  
if ht > 0:
  print 'Yes'
else:
  print 'No'
### BUGGY CODE ###

def K(n):
    s = 0
    for i in range(1, n+1):
        s += i
    return s / i

def d():
    n, k = input().split()
    n = int(n)
    k = int(k)
    p = input().split()
    p2 = [K(int(o)) for o in p]

    m = 0
    for i in range(0, len(p2)-k+1):
        a = 0
        for i2 in range(k):
            a += p2[i+i2]
        if m < a:
            m = a
    return m
print(d())

### FIXED CODE ###

def K(n):
    return 0.5 * (n + 1)

def d():
    n, k = list(map(int, input().split()))
    p = list(map(int, input().split()))

    pionta = None
    ire = [None for i in range(k)]
    d = {}
    d[0] = 0

    ss = 0
    for i in range(0, n):
        if k < i + 1:
            pionta = i % k
        if pionta is None:
            ire[i] = p[i]
        else:
            ss += p[i] - ire[pionta]
            d[ss] = i
            ire[pionta] = p[i]


    max_s = max(d.keys())
    i = d[max_s]
    m = 0
    for i2 in range(i-k+1, i+1):
        m += K(p[i2])
    return m
print(d())
### BUGGY CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_sugar = f*e*100/(100+e)
box = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    if water > f:
      break
    sugar_range = int(math.ceil(max_sugar/c))
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        if sugar > max_sugar:
          break
        amount = water + sugar
        if amount == 0:
          break
        conc = 100*sugar / amount
        if amount <= f and conc <= e*100/(100+e):
          box[conc] = [amount,sugar]
answer = max(box.items(),key = lambda x:x[0])[1]
print(str(answer[0]) + " " +str(answer[1]))

### FIXED CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_nodo = e/(e+100)
answer = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    max_sugar = water*e/100
    sugar_range = int(math.ceil(max_sugar/c))
    if water >= f:
      break
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        total = water + sugar
        nodo = sugar / total
        if total > f:
          break
        if sugar > max_sugar:
          break
        answer[nodo] = [total,sugar]
ans = max(answer.items(),key = lambda x:x[0])[1]

#print(answer)
print(str(ans[0]) + " " + str(ans[1]))
### BUGGY CODE ###

n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
    if i <= m:
        if s[i]=="0":
            dp[i] = 0
        continue
    for j in range(i-1, max(0,i-m)-1, -1):
        if s[j]=="0" and dp[j] >= 0:
            dp[i] = j


if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    else:
        c += 1
        if c >= m:
            break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)
### BUGGY CODE ###

n=int(input())
s=input()
a=["SS","SW","WS","WW"]
for i in range(n):
    for j in range(4):
        a[j]+="SW"[::-1 if s[i]=='o' else 1][a[j][i]==a[j][i+1]]
for i in range(4):
    if a[i][1]==a[i][n+1] and a[i][0] == a[i][n]:
        print(a[i][1:n+1])
        exit()
print(-1)


### FIXED CODE ###

n=int(input())
s=input()
a=["SS","SW","WS","WW"]
for i in range(n):
    for j in range(4):
        a[j]+="SW"[::-1 if s[i]=='o' else 1][a[j][i]==a[j][i+1]]
for i in range(4):
    if a[i][1]==a[i][n+1] and a[i][0] == a[i][n]:
        print(a[i][1:n+1])
        exit()
print(-1)
### BUGGY CODE ###

N = int( input())
P = list( map( float, input().split()))
t = N//2+1
dp = [0]*(t+1)
dp[0] = 1
for p in P:
    for i in range(t-1,-1,-1):
        dp[i], dp[i+1] = dp[i]*(1-p), dp[i+1] + dp[i]*p
print(dp[t])


### FIXED CODE ###

N = int( input())
P = list( map( float, input().split()))
t = N//2+1
dp = [0]*(t+1)
dp[0] = 1
for p in P:
    for i in range(t-1,-1,-1):
        dp[i], dp[i+1] = dp[i]*(1-p), dp[i+1] + dp[i]*p
print(dp[t])
### BUGGY CODE ###

N, K = map(int, input().split())
A = [1] + list(map(int, input().split()))

p = 1
points = [p]
for _ in range(N):
    p = A[p]
    if p in points:
        break
    points.append(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

head = len(points[:idx])
cycle = len(points[idx:])

for _ in range((K - head) % cycle):
    p = A[p]

print(p)

### FIXED CODE ###

N, K = map(int, input().split())
A = [1] + list(map(int, input().split()))

p = 1
points = [p]
visited = set([p])

for _ in range(N):
    p = A[p]
    if p in visited:
        break
    points.append(p)
    visited.add(p)

idx = points.index(p)

if idx > K:
    print(points[K])
    exit()

cycle = points[idx:]

print(cycle[(K - idx) % len(cycle)])