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

def main():
    s = str(input())
    q = int(input())
    lst = [list(map(str, input().split())) for _ in range(q)]
    switch = 0  # 0が通常　1が前

    str_lst = [s]
    for i in range(q):

        if lst[i][0] == '1':
            switch = 1 - switch

        else:
            f = lst[i][1]
            c = lst[i][2]

            if f == '1':  # 先頭に追加

                if switch == 0:
                    str_lst.insert(0, c)

                else:
                    str_lst.append(c)

            else:

                if switch == 0:
                    str_lst.append(c)

                else:
                    str_lst.insert(0, c)

    answer = ''.join(str_lst)
    if switch == 1:
        answer = answer[::-1]

    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = str(input())
    q = int(input())
    lst = [list(map(str, input().split())) for _ in range(q)]
    switch = 0  # 0が通常　1が前

    str_lst = [s]
    front_lst = []
    for i in range(q):

        if lst[i][0] == '1':
            switch = 1 - switch

        else:
            f = lst[i][1]
            c = lst[i][2]

            if f == '1':  # 先頭に追加

                if switch == 0:
                    front_lst.append(c)

                else:
                    str_lst.append(c)

            else:

                if switch == 0:
                    str_lst.append(c)

                else:
                    front_lst.append(c)

    front = ''.join(front_lst)
    front = front[::-1]
    after = ''.join(str_lst)
    answer = front + after

    if switch == 1:
        answer = answer[::-1]

    print(answer)


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

from collections import Counter
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[list(map(int, input().split())) for i in range(m)]
b.sort(key=lambda x:x[1])
c=Counter(a)
for x,y in b:
    for i in sorted(c):
        if y<=i or x==0:break
        if c[i]>x:
            c[i]-=x
            c[y]+=x
            x=0
        else:
            c[y]+=c[i]
            x-=c[i]
            del c[i]
ans=0
for i in c:
    ans+=c[i]*i
print(ans)

### FIXED CODE ###

from collections import Counter
n,m=map(int, input().split())
a=list(map(int, input().split()))
c=Counter(a)
for i in range(m):
    x,y=map(int, input().split())
    c[y]+=x
ans=0
for i in sorted(c, reverse=True):
    if n>c[i]:
        ans+=c[i]*i
        n-=c[i]
    else:
        ans+=n*i
        n=0
    if n<=0:break
print(ans)
### BUGGY CODE ###

