Harryxun/stf_run huggingface dataset:
# 区間[i,j]における最小値を返す
# 値の更新をする
import fractions
input = sys.stdin.readline
class segment_tree:
    '''
    init_val(int): 初期化値
    Input(array):  入力
    '''
    def __init__(self, init_val, Input):
        #self.num:n以上の最小の2のべき乗(一番下のNodeの数)
        n=len(Input)
        self.init_val = init_val
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [init_val] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = Input[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i]=self._segfunc(self.seg[2*i+1],self.seg[2*i+2])
    def _segfunc(self, left, right):
        '''
        ここに求めたい関数を入れる
        ex)最小値問題→min, 
        left:左の子
        right:右の子
        '''
        res=fractions.gcd(left,right)
        return res
    def update(self, k, x):
        '''
        k番目の値をxに書き換える
        '''
        k += self.num - 1
        self.seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.seg[k] = self._segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    def query(self, p, q):
        '''
        区間[p,q)の目的の値を取り出す
        '''
        if q <= p:
            return self.init_val
        p += self.num - 1
        q += self.num - 2
        res = self.init_val
        while q - p > 1:
            if p % 2 == 0: #始点が偶数or終点が奇数だと端っこが余る
                res = self._segfunc(res, self.seg[p])
            if q % 2 == 1:
                res = self._segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        res = self._segfunc(res, self.seg[p])
        res = self._segfunc(res, self.seg[q])
        return res
INF = 10 ** 10
n=int(input())
a=list(map(int,input().split()))

# a = [randint(0,N*2) for _ in range(N)]
dp = segment_tree(0, a)
ans=-1
for i in range(n):
  ans=max(ans,fractions.gcd(dp.query(0,i),dp.query(i+1,n)))
print(ans)

### FIXED CODE ###

def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x % y) #再帰定義
n=int(input())
a=list(map(int,input().split()))
l=[0]*n
r=[0]*n
for i in range(1,n):
  if i==1:
    l[1]=a[0]
    r[-2]=a[-1]
  else:
    l[i]=gcd(l[i-1],a[i-1])
    r[-i-1]=gcd(r[-i],a[-i])
g=[0]*n
for i in range(n):
  if l[i]==0 or r[i]==0:
    g[i]=l[i]+r[i]
  else:
    g[i]=gcd(l[i],r[i])
print(max(g))
h, w = map(int, input().split())
s = [list('.'*(w+2))]
for i in range(h):
    s.append(list('.' + input() + '.'))
s.append(list('.'*(w+2)))
for i in s:
    print(i)

def search(y, x):
    t = 0
    for i in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        dy, dx = y + i[0], x + i[1]
        if s[dy][dx] == '#':
            t += 1
    if t > 0:
        return True
    else:
        return False


for i in range(w):
    for j in range(h):
        if s[i+1][j+1] == '#' and not search(i+1, j+1):
            print('No')
            quit()
print('Yes')

### FIXED CODE ###

h, w = map(int, input().split())
s = [list('.'*(w+2))]
for i in range(h):
    s.append(list('.' + input() + '.'))
s.append(list('.'*(w+2)))

def search(y, x):
    t = 0
    for i in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        dy, dx = y + i[0], x + i[1]
        if s[dy][dx] == '#':
            t += 1
    if t > 0:
        return True
    else:
        return False


for i in range(w):
    for j in range(h):
        if s[j+1][i+1] == '#' and not search(j+1, i+1):
            print('No')
            quit()
print('Yes')
N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = [sum(range(1, ps[i]+1))/ps[i] for i in range(N)]
maxs = []
for i in range(N):
  if i<K:
    continue
  else:
    maxs.append(sum(Es[i-K:i]))
print(max(maxs))

### FIXED CODE ###

N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = [(ps[i]+1)/2 for i in range(N)]
maxs = []
for i in range(1, N+1):
  if i<K:
    continue
  elif i==K:
    tmp = sum(Es[:i])
    maxs.append(tmp)
  else:
    tmp = tmp +Es[i-1]-Es[i-K-1]
    maxs.append(tmp)
