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

s = input()
Q = int(input())
q = []
f = []
c = []

for _ in range(Q):
    tmp = list(map(str,input().split()))
    if len(tmp) == 1:
        q.append(int(tmp[0]))
        f.append(0)
        c.append('')
    else:
        q.append(int(tmp[0]))
        f.append(int(tmp[1]))
        c.append(tmp[2])

for i in range(Q):
    if q[i] == 1:
        s = s[::-1]
    else:
        if f[i] == 1:
            s = c[i]+s
        else:
            s = s+c[i]

print(s)


### FIXED CODE ###

from collections import deque

s = list(input())
s2 = deque(list(reversed(s)))
s = deque(s)
Q = int(input())
q = []
f = []
c = []
count = 0

for _ in range(Q):
    tmp = list(map(str,input().split()))
    if len(tmp) == 1:
        count += 1
        q.append(int(tmp[0]))
        f.append(0)
        c.append('')
    else:
        q.append(int(tmp[0]))
        f.append(int(tmp[1]))
        c.append(tmp[2])


for i in range(Q):
    if q[i] == 1:
        tmp = s
        s = s2
        s2 = tmp
    else:
        if f[i] == 1:
            s.appendleft(c[i])
            s2.append(c[i])
        else:
            s.append(c[i])
            s2.appendleft(c[i])

for i in range(len(s)):
    print(s.popleft(),end="")
print("")
### BUGGY CODE ###

import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

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

if __name__=="__main__":
    main()

### FIXED CODE ###

import sys
def main():
    input=sys.stdin.readline
    N,K=map(int,input().split())
    H=tuple(map(int,input().split()))
    if N-1<=K:
        print(H[N-1]-H[0])
        return
    inf=10**9+7
    dp=[inf]*N
    dp[0]=0

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

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

def ite(N, M):
    import itertools
    li = []
    for i in range(1, M+1, 1):
         li.extend([i for _ in range(N)])
         
    p = itertools.permutations(li, N)
    return list(p)


def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

N, M, Q = list(map(int, input().split(" ")))
li = []
for i in range(Q):
    li.append(list(map(int, input().split(" "))))

m_s = 0
li2 = ite(N, M) 
for l2 in li2:
    if check(l2):
        s = score(l2, li)
        if m_s < s:
            m_s = s
            
print(m_s)

### FIXED CODE ###

def ite(N, M):
    import itertools
    return itertools.combinations_with_replacement(range(M),N)
def check(li):
    for i in range(len(li)-1):
        if li[i] > li[i+1]:
            return False
    return True
    
def score(l1, l2):
    s = 0
    for (a, b, c, d) in l2:
      if l1[b-1] - l1[a-1] == c:
            s += d
    return s
        

N, M, Q = list(map(int, input().split(" ")))
li = []
for i in range(Q):
    li.append(list(map(int, input().split(" "))))

m_s = 0
for l2 in ite(N, M):
    s = score(l2, li)
    if m_s < s:
      m_s = s
            
print(m_s)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

total = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        total += (A[i]%mod) * (A[j]% mod) % mod
        total %= mod
print(total)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sum_a=0
for i in A:
    sum_a+=i
    sum_a%=mod

total=0
for i in range(N - 1):
    sum_a -= A[i]
    total+=A[i]*(sum_a)
    total%=mod
print(total)
### BUGGY CODE ###

x = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)

    return arr

for number in factorization(x):
  for a in range(x):
    b = a - number
    if a**5 - b**5 == x:
      print(a,b)
      break
    elif a**5 - (-b)**5==x:
      print(a,-b)
      break

### FIXED CODE ###

import sys
x = int(input())

for a in range(120):
  for b in range(120):
    if a**5 - b**5 == x:
      print(a,b)
      sys.exit()
    elif a**5 - (-b)**5==x:
      print(a,-b)
      sys.exit()
### BUGGY CODE ###

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

dp = [float('inf')] * N
dp[0] = 0
for i in range(N-1):
    for j in range(i+1, i+K+1):
        if N <= j:
            break
        dp[j] = min(dp[j], dp[i] + abs(h[i]-h[j]))

print(dp[-1])

### FIXED CODE ###

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

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

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

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 2 ** 61 - 1
p2 = 10 ** 8 + 7
q = 10 ** 2