from bisect import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
b_c= [0]*n
for i  in range(n-2):
    a = l[i]
    k = 0
    for j in range(i+1,n-1):
        b = l[j]
        max_c = a+b-1
        add_k = bisect(l[j+k+1:],max_c)
        k += add_k
        ans += k
        k = max(k-1,0)
        
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans = 0
for i  in range(n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        k = bisect_left(l,a+b)
        ans += k-j-1
print(ans)
### BUGGY CODE ###

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

MOD = 10**9 + 7
m = 2*10**5
mm = 2** m

def cmb(n,r,mod):        
    ret=1
    div = min(r,n-r)
    for i in range(div):        
        ret=ret*(n-i)*pow(div-i,mod-2,mod)%mod
        
    return ret % mod

ans = 1
for _ in range(n // m):
  ans = (ans * mm) % MOD

ans = (ans * 2**(n % m)) % MOD  
    
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)

### FIXED CODE ###

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

MOD = 10**9+7

def cmb(n,r,mod):        
    ret=1
    div = min(r,n-r)
    for i in range(div):        
        ret=ret*(n-i)*pow(div-i,mod-2,mod)%mod
        
    return ret % mod

ans = 1
ans = ans * pow(2,n,MOD)
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

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

import re
def main():
    S = input()
    S = input()
    cnt = 0

    for i in range(1000):
        PIN = "{:03d}".format(i)
        pattern = '^.*' + PIN[0] + '.*' + PIN[1] + '.*' + PIN[2] + '.*$' 
        repatter = re.compile(pattern)
        if repatter.match(S):
            cnt+=1
        
    print(cnt)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import re
def main():
    S = input()
    S = input()
    l = len(S)
    cnt = 0


    for i in range(10):
        iti = 0
        iti = S.find(str(i))
        if iti == -1 :
            continue
        for j in range(10):
            s = S[iti+1:]
            itj = s.find(str(j))
            if itj == -1 :
                continue
            for k in range(10):
                t = s[itj+1:]
                itk = t.find(str(k))
                if itk != -1 :
                    cnt += 1

    print(cnt)



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

from fractions import gcd
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
max_gcd = 0
for i in range(n):
    if i == 0:
        Gcd = reduce(gcd,a[1:])
    elif i == n-1:
        Gcd = reduce(gcd,a[:n-1])
    else:
        Gcd = reduce(gcd,a[:i] + a[i+1:])
    max_gcd = max(max_gcd,Gcd)
print(max_gcd)

### FIXED CODE ###

from fractions import gcd
import numpy as np
n = int(input())
a = list(map(int, input().split()))
l = np.zeros(n)
r = np.zeros(n+1)
r[n] = 0
for i in range(n):
    if i == 0:
        l[0] = 0
    else:
        l[i] = gcd(l[i-1],a[i-1])
for j in range(n-1, -1, -1):
        r[j] = gcd(r[j+1],a[j])
m = 0
for i in range(n):
    m = max(gcd(l[i],r[i+1]),m)
print(int(m))
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

for i in range(N):
    A_ = [A[j] for j in range(N) if i != j]
    print(max(A_))
    


### FIXED CODE ###

N = int(input())
A, A_sorted = [], []
for i in range(N):
    x = int(input())
    A.append(x)
    A_sorted.append(x)
A_sorted.sort()
vmax, vmax2 = A_sorted[-1], A_sorted[-2]

for i in range(N):
    x = A[i]
    if vmax == x:
        print(vmax2)
    else:
        print(vmax)
### BUGGY CODE ###

import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

N, *S = map(str, read().split())
N = int(N)
x = 0
answer = 0
for y in range(N):
    for i, j in product(range(N), repeat=2):
        if S[(i + x) % N][(j + y) % N] != S[(j + x) % N][(i + y) % N]:
            break
    else:
        answer += N

print(answer)


### FIXED CODE ###

import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

N, *S = map(str, read().split())
N = int(N)
x = 0
answer = 0
for y in range(N):
    for i, j in product(range(N), repeat=2):
        if S[(i + x) % N][(j + y) % N] != S[(j + x) % N][(i + y) % N]:
            break
    else:
        answer += N

print(answer)
### BUGGY CODE ###

h, w = map(int, input().split())
S = [list(input()) for i in range(h)]

L = [[0 for j in range(w)] for i in range(h)]
R = [[0 for j in range(w)] for i in range(h)]
U = [[0 for j in range(w)] for i in range(h)]
D = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        ri, rj = h-1-i, w-1-j
        if S[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
        if S[ri][rj] == '.':
            if rj == w-1:
                R[ri][rj] = 1
            else:
                R[ri][rj] = R[ri][rj+1] + 1
            if ri == h-1:
                D[ri][rj] = 1
            else:
                D[ri][rj] = D[ri+1][rj] + 1

ans = 0

for i in range(h):
    for j in range(w):
        ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
S = [list(input()) for i in range(h)]

L = [[0 for j in range(w)] for i in range(h)]
R = [[0 for j in range(w)] for i in range(h)]
U = [[0 for j in range(w)] for i in range(h)]
D = [[0 for j in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        ri, rj = h-1-i, w-1-j
        if S[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
        if S[ri][rj] == '.':
            if rj == w-1:
                R[ri][rj] = 1
            else:
                R[ri][rj] = R[ri][rj+1] + 1
            if ri == h-1:
                D[ri][rj] = 1
            else:
                D[ri][rj] = D[ri+1][rj] + 1

ans = 0

for i in range(h):
    for j in range(w):
        ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

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

count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                count += 1
print(count)

### FIXED CODE ###

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

count = 0
for x in range(K+1):
    if S-x<=2*K and S-x>=0:
        for y in range(K+1):
            if S-x-y<=K and S-x-y>=0:
                count += 1
#                 for z in range(K+1):
#                     if x+y+z==S:
#                         count += 1
print(count)
### BUGGY CODE ###

from random import randint


class RollingHash(object):
    mod = 1 << 61 - 1
    base = randint(2, mod - 2)

    def __init__(self, s):
        """
        sに関するローリングハッシュを構築する O(|s|)
        """
        self.s = s
        self.pw = pw = [1] * (len(s) + 1)

        l = len(s)
        self.h = h = [0] * (l + 1)

        v = 0
        for i in range(l):
            h[i + 1] = v = (v * self.base + ord(s[i])) % self.mod
        v = 1
        for i in range(l):
            pw[i + 1] = v = v * self.base % self.mod

    def hash(self, l, r):
        """ s[l:r] のhash (rはexclusive) O(1) """
        return (self.h[r] - self.h[l] * self.pw[r - l]) % self.mod

    def contains(self, t):
        """
        sがtを含むか O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return False
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                return True
        return False

    def count(self, t):
        """
        s中に含まれるtの数をカウントする O(|s|-|t|)
        tはRollingHashオブジェクト
        """
        slen, tlen = len(self.s), len(t.s)
        if slen < tlen:
            return 0
        cnt = 0
        th = t.hash(0, tlen)
        for i in range(slen - tlen + 1):
            if th == self.hash(i, i + tlen):
                cnt += 1
        return cnt

    def getLCP(self, a, b):
        l = min(len(self.s) + 1 - a, len(self.s) + 1 - b)
        low, high = 0, l
        while high - low > 1:
            mid = (low + high) >> 1
            if self.hash(a, a + mid) != self.hash(b, b + mid):
                high = mid
            else:
                low = mid
        return low


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

rh = RollingHash(S)
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        lcp = rh.getLCP(i, j)
        lcp = min(lcp, j - i)
        ans = max(ans, lcp)
print(ans)

### FIXED CODE ###

def z_algorithm(S):
    """
    文字列の各インデックスについて「SとS[i: len(S) - 1]の最良共通接頭辞の長さ」を求め、
    それを記録した配列Aを O(|S|) で作成します。
    """
    A = [-1 for _ in range(len(S))]
    A[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i + j < len(S) and S[j] == S[i + j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(S) and k + A[k] < j:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    return A


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

ans = 0
for i in range(N - 1):
    s = S[i:]
    A = z_algorithm(s)
    A = [min(i, a) for i, a in enumerate(A)]  # 重複する区間の除去
    ans = max(ans, max(A[1:]))
print(ans)
### BUGGY CODE ###

import numpy as np

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = np.zeros(n, dtype=np.int)
dp[0] = 1
for i in range(n-1):
  for j in range(k):
    dp[i + left[j] : i + right[j] + 1] += dp[i]
    dp[i + left[j] : i + right[j] + 1] %= mod
print(dp[-1])

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
  for j in range(k):
    dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
    dp[i] %= mod
  dp[i] = (dp[i-1] + dp[i]) % mod
print((dp[n] - dp[n-1]) % mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        count += 1
        a.append([int(i) for i in input().split(",")])
    except EOFError:
        break
dim = int(count/2)
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    global dp_
    if dp_[i][j]:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))


### FIXED CODE ###

from copy import copy
import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        a.append([int(i) for i in input().split(",")])
        count += 1
    except EOFError:
        break
dim = int(count/2)+1
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    global dp_
    if dp_[i][j] is True:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))
### BUGGY CODE ###

from collections import Counter
h,w=map(int,input().split())
#a=[list(input()) for i in range(w)]
a=[]
flag=True
for i in range(h):
  a+=list(input())
ca=Counter(a)
if h%2==0 and w%2==0:
  for i in ca:
    if ca[i]%4!=0:
      flag=False
      print('No')
      break
  if flag:
    print('Yes')

elif h%2!=0 and w%2!=0:
  yon=(h-1)*(w-1)
  ni=h*w-yon-1
  iti=1
  for i in ca:
    while ca[i]>0:
      if iti<0:
        break
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      elif iti>0:
        iti-=1
        ca[i]-=1
  if yon==0 and ni==0 and iti==0:
    print('Yes')
  else:
    print('No')
else:
  if h%2==0:
    yon=(h)*(w-1)
  else:
    yon=(h-1)*(w)
  ni=h*w-yon
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      else:
        break
  if yon==0 and ni==0:
    print('Yes')
  else:
    print('No')
  
  

### FIXED CODE ###

from collections import Counter
h,w=map(int,input().split())
#a=[list(input()) for i in range(w)]
a=[]
flag=True
for i in range(h):
  a+=list(input())
ca=Counter(a)
if h%2==0 and w%2==0:
  for i in ca:
    if ca[i]%4!=0:
      flag=False
      print('No')
      break
  if flag:
    print('Yes')

elif h%2!=0 and w%2!=0:
  yon=(h-1)*(w-1)
  ni=h*w-yon-1
  iti=1
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      elif iti>0:
        iti-=1
        ca[i]-=1
      else:
        break
  if yon==0 and ni==0 and iti==0:
    print('Yes')
  else:
    print('No')
else:
  if h%2==0:
    yon=(h)*(w-1)
  else:
    yon=(h-1)*(w)
  ni=h*w-yon
  for i in ca:
    while ca[i]>0:
      if ca[i]%4==0 and yon>0:
        ca[i]-=4
        yon-=4
      elif ca[i]%2==0 and ni>0:
        ni-=2
        ca[i]-=2
      else:
        break
  if yon==0 and ni==0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

s=str(input())
q=int(input())
now = 0
mae,usiro="",""
for _ in range(q):
  lis = list(map(str,input().split()))
  if int(lis[0]) == 1:
    now = (now+1)%2
  else:
    if (int(lis[1])+now)%2 == 1:
      mae = lis[2]+mae
    else:
      usiro= usiro +lis[2]
s = mae+s+usiro
if now ==0:
  for i in range(len(s)):
    print(s[i],end="")
else:
  for i in range(len(s)):
    print(s[-i-1],end="")
    
  


### FIXED CODE ###

s=str(input())
q=int(input())
now = 0
mae,usiro="",""
for _ in range(q):
  lis = list(map(str,input().split()))
  if int(lis[0]) == 1:
    now = (now+1)%2
  else:
    if (int(lis[1])+now)%2 == 1:
      mae = lis[2]+mae
    else:
      usiro= usiro +lis[2]
s = mae+s+usiro
if now ==0:
  print(s)
else:
  print(s[::-1])
### BUGGY CODE ###

import copy
H, W, K = map(int, input().split())
C = [[0] * W for i in range(H)]
for i in range(H):
  s = str(input())
  for j in range(W):
    C[i][j] = int(s[j])
  
def delete(mass, s, t):
  #ここでは、mass[s][t]を試す
  mass[s][t] = 0
  #print(mass)
  score = 0#score
  p = -1
  time = -1#何回目の消滅か
  while p < 1:#消せるものがある間
    this = 0
    for i in range(H):
      now = 1
      for j in range(1, W):
        if (mass[i][j] == mass[i][j - 1]) and (mass[i][j] != 0):
          now += 1
        else:
          if now >= K:
            this += 1
            score += (2 ** time) * now * mass[i][j - 1]
            for k in range(j - now, j):
              mass[i][k] = 0
          now = 1
       # print(mass)
      if now >= K:
        this += 1
        score += (2 ** time) * now * mass[i][j - 1]
        for k in range(j - now + 1, j + 1):
          mass[i][k] = 0
    #print(mass)
    if this == 0:
      p += 1
    #落とすところ
    for i in range(1, H + 1):
      for j in range(W):
        if (mass[H - i][j] == 0) and (i != H):
          k = 1
          while (mass[H - i - k][j] == 0) and (k + i < H):
            k += 1
          mass[H - i][j] = mass[H - i - k][j]
          mass[H - i - k][j] = 0
    time += 1
  return score

ans = 0
for i in range(H):
  for j in range(W):
    D = copy.deepcopy(C)
    ans = max(ans, delete(D, i, j))
  
print(ans)
  






### FIXED CODE ###

import copy
H, W, K = map(int, input().split())
C = [[0] * W for i in range(H)]
for i in range(H):
  s = str(input())
  for j in range(W):
    C[i][j] = int(s[j])
  
def delete(mass, s, t):
  #ここでは、mass[s][t]を試す
  mass[s][t] = 0
  #print(mass)
  score = 0#score
  p = -1
  time = -1#何回目の消滅か
  while p < 1:#消せるものがある間
    this = 0
    for i in range(H):
      now = 1
      for j in range(1, W):
        if (mass[i][j] == mass[i][j - 1]) and (mass[i][j] != 0):
          now += 1
        else:
          if now >= K:
            this += 1
            score += (2 ** time) * now * mass[i][j - 1]
            for k in range(j - now, j):
              mass[i][k] = 0
          now = 1
       # print(mass)
      if now >= K:
        this += 1
        score += (2 ** time) * now * mass[i][j - 1]
        for k in range(j - now + 1, j + 1):
          mass[i][k] = 0
    #print(mass)
    if this == 0:
      p += 1
    #落とすところ
    for i in range(1, H + 1):
      for j in range(W):
        if (mass[H - i][j] == 0) and (i != H):
          k = 1
          while (mass[H - i - k][j] == 0) and (k + i < H):
            k += 1
          mass[H - i][j] = mass[H - i - k][j]
          mass[H - i - k][j] = 0
    time += 1
  return score

ans = 0
for i in range(H):
  for j in range(W):
    D = copy.deepcopy(C)
    ans = max(ans, delete(D, i, j))
  
print(ans)
### BUGGY CODE ###

n = int(input())
data_list = [input() for i in range(n)]
data_list.sort()


data_set = set(data_list)
sorted_list = sorted(data_set)

count_list = [0] * len(sorted_list)

for i in range(len(sorted_list)):
    for j in range(len(data_list)):
        if sorted_list[i] == data_list[j]:
            count_list[i] +=1

max_indexes = [i for i, x in enumerate(count_list) if x == max(count_list)]

for i in range(len(max_indexes)):
    print(sorted_list[max_indexes[i]])

### FIXED CODE ###

import collections

n = int(input())
data_list = [input() for i in range(n)]
data_list.sort()

count_dict = collections.Counter(data_list)

max_val = max(count_dict.values())
max_keys = [key for key in count_dict if count_dict[key] == max_val]

max_keys.sort()

for i in range(len(max_keys)):
    print(max_keys[i])
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
import numpy as np
p = np.array(p)
p = (p + 1)/2
ans = -1
for i in range(N-K+1):
  a = np.sum(p[i:i+K])
  if a > ans:
    ans = a
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
import numpy as np
p = np.array(p)
p = (p + 1)/2
ans = -1
for i in range(N-K+1):
  if i == 0:
    a = np.sum(p[:K])
  else:
    a = (a-p[i-1]+p[i+K-1])
  if a > ans:
    ans = a
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC78 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,z,w = LI()
a = LI()
que = deque(a)
tmp1 = que.popleft()
tmp2 = w
turn = 0
cnt = 0
while que:
    if turn == 0:
        if tmp1 <= que[0]:
            tmp1 = que.popleft()
        else:
            turn = 1
    else:
        if tmp2 >= que[0]:
            tmp2 = que.popleft()
        else:
            turn = 0
    cnt += 1
    if cnt > n:
        print(abs(tmp1 - tmp2))
print(abs(tmp1-tmp2))


### FIXED CODE ###

#!/usr/bin/env python3
#ABC78 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,z,w = LI()
a = LI()
if n == 1:
    print(abs(a[-1] - w))
else:
    print(max(abs(a[-1]-w),abs(a[-2]-a[-1])))
### BUGGY CODE ###

s=input()
k=int(input())
#s=list(input())

t=[]
d=dict()
di=0
for i in range(len(s)):
    for j in range(i,len(s)):
        if s[i:j+1] not in d:
            di=di+0
            d[s[i:j+1]]=di
            
d_sorted = sorted(d.items(), key=lambda x:x[0])
            
astr=d_sorted[k-1][0]
        
print(astr)   

### FIXED CODE ###

s=input()
k=int(input())
#s=list(input())

#t=[]
#for kk in range(k):
#    t.append(s)

t=["zzzzz"]*k

for i in range(len(s)):
    for j in range(i,min(len(s),i+k)):
        sij=s[i:j+1]
        for kk in range(k):
            if t[kk]==sij:
                break
        if t[kk]>sij:
            t[kk]=sij
            t.sort()
        
print(t[k-1])  
#print(t)