print(max(maxs))
k,x = map(int,input().split())
a = x-k+1
b = x+k
c = list(range(a,b))
str(c)
print(' '.join(c))

### FIXED CODE ###

k,x = map(int,input().split())
t = []
for i in range(x-k+1,x+k):
    t.append(str(i))
print(' '.join(t))
import math

# 最大公約数を求める問題
N, X = map(int, input().split())
x = [int(_) for _ in input().split()]
if N == 1:
    print(abs(x[0]-X))
    exit()

x.sort()
# N > 1と仮定
for i in range(N-1):
    if x[i] < X and x[i+1] > X:
        x = x[:i+1] + [X] + x[i+1:]
        break

if len(x) >= 3:
    base = math.gcd(x[1]-x[0], x[2]-x[1])
    for i in range(2, N):
        diff = x[i+1] - x[i]
        base = math.gcd(base, diff)
    print(base)
else:
    print(x[1] - x[0])


### FIXED CODE ###

import math

# 最大公約数を求める問題
N, X = map(int, input().split())
x = [int(_) for _ in input().split()]
if N == 1:
    print(abs(x[0]-X))
    exit()

x.sort()
# N > 1と仮定
for i in range(N-1):
    if x[i] < X and x[i+1] > X:
        x = x[:i+1] + [X] + x[i+1:]
        break
    elif x[i] >= X:
        x = [X] + x
        break
    elif x[i+1] <= X:
        x = x + [X]
        break

if len(x) >= 3:
    base = math.gcd(x[1]-x[0], x[2]-x[1])
    for i in range(2, N):
        diff = x[i+1] - x[i]
        base = math.gcd(base, diff)
    print(base)
else:
    print(x[1] - x[0])
from collections import deque
N,K = list(map(int,input().split()))
K = deque()
for i in range(M):
    A = deque(map(int,input().split()))
    K.append(A[0])
    A.popleft()
p = list(map(int,input().split()))
ans = 0
for i in range(1 << N):
    f = True
    for j in range(M):
        s = 0
        for k in ks[j][1:]:
            s += (i >> (k - 1)) & 1
        if s % 2 != p[j]:
            f = False
    if f:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import deque
N,M = list(map(int,input().split()))
K = []
for i in range(M):
    A = list(map(int,input().split()))
    K.append(A)
p = list(map(int,input().split()))
ans = 0
for i in range(1 << N):
    f = True
    for j in range(M):
        s = 0
        for k in K[j][1:]:
            s += (i >> (k - 1)) & 1
        if s % 2 != p[j]:
            f = False
    if f:
        ans += 1
print(ans)
n, k = map(int, input().split())
s = input()

print(s[:k-1] + s[k-1].lower() + s[k:n])

### FIXED CODE ###

H, W = map(int, input().split())
h, w = map(int, input().split())

print((H - h) * (W - w))
S=str(input())
K=int(input())
if len(S)<=K:
    print(S)
else:
    print(S[0:K]+"...")

### FIXED CODE ###

K=int(input())
S=input()
if len(S)<=K:
    print(S)
else:
    print(S[:K]+"...")
import  math

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

ans = (math.factorial(n) // (math.factorial(n - 2) * math.factorial(2)))  + (math.factorial(m) // ((math.factorial(m - 2) * math.factorial(2))))
print(ans)

### FIXED CODE ###

import  math

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

def ans(a):
    if a<2:
        return 0
    else:
        return math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))

print(int(ans(n) + ans(m)))
S = Input().split(' ')
A = int(S[0])
B = int(S[1])
A_t = A/0.08
B_t = B/0.1
if A_t == B_t:
    print(A_t)
else:
    print(-1)

### FIXED CODE ###

import math

S = input().split(' ')
A = int(S[0])
B = int(S[1])
p = -1
for x in range(2100):
    if math.floor(x*0.08) == A and math.floor(x*0.1) == B:
        p = x
        break
