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

# See:
# https://qiita.com/suecharo/items/30f5d817da4c948c3be6
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged


if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    order = list(x)

    for i in range(n):
        tmp = order[i]
        x.remove(tmp)
        x = merge_sort(x)
        print(x[(n // 2) - 1])
        x += [tmp]


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    sorted_x = sorted(x)

    low = sorted_x[(n // 2) - 1]
    high = sorted_x[(n // 2)]

    for i in range(n):
        if x[i] < high:
            print(high)
        else:
            print(low)
### BUGGY CODE ###

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

inf = 10 ** 4 + 1
dp = [inf] * N
dp[0] = 0

for i in range(1,N):
    H = h[i]
    dp[i] = min( [dp[j] + abs(h[j] - H) for j in range(max(0, i-K),i)])


print(dp[-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

n, q = list(map(int, input().split(" ")))
s = input()
s = s.replace("AC", "Z")
ac_index = []
i = 0
for _s in s:
    if _s == "Z":
        ac_index.append(i)
        i += 2
    else:
        i += 1
for _ in range(q):
    l, r = list(map(int, input().split(" ")))
    print(len([x for x in ac_index if l - 1 <= x <= r - 2]))


### FIXED CODE ###

n, q = list(map(int, input().split(" ")))
s = input()
s = s.replace("AC", "ZC")
num = 0
ac_index = []
for _s in s:
    if _s == "Z":
        ac_index.append(num)
        num += 1
    else:
        ac_index.append(num)
i = 0

for _ in range(q):
    l, r = list(map(int, input().split(" ")))
    print(ac_index[r-1] - ac_index[l-1])
### BUGGY CODE ###

def jud(n1,n2):
	if abs(n1-int(str(n2)[0]))<=1:
		return 1
	else:
		return 0

rnrn = [[1,2,3,4,5,6,7,8,9],[10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99]]

for div in range(1,12):
	rnrn.append([])
	for i in range(len(rnrn[div])):
		y = str(rnrn[div][i])
		x = int(y[-1])
		if x-1!=-1:
			rnrn[div+1].append(int(y+str(x-1)))
		rnrn[div+1].append(int(y+str(x)))
		if x+1!=10:
			rnrn[div+1].append(int(y+str(x+1)))
		
rnrn2 = []
for i in range(len(rnrn)):
	rnrn2.extend(rnrn[i])

print(rnrn2[int(input())])

### FIXED CODE ###

def jud(n1,n2):
	if abs(n1-int(str(n2)[0]))<=1:
		return 1
	else:
		return 0

rnrn = [[1,2,3,4,5,6,7,8,9],[10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99]]

for div in range(1,10):
	rnrn.append([])
	for i in range(len(rnrn[div])):
		y = str(rnrn[div][i])
		x = int(y[-1])
		if x-1!=-1:
			rnrn[div+1].append(int(y+str(x-1)))
		rnrn[div+1].append(int(y+str(x)))
		if x+1!=10:
			rnrn[div+1].append(int(y+str(x+1)))
		
rnrn2 = []
for i in range(len(rnrn)):
	rnrn2.extend(rnrn[i])

print(rnrn2[int(input())-1])
### BUGGY CODE ###

T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

A = 0
B = 0
ans = 0

if B1*T1+B2*T2==A1*T1+A2*T2:
    print('infinity')
    exit()

while True:
    flag1,flag2 = False,False
    if A>B and B+B1*T1>=A+A1*T1:
        ans += 1
    elif A<B and B+B1*T1<=A+A1*T1:
        ans += 1
    else:
        flag1 = True
    A += A1*T1
    B += B1*T1
    if A>B and B+B2*T2>=A+A2*T2:
        ans += 1
    elif A<B and B+B2*T2<=A+A2*T2:
        ans += 1
    else:
        flag2 = True
    A += A2*T2
    B += B2*T2

    if flag1 and flag2:
        break
print(ans)

### FIXED CODE ###

T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

C1 = (A1-B1)*T1
C2 = (A2-B2)*T2

if C1+C2==0:
    print('infinity')
elif C1*(C1+C2)>0:
    print(0)
else:
    if abs(C1)%abs(C1+C2)==0:
        print(abs(C1)//abs(C1+C2)*2)
    else:
        print(abs(C1)//abs(C1+C2)*2+1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

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

ans = 0
dp = [[0]*(S+1) for _ in range(N+1)]
for i in range(N):
    dp[i][0] += 1       # Lがiからを足す
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]             # A[i]を選ばない
        dp[i+1][j] %= MOD
        if j+A[i]<=S:
            dp[i+1][j+A[i]] += dp[i][j]    # A[i]を選ぶ
            dp[i+1][j+A[i]] %= MOD
    ans += dp[i+1][S]    # Rがiまでを足す
    ans %= MOD

print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

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

ans = 0
dp = [0]*(S+1)
for i in range(N):
    dp[0] += 1      # Lがiからを足す
    next_dp = [0]*(S+1)
    for j in range(S+1):
        next_dp[j] += dp[j]             # A[i]を選ばない
        next_dp[j] %= MOD
        if j+A[i]<=S:
            next_dp[j+A[i]] += dp[j]    # A[i]を選ぶ
            next_dp[j] %= MOD
    dp = next_dp
    ans += dp[S]    # Rがiまでを足す
    ans %= MOD

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

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

for i in range(n):
    count = 0
    w = s[:i]
    e = s[i + 1:]
    count += w.count('W')
    count += e.count('E')
    m = min(m, count)

print(m)

### FIXED CODE ###

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

reS = S[::-1]

wSum = [0 for i in range(N)]
eSum = [0 for i in range(N)]

for i in range(N):
    if i == 0:
        if S[i] == 'W':
            wSum[i] = 1
        if reS[i] == 'E':
            eSum[i] = 1
    else:
        if S[i] == 'W':
            wSum[i] = wSum[i-1] + 1
        else:
            wSum[i] = wSum[i-1]
        if reS[i] == 'E':
            eSum[i] = eSum[i-1] + 1
        else:
            eSum[i] = eSum[i-1]

eSum = eSum[::-1]

cost = eSum[1]

for i in range(1,N):
    if i == N - 1:
        if cost > wSum[N-2]:
            cost = wSum[N-2]
    else:
        if cost > wSum[i-1] + eSum[i+1]:
            cost = wSum[i-1] + eSum[i+1]
print(cost)
### BUGGY CODE ###

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

dp = [10**9]*n
dp[0] = 0

for i in range(n):
    for j in range(1,k+1):
        if i+j>=n:
            break
        dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
print(dp[n-1])

### FIXED CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,k = MAP()
h = MAP()

dp = [MOD]*n
dp[0]=0

for i in range(n-1):
    for j in range(i+1,min(i+k+1,n)):
        dp[j] = min(dp[j],dp[i]+abs(h[i]-h[j]))
print(dp[n-1])
### BUGGY CODE ###

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

# print(aa)
def mod(xx):
    bb=[]
    minX = min(xx)
    for i in range(len(xx)):
        b = xx[i] % minX if xx[i]>min(xx) else xx[i]
        if b>0:
            bb.append(b)
    return list(set(bb))

while True:
    bb = mod(aa)
    # print(bb)
    if min(aa)==min(bb) or min(bb)==1:
        break
    aa=bb
print(min(bb))

### FIXED CODE ###

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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

ans=aa[0]
for i in range(1,n):
    ans = gcd(ans, aa[i])
print(ans)
### BUGGY CODE ###

n = int(input())
Nr = list(reversed(list(map(int,str(n)))))
Nr.append(0)

ans = 0 
for i in range(len(Nr)):
    if Nr[i] > 5:
        Nr[i+1] += 1
        ans += (10 - Nr[i])
    elif Nr[i]==5:
        if Nr[i+1]>=5:
            Nr[i+1] += 1
            ans += (10 - Nr[i])
        else:
            ans += Nr[i]
    else:
        ans += Nr[i]


print(ans)

### FIXED CODE ###

n = input()
Nr = list(map(int,list(reversed(n))))
Nr.append(0)

ans = 0 
for i in range(len(Nr)):
    if Nr[i] > 5:
        Nr[i+1] += 1
        ans += (10 - Nr[i])
    elif Nr[i]==5:
        if Nr[i+1]>=5:
            Nr[i+1] += 1
            ans += (10 - Nr[i])
        else:
            ans += Nr[i]
    else:
        ans += Nr[i]

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

import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += math.gcd(k,math.gcd(i,j))

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):
        for k in range(1,K+1):
            if (i == j == k):
                ans += i
            if(i == j and j!= k ):
                    ans += 3*math.gcd(k,math.gcd(i,j))
            if(i<j<k and i != j != k):
                    ans += 6*math.gcd(k,math.gcd(i,j))

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

h, w = [int(i) for i in input().split()]

s = [input() for i in range(h)]

light = [[[0, 0, 0, 0] for i in range(w)] for j in range(h)]

for j in range(h):
    point = 0
    for i in range(w):
        if s[j][i] == ".":
            point += 1
            light[j][i][0] += point
        else:
            point = 0

    point = 0
    for i in range(w):
        if s[j][-1-i] == ".":
            point += 1
            light[j][-1-i][1] += point
        else:
            point = 0

for j in range(w):
    point = 0
    for i in range(h):
        if s[i][j] == ".":
            point += 1
            light[i][j][2] += point
        else:
            point = 0

    point = 0
    for i in range(h):
        if s[-1-i][j] == ".":
            point += 1
            light[-1-i][j][3] += point
        else:
            point = 0

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, sum(light[i][j]) -3)

print(ans)


### FIXED CODE ###

h, w = [int(i) for i in input().split()]

s = [input() for i in range(h)]

light = [[0 for i in range(w)] for j in range(h)]

for j in range(h):
    point = 0
    for i in range(w):
        if s[j][i] == ".":
            point += 1
            light[j][i] += point
        else:
            point = 0

    point = 0
    for i in range(w):
        if s[j][-1-i] == ".":
            point += 1
            light[j][-1-i] += point
        else:
            point = 0

for j in range(w):
    point = 0
    for i in range(h):
        if s[i][j] == ".":
            point += 1
            light[i][j] += point
        else:
            point = 0

    point = 0
    for i in range(h):
        if s[-1-i][j] == ".":
            point += 1
            light[-1-i][j] += point
        else:
            point = 0

ans = 0
for i in range(h):
    ans = max(ans, max(light[i]))
print(ans-3)
### BUGGY CODE ###

mondai = input()
s=[]
for i in range(len(mondai)):
    s.append(mondai[i])
alpha = 'abcdefghijklmnopqrstuvwxyz'
def check(s):
    if len(s)<2:return False
    border=len(s)//2
    for a in range(len(alpha)):
        k = s.count(alpha[a])
        if k>border:return True
    return False
def main(s):
    l = len(s)
    for i in range(l):
        target=''
        for j in range(i,l):
            target+=s[j]
            if check(target):
                return str(i+1)+' '+str(j+1)
    return '-1 -1'
print(main(s))

### FIXED CODE ###

mondai = input()
s=[]
for i in range(len(mondai)):
    s.append(mondai[i])
alpha = 'abcdefghijklmnopqrstuvwxyz'
def main(s):
    now=[]
    ind=len(s)
    for i in range(len(s)):
        x=s.pop()
        k = len(now)
        if k==0:now.append(x)
        if k==1:
            if x in now:return str(ind)+' '+str(ind+1)
            now.append(x)
        if k==2:
            if x in now:return str(ind)+' '+str(ind+2)
            if x not in now:
                now = now[1:]
                now.append(x)
        ind-=1
    return '-1 -1'
print(main(s))
### BUGGY CODE ###

# @author 

import sys

class RWalk:
    def solve(self):

        MOD = 10 ** 9 + 7

        def mult(A, B):
            n, m, p = len(A), len(A[0]), len(B[0])
            assert(len(B) == m)
            C = [[0] * p for _ in range(n)]
            for i in range(n):
                for j in range(p):
                    for k in range(m):
                        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD

            return C

        def pow(A, k):
            n, m = len(A), len(A[0])
            if k == 0:
                return [[1 if i == j else 0 for j in range(m)] for i in range(n)]

            if k % 2 == 0:
                return pow(mult(A, A), k // 2)

            return mult(A, pow(A, k - 1))


        n, k = [int(_) for _ in input().split()]
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])

        print(sum([sum(line) for line in pow(a, k)]) % MOD)

solver = RWalk()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class RWalk:
    def solve(self):

        MOD = 10 ** 9 + 7

        def mult(A, B):
            n, m, p = len(A), len(A[0]), len(B[0])
            assert(len(B) == m)
            C = [[0] * p for _ in range(n)]
            for i in range(n):
                for j in range(p):
                    for k in range(m):
                        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD

            return C

        def pow(A, k):
            n, m = len(A), len(A[0])
            if k == 0:
                return [[1 if i == j else 0 for j in range(m)] for i in range(n)]

            if k % 2 == 0:
                return pow(mult(A, A), k // 2)

            return mult(A, pow(A, k - 1))


        n, k = [int(_) for _ in input().split()]
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])

        print(sum([sum(line) for line in pow(a, k)]) % MOD)

solver = RWalk()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
#A = [a for a,b in AB]
#B = [b for a,b in AB]
#C = list(range(N))

def merge(la, lb, key):
  na = len(la)
  nb = len(lb)
  ans = [None] * (na+nb)
  ia = 0
  ib = 0
  
  while ia<na and ib<nb:
    if key(la[ia]) < key(lb[ib]):
      ans[ia+ib] = la[ia]
      ia += 1
    else:
      ans[ia+ib] = lb[ib]
      ib += 1
      
  if ia<len(la):
    ans[ia+ib:] = la[ia:]
  if ib<len(lb):
    ans[ia+ib:] = lb[ib:]
  return ans
    
def mergeSort(x, key):
    l = len(x)
    if l <= 1:
        return x
    d = l // 2 
    left = mergeSort(x[:d], key)
    right = mergeSort(x[d:], key)
    return merge(left,right, key)

AB = mergeSort(AB, key=lambda x:x[1])

ans = "Yes"
t = 0
for a,b in AB:
    t += a
    if t > b:
        ans = "No"

print(ans)

### FIXED CODE ###

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort(key = lambda x:x[1])

temp_total = 0
for a,b in AB:
  temp_total += a
  if temp_total<=b:
    continue
  else:
    print('No')
    break
else:
  print('Yes')
### BUGGY CODE ###

a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

### FIXED CODE ###

a=reversed(input())
#num=len(a)
mod_list=[1]+[0]*2019
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    mod_list[mod]+=1
res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)
### BUGGY CODE ###

import bisect
import sys
from collections import deque
sys.setrecursionlimit(100000000)

def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
  query = sorted(query,reverse = False)
  query2 = []
  for i in range(n):
    query2 += [query[i][0]]

  ans = 0
  judge = deque([])
  for i in range(m):
    left = bisect.bisect_left(query2,i+1)
    right = bisect.bisect_right(query2,i+1)

    judge += query[left:right]
    judge = deque(sorted(judge,reverse = True,key=lambda x: x[1]))
    if len(judge) != 0:
     a,b = judge.popleft()
     ans += b
  print(ans)
  
    
    
    
solve()
  
  

### FIXED CODE ###

import bisect
import sys
from collections import deque
import heapq
sys.setrecursionlimit(100000000)

def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
  query = sorted(query,reverse = False)
  query2 = []
  for i in range(n):
    query2 += [query[i][0]]

  ans = 0
  judge = []
  for i in range(m):
    left = bisect.bisect_left(query2,i+1)
    right = bisect.bisect_right(query2,i+1)
    for j in range(left,right):
     b,a = (query[j])
     heapq.heappush(judge, [-a,b])
    #print(judge)
    if len(judge) != 0:
     b,a = heapq.heappop(judge)
     ans += -b
  print(ans)
solve()
### BUGGY CODE ###

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

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (2*N+10)
IMOS[1] = 1
for i in range(0,N):
  for l,r in PAT:
    IMOS[i+l] += IMOS[i]
    IMOS[i+r+1] -= IMOS[i]
  #print(i, IMOS)
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] % MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)
    

### FIXED CODE ###

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

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (N+10)
IMOS[1] = 1
for i in range(0,N):
  if IMOS[i] == 0:
    continue
  for l,r in PAT:
    if i+l > N+1:
      continue
    IMOS[i+l] += IMOS[i]
    if i+r-1 > N+1:
      continue
    IMOS[i+r+1] -= IMOS[i]
  #print(i, IMOS)
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] %= MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)
### BUGGY CODE ###

a,b,c,d = map(int, input().split())

result = 0
for i in range(a, b+1):
  if i%c != 0 and i%d != 0:
    result += 1
  
print(result)

### FIXED CODE ###

a,b,c,d = map(int, input().split())

import fractions

def lcm(x, y):
    return int((x * y) / fractions.gcd(x, y))

com = lcm(c,d)

total = b - a + 1
fir = b//c - (a-1)//c
sec = b//d - (a-1)//d
rem = b//com - (a-1)//com

result = total - (fir + sec -rem)
  
print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def dp(i,is_reverse):
  if i == 0:
    if is_reverse == 0: return 0
    else: return -float('inf')
  else:
    if is_reverse == 0: return max(dp(i-1,0)+A[i-1],dp(i-1,1)-A[i-1])
    else: return max(dp(i-1,0)-A[i-1],dp(i-1,1)+A[i-1])

N = int(input())
A = list(map(int,input().split()))
print(dp(N,0))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
neg_num = 0
min_abs_a = float('inf')
sum_abs_A = 0
include_zero = False
for a in A:
  sum_abs_A += abs(a)
  min_abs_a = min(abs(a),min_abs_a)
  if a == 0: include_zero = True
  if a < 0 : neg_num += 1
print(sum_abs_A if neg_num%2==0 or include_zero is True else sum_abs_A - 2*min_abs_a)
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
A = np.array(A, dtype=int)

# dp[i]: i まで見たときの答えの最小値
# dp[i][0]: どこも通ってない
# dp[i][1]: D まで通った
# dp[i][2]: S まで通った
# dp[i][3]: T まで通った
# dp[i][4]: U まで通った
dp = np.zeros((N, 5), dtype=int)

dp[:, 0] = A.cumsum()
dp[0, 1] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0, 2] = int(A[0] % 2 != 1)
dp[0, 3] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0, 4] = A[0]
for i in range(1, N):
    dp[i, 1] = dp[i - 1, :1 + 1].min() + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i, 2] = dp[i - 1, :2 + 1].min() + int(A[i] % 2 != 1)
    dp[i, 3] = dp[i - 1, :3 + 1].min() + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i, 4] = dp[i - 1, :4 + 1].min() + A[i]