def rollingHash(N, M, A, ans):
	mul = 1
	for i in range(M):
		mul = (mul * q) % p

	Droll = defaultdict(lambda:-1)
	val = 0
	for i in range(M):
		val = val * q + A[i]
		val %= p

	Droll[val] = 0
	for i in range(N - M):
		val = (val * q - A[i] * mul + A[i + M]) % p
		if Droll[val] != -1 and i + 1 - Droll[val] >= M:
			return M

		Droll[val] = i + 1
	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, N):
		ans = rollingHash(N, i, S, ans)

	print(ans)



if __name__ == '__main__':
	main()

### FIXED CODE ###

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

p = 10 ** 9 + 7
p2 = 10 ** 9 + 9
q = 1007
q2 = 2009

def rollingHash(N, M, A, ans):
	mul1 = 1
	mul2 = 1
	for i in range(M):
		mul1 = (mul1 * q) % p
		mul2 = (mul2 * q2) % p2

	Droll1 = defaultdict(lambda:-1)
	Droll2 = defaultdict(lambda:-1)
	val1 = 0
	val2 = 0
	for i in range(M):
		val1 = val1 * q + A[i]
		val1 %= p
		val2 = val2 * q2 + A[i]
		val2 %= p2

	Droll1[val1] = 0
	Droll2[val2] = 0
	rolling_Hash1 = [None] * (N - M + 1)
	rolling_Hash1[0] = val1
	rolling_Hash2 = [None] * (N - M + 1)
	rolling_Hash2[0] = val2

	for i in range(N - M):
		val1 = (val1 * q - A[i] * mul1 + A[i + M]) % p
		val2 = (val2 * q2 - A[i] * mul2 + A[i + M]) % p2
		rolling_Hash1[i + 1] = val1
		rolling_Hash2[i + 1] = val2

		if Droll1[val1] == -1:
			Droll1[val1] = i + 1
		else:
			if rolling_Hash1[i + 1] == rolling_Hash1[Droll1[val1]] and rolling_Hash2[i + 1] == rolling_Hash2[Droll1[val1]] and i + 1 - Droll1[val1] >= M:
				return M

	return ans