print(p)
N = int(input())
P = sorted([int(input()) for X in range(0,N)])
P[-1] = P[-1]//2
print(sum(SP))

### FIXED CODE ###

N = int(input())
P = [int(input()) for X in range(0,N)]
P[P.index(max(P))] = max(P)//2
print(sum(P))
a = int(input())
b = int(input())
print(str(a * b))

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
from otsutil import parg
A, B, C = map(int, input().split())
for i in range(1, B + 1):
    if A * i % B == C:
        print('YES')
        break
else:
    print('NO')


### FIXED CODE ###

A, B, C = map(int, input().split())
for i in range(1, B + 1):
    if A * i % B == C:
        print('YES')
        break
else:
    print('NO')
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ab = [[a[i], b[i]] for i in range(n)]
ab.sort(key=lambda x:x[1])

a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]

a2 = [[a[i], i] for i in range(n)]
a2.sort(key=lambda x:x[0])

flag1 = 0
for i in range(n):
    if a2[i][0] > b[i]:
        flag1 = 1

flag2 = 1
idx = a2[0][1]
cnt = 0
while idx != 0:
    idx = a2[idx][1]
    cnt += 1

if cnt == n-1:
    for i in range(n-1):
        if a2[i+1] <= b[i]:
            flag2=0
            break
else:
    flag2 = 0

if flag1 == 1 or flag2 == 1:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

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

ab = [[a[i], b[i]] for i in range(n)]
ab.sort(key=lambda x:x[1])

a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]

a2 = [[a[i], i] for i in range(n)]
a2.sort(key=lambda x:x[0])

flag1 = 0
for i in range(n):
    if a2[i][0] > b[i]:
        flag1 = 1

flag2 = 1
idx = a2[0][1]
cnt = 0
while idx != 0:
    idx = a2[idx][1]
    cnt += 1

if cnt == n-1:
    for i in range(n-1):
        if a2[i+1][0] <= b[i]:
            flag2=0
            break
else:
    flag2 = 0

if flag1 == 1 or flag2 == 1:
    print('No')
else:
    print('Yes')
N = int(input())

def amari(x):
    if x == 1:
        return 'a'
    elif x == 2:
        return 'b'
    elif x == 3:
        return 'c'
    elif x == 4:
        return 'd'
    elif x == 5:
        return 'e'
    elif x == 6:
        return 'f'
    elif x == 7:
        return 'g'
    elif x == 8:
        return 'h'
    elif x == 9:
        return 'i'
    elif x == 10:
        return 'j'
    elif x == 11:
        return 'k'
    elif x == 12:
        return 'l'
    elif x == 13:
        return 'm'
    elif x == 14:
        return 'n'
    elif x == 15:
        return 'o'
    elif x == 16:
        return 'p'
    elif x == 17:
        return 'q'
    elif x == 18:
        return 'r'
    elif x == 19:
        return 's'
    elif x == 20:
        return 't'
    elif x == 21:
        return 'u'
    elif x == 22:
        return 'v'
    elif x == 23:
        return 'w'
    elif x == 24:
        return 'x'
    elif x == 25:
        return 'y'
    elif x == 26:
        return 'z'