print(dp[-1].min())


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def cumsum(li):
    ret = []
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret


# 解説AC
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]

# dp[i]: i まで見たときの答えの最小値
# dp[i][0]: どこも通ってない
# dp[i][1]: D まで通った
# dp[i][2]: S まで通った
# dp[i][3]: T まで通った
# dp[i][4]: U まで通った
dp = [[0] * 5 for _ in range(N)]
for i, a in enumerate(cumsum(A)):
    dp[i][0] = a
dp[0][1] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0][2] = int(A[0] % 2 != 1)
dp[0][3] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0][4] = A[0]

for i in range(1, N):
    dp[i][ 1] = min(dp[i - 1][ :1 + 1]) + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i][ 2] = min(dp[i - 1][ :2 + 1]) + int(A[i] % 2 != 1)
    dp[i][ 3] = min(dp[i - 1][ :3 + 1]) + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i][ 4] = min(dp[i - 1][ :4 + 1]) + A[i]
print(min(dp[-1]))
### BUGGY CODE ###

s = input()
q = int(input())

num = 0

import sys

for _ in range(q):
    t = sys.stdin.readline().rstrip()
    if t == '1':
        if num == 0:
            num = 1
        else:
            num = 0
    else:
        t, f, c = t.split()
        if num == 0:
            if f == '1':
                s = c + s
            else:
                s = s + c
        else:
            if f == '2':
                s = c + s
            else:
                s = s + c