#処理内容
def main():
	N = int(input())
	S = list(input())
	for i in range(N):
		S[i] = ord(S[i]) - 97

	ans = 0
	for i in range(1, int(N // 2) + 1):
		ans = rollingHash(N, i, S, ans)

	print(ans)



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

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
A += A    
from collections import defaultdict
d = defaultdict(list)
for i in range(N):
    d[B[i]].append(i)
i = 0
ans = []
while i < N:
    ok = True
    for j in range(N):
        if B[N-j-1] != A[N-j-1+i]:
            if d[A[N-j-1]] == []:
                i += N
                ok = False
                break
            else:
                i += N - d[A[N-j-1+i]][-1] - 1
                ok = False
                break
    if ok:
        ans.append((i,a[i]^b[0]))
        if len(d[A[N-1+i]]) == 1:
            i += N
        else:
            i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
if A == B == [A[0]]*N:
    for i in range(N): 
        ans.append((i,a[i]^b[0]))
else:
    A += A    
    d = defaultdict(list)
    for i in range(N):
        d[B[i]].append(i)
    i = 0
    ans = []
    while i < N:
        ok = True
        for j in range(N):
            if B[N-j-1] != A[N-j-1+i]:
                if d[A[N-j-1]] == []:
                    i += N
                    ok = False
                    break
                else:
                    i += N - d[A[N-j-1+i]][-1] - 1
                    ok = False
                    break
        if ok:
            ans.append((i,a[i]^b[0]))
            if len(d[A[N-1+i]]) == 1:
                i += N
            else:
                i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)
### BUGGY CODE ###

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

li_ = [0]*(N+1)
li_[2]=1
for i in range(2,N):
    li_[i+1]=li_[i]*(i+1)//(i-1)


for i in A:
    counter = 0
    for kind in se_:
        if kind == i:
            counter += li_[A.count(kind)-1]
        else:
            counter += li_[A.count(kind)]
    print(counter)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
se_ = Counter(A)
key = se_.keys()
 
 
all = 0
for i in key:
    all += se_[i]*(se_[i]-1)//2
    
 
for i in A:
    final=0
    final = all -se_[i]+1
    print(final)
### BUGGY CODE ###

def resolve():
    n, k = map(int, input().split())
    k = min(100, k)
    A = list(map(int, input().split()))
    for m in range(k):
        B = [0 for i in range(n + 1)]
        for i in range(n):
            l = max(0, i - A[i])
            r = min(n, i + A[i] + 1)
            B[l] += 1
            if r < n:
                B[r] -= 1

        for i in range(1, n):
            B[i] += B[i - 1]

        if A == B:
            break
        A = B[:n]

    for a in A:
        print(a, end=" ")

resolve()


### FIXED CODE ###

from numba import jit
import numpy as np

@jit
def resolve():
    n, k = map(int, input().split())
    A = np.array(list(map(int, input().split())), dtype=np.int64)
    for m in range(k):
        B = np.zeros(n + 1, dtype=np.int64)
        for i in range(n):
            l = max(0, i - A[i])
            r = min(n, i + A[i] + 1)
            B[l] += 1
            if r < n:
                B[r] -= 1
        A = np.cumsum(B)[:-1]
        if np.all(A == n):
            break

    for a in A:
        print(a, end=" ")

resolve()
### BUGGY CODE ###

s = input()

length = len(s)
f = 0

for p in range(length-1):
    for q in range(p+2,length+1):
        hikaku = s[p:q]
        #print(hikaku)
        for i in range(len(hikaku)):
            num = hikaku.count(hikaku[i])
            if num > len(hikaku)/2:
                print(str(p+1) + ' ' + str(q))
                f = 1
                break
        if f == 1:
            break
    if f == 1:
        break
if f == 0:
    print('-1 -1')


### FIXED CODE ###

s = input()

length = len(s)
f = 0

for p in range(length-1):
    for q in range(p+2,p+4):
        hikaku = s[p:q]
        #print(hikaku)
        for i in range(len(hikaku)):
            num = hikaku.count(hikaku[i])
            if num > len(hikaku)/2:
                print(str(p+1) + ' ' + str(q))
                f = 1
                break
        if f == 1:
            break
    if f == 1:
        break
if f == 0:
    print('-1 -1')
### BUGGY CODE ###

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

import fractions

def gcdoflist(l):
    n=len(l)
    if n==1:
        return l[0]
    else:
        ans=l[0]
        for i in range(1,n):
            ans=fractions.gcd(ans,l[i])
        return ans
m_list=[]
#端点の場合
#右端
m_list.append(gcdoflist(al[0:n-1]))

#左端
m_list.append(gcdoflist(al[1:n]))

for i in range(1,n-1):
    left=al[0:i]
    right=al[i+1:n]
    m_list.append(fractions.gcd(gcdoflist(left),gcdoflist(right)))
print(max(m_list))



### FIXED CODE ###

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

import fractions
ans=0
left=[0]
for i in range(1,n):
    ans=fractions.gcd(ans,al[i-1])
    left.append(ans)
#print(left)
right=[0 for i in range(n+1)]
for i in range(1,n+1):
    right[n-i]=fractions.gcd(right[n-i+1],al[n-i])
#print(right)

ans=0

for i in range(n):
    ans=max(ans,(fractions.gcd(left[i],right[i+1])))
print(ans)
### BUGGY CODE ###

def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import numpy as np
xs, ys, xt, yt = flpl()
rs,rt = 0, 0
N = int(input())
xyr = [(xs, ys, rs),(xt, yt,rt)] + [inpl() for _ in range(N)]
X, Y, R = np.array(xyr).T
X, Y, R = np.tile(X, (N+2, 1)), np.tile(Y, (N+2, 1)), np.tile(R, (N+2, 1))
edge = np.maximum(np.zeros((N+2, N+2)), np.sqrt(np.square(X-X.T) +\
                    np.square(Y-Y.T))-(R+R.T))
inf = float('inf')
dist = np.array([inf for _ in range(N+2)])
dist[0] = 0 
import heapq

remain = set(range(N+2))
Q = []
heapq.heappush(Q,(0,0))
while Q:
    k = heapq.heappop(Q)
    k = k[1]
    if k not in remain:
        continue
    remain.remove(k)
    for j in remain:
        if dist[k] + edge[k][j] < dist[j]:
            dist[j] = dist[k] + edge[k][j] 
            heapq.heappush(Q,(dist[j],j)) 
    if not remain:
        break
print(dist[1])

### FIXED CODE ###

def flpl(): return [float(i) for i in input().split()]
def inpl(): return [int(i) for i in input().split()]
import heapq
def dijkstra(vnum, vs):
    dist = [float('inf') for _ in range(vnum)]
    dist[vs] = 0 
    remain = set(range(vnum))
    Q = []
    heapq.heappush(Q,(0,vs))
    while Q:
        c, vn = heapq.heappop(Q)
        if vn not in remain :
            continue
        remain.remove(vn)
        for j in remain:
            evnj = edge(vn, j)
            if dist[vn] + evnj < dist[j]:
                dist[j] = dist[vn] + evnj 
                heapq.heappush(Q,(dist[j],j)) 
        if not remain:
            break
    return dist
def edge(s, t):
    return max(((X[s] - X[t])**2 + (Y[s] - Y[t])**2)**(1/2) -(R[s]+R[t]), 0)

xs, ys, xt, yt = flpl()
N = int(input())
xyr = [(xs, ys, 0),(xt, yt, 0)] + [inpl() for _ in range(N)]
X, Y, R = list(map(list, zip(*xyr)))
D = dijkstra(N+2, 0)
print(D[1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [int(x) for x in input().split()]
ans = 0
mod = 10 ** 9 + 7
# 制約がai <= 2^60なので
for d in range(61):
    # d桁目ごとに考える
    x = 0
    for a in A:
        if (a >> d) & 1:
            x += 1
    ans += x * (n-x) * 2**d
    ans %= mod
print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    ans = 0
    mod = 10 ** 9 + 7
    for d in range(61):
        # d桁目ごとに考える
        x = 0
        for a in A:
            if (a >> d) & 1:
                x += 1
        ans += x * (n-x) * 2**d
        ans %= mod
    print(ans)

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

import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L2 = sorted(L1)
ans = 0
for i in range(N):
    x,h = L2[i] 
    if h > 0:
        ans += h
        L2[i][1] = 0
        lim = x + 2*D
        for j in range(1,N-i):
            if L2[i+j][0] <= lim:
                L2[i+j][1] -= h
            else:
                break
print(ans)

### FIXED CODE ###

import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L1 = sorted(L1)
j = 1
L2 = [-1]*N
for i in range(N):
    lim = L1[i][0] + 2*D
    for k in range(j,N):
        if L1[k][0] > lim:
            L2[i] = k-1
            j = k-1
            break
        elif k == N-1:
            L2[i] = N-1
            j = N-1
ans = 0
a,s = 0,0
for i in range(N):
    x,h = L1[i]
    h -= a
    if h > 0:
        ans += h
        a += h
        L1[i][1] = h
    else:
        L1[i][1] = 0
    while s < N and L2[s] <= i:
        a -= L1[s][1]
        s += 1
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    h, w = MI()
    s = [[c == "#" for c in input()] for _ in range(h)]
    if w == 2:
        s = [list(sc) for sc in zip(*s)]
        h, w = w, h
    # p2D(s)
    t = [[-1] * (w - 1) for _ in range(h - 1)]
    for i in range(h - 1):
        for j in range(w - 1):
            t[i][j] = 1 - (sum(s[i][j:j + 2]) + sum(s[i + 1][j:j + 2])) % 2
    # p2D(t)
    # print()
    for j in range(w - 1):
        for i in range(1, h - 1):
            if t[i][j]: t[i][j] = t[i - 1][j] + 1
    # p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        # 高さ、位置の順
        stack = [[-1, 0]]
        for j in range(w - 1):
            while stack[-1][0] >= t[i][j]: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([t[i][j], j + 1])

        stack = [[-1, w - 1]]
        for j in range(w - 2, -1, -1):
            while stack[-1][0] >= t[i][j]: stack.pop()
            jtor[j] = stack[-1][1]
            stack.append([t[i][j], j])

        for j in range(w - 1):
            tmp = (jtor[j] - jtol[j] + 1) * (t[i][j] + 1)
            if tmp > ans: ans = tmp
    print(ans)

main()


### FIXED CODE ###

import sys

input=sys.stdin.readline
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())

def main():
    h, w = MI()
    s = [[c == "#" for c in input()[:-1]] for _ in range(h)]
    #if w == 2:
    #    s = [list(sc) for sc in zip(*s)]
    #    h, w = w, h
    # p2D(s)
    t = [[-1] * (w - 1) for _ in range(h - 1)]
    for i in range(h - 1):
        si = s[i]
        si1 = s[i + 1]
        t[i] = [1 - (sum(si[j:j + 2]) + sum(si1[j:j + 2])) % 2 for j in range(w - 1)]
    # p2D(t)
    # print()
    ti=t[0]
    for i in range(1, h - 1):
        ti1=ti
        ti=t[i]
        for j in range(w - 1):
            if ti[j]: ti[j] = ti1[j] + 1
    # p2D(t)
    ans = 0
    for i in range(h - 1):
        jtol = [0] * (w - 1)
        jtor = [0] * (w - 1)
        ti=t[i]
        # 高さ、位置の順
        stack = [[-1, 0]]
        for j in range(w - 1):
            tij=ti[j]
            while stack[-1][0] >= tij: stack.pop()
            jtol[j] = stack[-1][1]
            stack.append([tij, j + 1])

        stack = [[-1, w - 1]]
        for j in range(w - 2, -1, -1):
            tij=ti[j]
            while stack[-1][0] >= tij: stack.pop()
            jtor[j] = stack[-1][1]
            stack.append([tij, j])

        for j in range(w - 1):
            tmp = (jtor[j] - jtol[j] + 1) * (ti[j] + 1)
            if tmp > ans: ans = tmp
    print(max(ans,h,w))

main()
### BUGGY CODE ###

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

N, M = map(int, input().split())
abM = [list(map(int, input().split())) for i in range(M)]

transit = []
for i in range(M):
    if abM[i][0] == 1:
        transit.append(abM[i][1])

for i in range(M):
    if abM[i][0] in transit and abM[i][1] == N:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

### FIXED CODE ###

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

N, M = map(int, input().split())
abM = [list(map(int, input().split())) for i in range(M)]

transit = []
transit2 = []
for i in range(M):
    if abM[i][0] == 1:
        transit.append(abM[i][1])
    if abM[i][1] == N:
        transit2.append(abM[i][0])

# setで共通要素の集合を取ってみる
if len(set(transit) & set(transit2)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

# import numpy as np
# from decimal import Decimal

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

# A = np.array(A).astype(np.int64)

# ans = int(np.prod(A))


import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)

ans = functools.reduce(lambda a, b: a * b, A)

if ans > 10**18:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

import sys

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

ans = 1

if 0 in A:
  print(0)
  sys.exit()

for i in range(N):
  ans *= A[i]
  if ans > 1e18:
    print(-1)
    sys.exit()
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
if any(a[i] in a[:i] or a[i] in a[i+2:] for i in range(n)):
    print('NO')
else:
    print('YES')


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
if any(a[i] == a[i+1] for i in range(n-1)):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

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

N = NK[0]
K = NK[1]

town = 1
for i in range(K):
  town = A[town-1]
  
print(str(town))

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split())) 
b = 0
if k<=n:
  for i in range(k):
    b = a[b]-1
  print(b+1)
  exit(0)