i = 1
my_str = []
while True:
    if 26 ** i > N:
        if i == 1:
            print(amari(N))
            exit()
        for j in range(i - 2 + 2):
            t = amari(N // (26 ** (1 + i - 2 - j)))
            my_str.append(t)
            N -= ((26 ** (1 + i - 2 - j) *  (N // (26 ** (1 + i - 2 - j)))))
        strA = "".join(my_str)
        print (strA)
        exit()
    i += 1

### FIXED CODE ###

def amari(x):
    if x == 0:
        return 'a'
    elif x == 1:
        return 'b'
    elif x == 2:
        return 'c'
    elif x == 3:
        return 'd'
    elif x == 4:
        return 'e'
    elif x == 5:
        return 'f'
    elif x == 6:
        return 'g'
    elif x == 7:
        return 'h'
    elif x == 8:
        return 'i'
    elif x == 9:
        return 'j'
    elif x == 10:
        return 'k'
    elif x == 11:
        return 'l'
    elif x == 12:
        return 'm'
    elif x == 13:
        return 'n'
    elif x == 14:
        return 'o'
    elif x == 15:
        return 'p'
    elif x == 16:
        return 'q'
    elif x == 17:
        return 'r'
    elif x == 18:
        return 's'
    elif x == 19:
        return 't'
    elif x == 20:
        return 'u'
    elif x == 21:
        return 'v'
    elif x == 22:
        return 'w'
    elif x == 23:
        return 'x'
    elif x == 24:
        return 'y'
    elif x == 25:
        return 'z'
    
N = int(input())
K = 0
k = 0
i = 0
my_str = []
while True:
    if  k <= N <= K:
        N = N - k #number in the floor
        for j in range(i): # i=length of the coded name
            my_str.append(amari(N % 26))
            N = N // 26
        strA = ''.join(my_str[::-1])
        print(strA)
        exit()
    else:
        i += 1
        k = K + 1
        K += 26 ** i
h,w=map(int,input().split())
a=[]
for i in range(h):
  tmp=input()
  if len(tmp)!=tmp.count('.'):
    a.append(tmp)
  else:
    h-=1
    
a=list(zip(*a))
for i in range(w):
  if len(a[i])==a[i].count('.'):
    del a[i]
    w-=1
    i-=1
    
a=list(zip(*a))
for i in range(h):
  print(a[i])
      


### FIXED CODE ###

h,w=map(int,input().split())
a=[]
for i in range(h):
  tmp=input()
  if len(tmp)!=tmp.count('.'):
    a.append(tmp)
  else:
    h-=1

b=[]
for i in range(w):
  cnt=0
  for j in range(h):
    if a[j][i]=='.':
      cnt+=1
  if cnt==h:
    b.append(0)
  else:
    b.append(1)

for i in range(h):
  for j in range(w):
    if b[j]:
      print(a[i][j], end='')
  print()
a,b=input().split()
if (a=="H" and b=="H") or (a=="D" and b=="D"):
  print(H)
  else:
    print(D)

### FIXED CODE ###

a,b=input().split()
if (a=="H" and b=="H") or (a=="D" and b=="D"):
    print("H")
else:
    print("D")
N, M = map(int, input().split())
pLst = [list(map(int, input().split())) for i in range(M)]

for i in range(len(pLst)):
    pLst[i].append(i)
nLst = [''] * N

for i in range(N):
    nLst[i] = str(i + 1).zfill(6)
tLst = sorted(pLst, key=lambda x: (x[0], x[1]))
ansLst = [''] * M
tmp = nLst[tLst[i][0] - 1]
index = 1
for i in range(M):
    if tmp == nLst[tLst[i][0] - 1]:
        ansLst[tLst[i][2]] = nLst[tLst[i][0] - 1] + str(index).zfill(6)
        index += 1
    else:
        index = 1
        tmp == nLst[tLst[i][0] - 1]
        ansLst[tLst[i][2]] = nLst[tLst[i][0] - 1] + str(index).zfill(6)

for i in ansLst:
    print(i)

### FIXED CODE ###

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

for i in range(len(pLst)):
    pLst[i].append(i)
nLst = [''] * N

for i in range(N):
    nLst[i] = str(i + 1).zfill(6)
tLst = sorted(pLst, key=lambda x: (x[0], x[1]))
ansLst = [''] * M
tmp = nLst[tLst[0][0] - 1]
index = 1
for i in range(M):
    if tmp == nLst[tLst[i][0] - 1]:
        ansLst[tLst[i][2]] = nLst[tLst[i][0] - 1] + str(index).zfill(6)
        index += 1
    else:
        index = 1
        tmp = nLst[tLst[i][0] - 1]
        ansLst[tLst[i][2]] = nLst[tLst[i][0] - 1] + str(index).zfill(6)
        index += 1

for i in ansLst:
    print(i)
import sys
table = "abcdefghijklmnopqrstuvwxyz"
sentence = ''
for line in sys.stdin:
    sentence += str(input().lower())

for i in table:
    print(i + " : " + str(sentence.count(i)))



### FIXED CODE ###

import sys

table = "abcdefghijklmnopqrstuvwxyz"

sentence = sys.stdin.read()
sentence1 = sentence.lower()
for i in table:
    print(i + ' : ' + str(sentence1.count(i)))
from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor(left + right)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle - 1
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])

### FIXED CODE ###

from math import floor  
stairs_num, broken_num = tuple(int(i) for i in input().split(" "))
broken_list = []
for i in range(broken_num):
    broken_list.append(int(input()))
trance_num_list = []
if len(broken_list) >= 1 and broken_list[0] == 1:
    trance_num_list.append(0)
else:
    trance_num_list.append(1)
if (len(broken_list) >= 1 and broken_list[0] == 2) or \
 (len(broken_list) >= 2 and broken_list[1] == 2):
    trance_num_list.append(0)
else:
    if trance_num_list[0] == 0:
        trance_num_list.append(1)
    else:
        trance_num_list.append(2)
if stairs_num > 2:
    a = len(broken_list)
    for i in range(stairs_num - 2):
        key = 0
        left = 0
        right = a
        while left < right:
            midle = floor((left + right) / 2)
            if broken_list[midle] < i + 3:
                left = midle + 1
            elif broken_list[midle] == i + 3:
                key = 1
                break
            else:
                right = midle
        if key:
            trance_num_list.append(0)
        else:
            trance_num_list.\
             append((trance_num_list[-1] + trance_num_list[-2]) % 1000000007)
print(trance_num_list[stairs_num - 1])
N = int(input())

import math

lcm = lambda a, b: a * b // math.gcd(a, b)

print(lcm(2, N))

### FIXED CODE ###

N = int(input())

if N % 2 == 0:
    print(N)
else:
    print(2*N)
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    H,W=map(int,input().split())
    maze=[[_ for _ in input()] for _ in range(H)]

    from collections import deque

    sy, sx = 1,1
    gy, gx = H,W
    sy, sx, gy, gx = sy - 1, sx - 1, gy - 1, gx - 1

    maze = [input() for i in range(H)]
    visited = [[-1] * W for j in range(H)]


    def bfs(maze, visited, sy, sx, gy, gx):
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited
            for j, k in ([1, 0], [0, 1]):
                ny, nx = y + j, x + k
                if 0 <= ny < H and 0 <= nx < W and visited[nx][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])

    for i in range(H):
        for j in range(W):
            if visited[i][j]


    print(bfs(maze, visited, sy, sx, gy, gx))



resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 5
    # dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
    dp = [[INF] * W for _ in range(H)]

    if maze[0][0] == '#':
        dp[0][0] = 1
    else:
        dp[0][0] = 0

    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '#':
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[H - 1][W - 1])