if num == 1:
    s = s[::-1]

print(s)

### FIXED CODE ###

#TLE
from collections import deque
s = deque(input())
q = int(input())
num = 0
for _ in range(q):
    t = input()
    if t == '1':
        if num == 0:
            num = 1
        else:
            num = 0
    else:
        t, f, c = t.split()
        if num == 0:
            if f == '1':
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == '2':
                s.appendleft(c)
            else:
                s.append(c)
s = ''.join(s)
if num == 1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

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

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

  
def power_func(x,y,z):
  bi=str(format(y,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %z
    if bi[i]=="1":
      res=(res*x) %z
  return res
C=[]
for i in range(p):
  C.append(comb(p-1,i,p))


B=[0]*p
if A[0]==0:
  for i in range(p):
    if A[i]==1:
      for j in range(p):
        B[j]=B[j]+(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]+1
else:
  B[0]=1
  for i in range(1,p):
    if A[i]==0:
      for j in range(p):
        B[j]=B[j]-(-1)**(j+1)*C[j]*power_func(i,p-j-1,p)
      B[0]=B[0]-1
for i in range(p-1):
  print(B[i]%p,end=" ")
print(B[-1]%p)

### FIXED CODE ###

p=int(input())
A=list(map(int,input().split()))
cmb=[0]*p
cmb[0]=1
for i in range(1,p):
  cmb[i]=cmb[i-1]*(p-i)*pow(i,p-2,p)%p
ans=[0]*p
for i in range(p):
  if A[i]==1:
    b=1
    ans[0]=ans[0]+1
    for j in range(p):
      ans[p-j-1]=(ans[p-j-1]-cmb[j]*b)%p
      b=b*(-i)%p
for i in range(p-1):
  print(ans[i],end=" ")
print(ans[p-1])