c = [0]
for i in range(n):
  b = a[b]-1
  c.append(b)
d = c[:-1].index(c[-1])
c = c[d:-1]
k = k-d
print(c[k%len(c)]+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(K):
        next_A_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            for j in range(i-d, i+d+1):
                if j >= 0 and j <= N-1:
                    next_A_list[j] += 1
        A_list = next_A_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

if __name__ == "__main__":
    main()
    """
    N = 11
    K = N
    A_list = [0 for i in range(N)]
    A_list[N//2] = 1
    print(" ".join([ str(i).zfill(2) for i in A_list]))
    simulation(N, K, A_list)
    """



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(min(K, 42)):
        #next_A_list = [0 for i in range(N)]
        imos_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            imos_list[max(i-d, 0)] += 1
            if i+d+1 <= N-1:
                imos_list[i+d+1] -= 1
            #for j in range(i-d, i+d+1):
            #    if j >= 0 and j <= N-1:
            #        next_A_list[j] += 1
        for i in range(1, N):
            imos_list[i] += imos_list[i-1]
        A_list = imos_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

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

#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [10**6 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      if pre[x] == y:
        continue
      pre[y] = x
      now.append(y)
for x in pre:
  if x != 10**6:
    print(x+1)
  else:
    print(0)

### FIXED CODE ###

#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
precnt = [0 for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  precnt[b] += 1
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [-1 for _ in range(n)]
now = [r]
#print(precnt)
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      precnt[y] -= 1
      if precnt[y] == 0:
        now.append(y)
      pre[y] = x
#print(pre)
#print(precnt)
for x in pre:
  print(x+1)