resolve()
def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  visit = [[False]*w for i in range(h)]
  count = h*w
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == "#":
        white.append((i,j))
        count -= 1
        visit[i][j] = True
        
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while count > 0:
   ans += 1
   newwhite = []
   while white:
      x,y = white.pop(0)
      for dx,dy in d:
        nx,ny = x+dx,y+dy
        if nx < 0 or nx >= h or ny < 0 or ny >=w :
         continue 
        elif visit[nx][ny]:continue
          
        if maze[nx][ny] == ".":
          count -= 1
          str_list = list(maze[nx])
          str_list[ny] = "#"
          maze[nx] = "".join(str_list)          
          newwhite.append((nx,ny))
          visit[nx][ny] =True
   white = newwhite
    
  print(ans)
solve()


### FIXED CODE ###


from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        black.append((0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()
a = input().spolit()

if int(a[0]) > int(a[1]):
  print("safe")
else:
  print("unsafe")

### FIXED CODE ###

a = input().split()

if int(a[0]) <= int(a[1]):
  print("unsafe")
else:
  print("safe")
import fractions
n,m=map(int,input().split())
s=list(str(input()))
t=list(str(input()))

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

l=lcm(n, m)
ans=[0]*(l*2)

for i in range(n):
    index=l//n*i+1

    if ans[index]==0:
        ans[index]=s[i]
#print(ans)
for i in range(m):
    index=l//m*i+1
    if ans[index]==0:
        ans[index]=t[i]
    else:
        if t[i]!=ans[index]:
            print(-1)
            exit()
#print(ans)
print(l)


### FIXED CODE ###

from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
#一文字目が違うと無理
gcd_n_m = gcd(n,m)
if gcd_n_m == 1 and s[0] == t[0]:
    print(n*m)
else:
    step_s = n // gcd_n_m
    step_t = m // gcd_n_m
    index_s = 0
    index_t = 0
    while index_s < n and index_t < m:
        if s[index_s] != t[index_t]:
            print(-1)
            exit()
        index_s += step_s
        index_t += step_t
    print(n*m//gcd_n_m)
# coding: utf-8
# Your code here!
# from collections import Counter
# from functools import *

def LI():
    return list(map(int,input().split()))

n,k=LI()
a=[q-1 for q in LI()]

visited=[-1]*n
now=0
visited[now]=0

if k<=2*10**5:
    for i in range(k):
        nxt=a[now]
        now=nxt
    print(now)
    exit()

for i in range(k):
    nxt=a[now]
    now=nxt
    if visited[nxt]==-1:
        visited[nxt]=i
    else:
        m=i-visited[nxt]
        break
now=0
for i in range(k%m+m):
    nxt=a[now]
    now=nxt
print(now)
exit()



### FIXED CODE ###

n,k=map(int,input().split())
a=[0]+list(map(int,input().split()))

MAX_N=2*10**5
b=[1]
visited=[-1]*(n+10)
for i in range(1,2*MAX_N+1):
    nxt=a[b[-1]]
    b.append(nxt)
        
if k<=n:
    print(b[k])
    exit()
# print(b)  
for i,bi in enumerate(b):
    if visited[bi]==-1:
        visited[bi]=i
    else:
        m=i-visited[bi]
        l=visited[bi]
        break
k=k%m

while k<n:
    k+=m
print(b[k])
n,y = (int(_) for _ in input().split())  
a=-1
b=-1
c=-1
for i in range(n+1):
  for j in range(n-i+1):
      if 10000*i+5000*j+1000*(n-i-j+1)==y:
        a=i
        b=j
        c=n-i+j+1
        break

print(a b c)        

### FIXED CODE ###

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

print(a ,b ,c)
n, z, w = map(int, input().split())
a = [int(x) for x in input().split()]

turn = True
p= max(a)
for i in range(n-1):
  if turn:
    if a[i] <= a[i+1]:
      continue
    elif a[i] < z and a[i] != p:
      continue
    else:
      z = a[i]
      turn = False
      if a[i] < z and a[i] == p:
        q = min(a[i+1:])
  else:
    if a[i] >= a[i+1]:
      continue
    elif a[i] > w and a[i] != q:
      continue
    else:
      w = a[i]
      turn = True
      if a[i] > w and a[i] == q:
        p = max(a[i+1:])
if turn:
  z = a[-1]
else:
  w = a[-1]
print(abs(z-w))

### FIXED CODE ###

import sys
from itertools import product
input = sys.stdin.readline

def main():
    n, z, w = map(int, input().split())
    
    a = list(map(int, input().split()))
    
    ans = abs(w-a[-1])
    if n != 1:
        ans = max(ans, abs(a[-2]-a[-1]))
    
    print(ans)
        

    
if __name__ == "__main__":
    main()