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

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

def main():
    s = input()
    K = int(input())

    dict_list = []


    abc_list = 'abcdefghijklmnopqrstuvwxyz'
    
    for abc in abc_list:
        dict_temp = []
        j = 1
        while True:
            for i in range(len(s)):
                if  i + j <= len(s) and s[i] == abc and len(s[i:i+j]) <= K:
                    dict_temp.append(s[i:i+j])
            j += 1
            if j > len(s):
                break
        dict_temp = list(set(dict_temp))
        dict_list += dict_temp
        dict_list.sort()
        if len(dict_list) >= K:
            print(dict_list[K-1])
            break
        
    #print(dict_list)
            

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def main():
    s = input()
    K = int(input())

    a = set()

    for i in range(len(s)):
        for j in range(K):
            a.add(s[i:i+j+1])
            if i + j > len(s):
                break
    a_list = list(a)
    a_list.sort()
    print(a_list[K-1])
            

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

n,k=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>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))
            
print(dp[-1])        


### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    n,k=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>=0:
                dp[i]=min(dp[i],dp[i-j]+abs(H[i]-H[i-j]))
            
    print(dp[-1])        

main()
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [0] * n
for i in range(1, n):
    ans = 1000000000
    for j in range(1, k + 1):
        if i - j >= 0: ans = min(ans, cost[i - j] + abs(h[i] - h[i - j]))
    cost[i] = ans
print(cost[n - 1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
cost = [0] * n
for i in range(1, n):
    ans = 1000000000
    for j in range(1, k + 1):
        if i - j >= 0: ans = min(ans, cost[i - j] + abs(h[i] - h[i - j]))
    cost[i] = ans
print(cost[n - 1])
### BUGGY CODE ###

n, k = map(int, input().split())
aa = tuple(map(int, input().split()))

s = 1
ps = 1
for i in range(n):
    s *= aa[i]
    if i >= k:
        s //= aa[i - k]
        if ps < s:
            print('Yes')
        else:
            print('No')
    ps = s


### FIXED CODE ###

n, k = map(int, input().split())
aa = tuple(map(int, input().split()))

for i in range(k, n):
    if aa[i - k] < aa[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import Counter
import math, copy

def c(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

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

d = Counter(A)

for a in A:
    x = copy.copy(d)
    x[a] -= 1
    ans = 0
    for v in x.values():
        if v >= 2:
            ans += c(v, 2)
    print(ans)

### FIXED CODE ###

from collections import Counter
from scipy.special import comb

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

d = Counter(A)

sum_c = 0
for v in d.values():
    if v >= 2:
        sum_c += comb(v, 2, exact=True)

for a in A:
    x = sum_c - comb(d[a], 2, exact=True) + comb(d[a]-1, 2, exact=True)
    print(x)
### BUGGY CODE ###

from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    flag = 0
    for j,b in enumerate(A):
        if a % b  == 0 and i != j:
            flag = 1
            break
    if flag == 0:
        count += 1
print(count)




### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
M = 1000001
cnt = [0]*M
ans = 0
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x,M,x):
        cnt[i] += 1
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def prime_factor(n):
    p = sieve(n)
    for pi in compress(count(0), p):
        while n % pi == 0:
            n //= pi
            yield pi

from sys import stdin
from itertools import compress, count

readline = stdin.readline

n = int(readline())
print('{}: '.format(n) + ' '.join(map(str, prime_factor(n))))

### FIXED CODE ###

import math
def sieve(n):
    p = [1] * (n + 1)
    p[0] = p[1] = 0
    
    for i in range(math.ceil((n + 1) ** 0.5)):
        if p[i]:
            for j in range(2 * i, len(p), i):
                p[j] = 0
    return p

def prime_factor(n):
    p = sieve(int(n ** 0.5))
    factor = []
    for pi in compress(count(0), p):
        while n % pi == 0:
            n //= pi
            factor.append(pi)

    if n != 1:
        factor.append(n)
    return factor

from sys import stdin
from itertools import compress, count

readline = stdin.readline


n = int(readline())
print('{}: '.format(n) + ' '.join(map(str, prime_factor(n))))
### BUGGY CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        leftA, leftQ = S[:i].count("A"), S[:i].count("?")
        rightC, rightQ = S[i+1:].count("C"), S[i+1:].count("?")
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        count += leftpatt * rightpatt
        count %= mod
print(int(count))

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)
### BUGGY CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy

N,M=map(int, input().split())
A=set([i for i in range(N+1)[1::]])

for _ in range(M):
    L,R=map(int, input().split())
    tmp=set([i for i in range(R+1)[L::]])
    A = A & tmp

print(len(A))

### FIXED CODE ###

# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy

N,M=map(int, input().split())
A=np.array([i for i in range(N+1)[1::]])


minimum = 1
maximum = N

for _ in range(M):
    L,R=map(int, input().split())

    if(R < minimum or maximum < L):
        print(0)
        exit()

    if(minimum < L):
        minimum = L
    if(R < maximum):
        maximum = R

print(maximum - minimum + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
a=[[] for i in range(n)]
p=[]*n
l=[0]*n
ans=[0]*n

def dfs(parent,current,value):
    value += l[current-1]
    ans[current-1] = value
    for i in a[current-1]:
        if i != parent:
            dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,input().split())
    a[t1-1].append(t2)
    a[t2-1].append(t1)
    
for i in range(q):
    t1,t2 = map(int,input().split())
    l[t1-1]+=t2
dfs(-1,1,0)

print(" ".join(map(str,ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

n,q = map(int,readline().split())
a=[[] for i in range(n)]
l=[0 for _ in range(n)]
ans=[0 for _ in range(n)]

def dfs(parent,current,value):
    value += l[current]
    ans[current] = value
    for i in a[current]:
        if i == parent:
            continue
        dfs(current,i,value)


for i in range(n-1):
    t1,t2 = map(int,readline().split())
    a[t1-1].append(t2-1)
    a[t2-1].append(t1-1)
    
for i in range(q):
    t1,t2 = map(int,readline().split())
    l[t1-1]+=t2
dfs(-1,0,0)

print(" ".join(map(str,ans)))
### BUGGY CODE ###

S = input()


MOD = 10**9 + 7

# time complexity: O(|S|)
def focus_on_B(S):
    cuml = {"A": [], 
            "C": [],
            "?": []}
    current_nums = {"A": 0,
                    "C": 0,
                    "?": 0}
    for char in S:
        if char in cuml.keys():
            current_nums[char] += 1
        for key in cuml.keys():
            cuml[key].append(current_nums[key])
    assert len(cuml['A']) == len(S)

    # num_combinations[i]: i番目をBとした時に、可能な組み合わせの数
    num_combinations = [0] * len(S)
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml["A"][i-1]
            Q_L = cuml["?"][i-1]
            C_R = cuml["C"][-1] - cuml["C"][i]
            Q_R = cuml["?"][-1] - cuml["?"][i]
            num_combinations[i] = (A_L * 3**Q_L + Q_L * int(3**(Q_L - 1)))\
                                * (C_R * 3**Q_R + Q_R * int(3**(Q_R - 1)))
            num_combinations[i] %= MOD
        else:
            continue
    print(sum(num_combinations) % MOD)

focus_on_B(S)


### FIXED CODE ###

S = input()

MOD = 10**9 + 7
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S))[::-1]:
    dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
    dp[i][3] %= MOD
    if S[i] == "?":
        dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
        dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
    else:
        dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
        dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
        dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
print(dp[0][0])
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
q = int(input())
count = 0
s = []

for i in range(q):
	count = 0
	b, c = map(int, input().split())
	for a in l:
		if a == b:
			l[count] = c
		count += 1
	s.append(sum(l))

[print(i) for i in s]


### FIXED CODE ###

import collections

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

num = collections.Counter(A)

S = sum(A)
slist = []

for i in range(Q):
	B, C = map(int, input().split())
	numb = num[B]
	S += (C - B) * numb
	num[C] += numb
	num[B] = 0
	slist.append(S)

[print(i) for i in slist]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline

if __name__ == '__main__':
  n,m,k=map(int,input().strip("\n").split())
  A=list(map(int,input().strip("\n").split()))
  B=list(map(int,input().strip("\n").split()))
#  A.append(10**9+1)
#  B.append(10**9+1)

  def dfs(a,b,k,s):
    if k<0:
      return s-1
    if k==0:
      return s
    if a<n:
      ansA=dfs(a+1,b,k-A[a],s+1)
    else:
      ansA=s
    if b<m:
      ansB=dfs(a,b+1,k-B[b],s+1)
    else:
      ansB=s
    return max(ansA,ansB)

  ans=dfs(0,0,k,0)
  print(ans)


### FIXED CODE ###

import sys
from collections import deque
import copy
sys.setrecursionlimit(2147483647)
input = sys.stdin.readline

if __name__ == '__main__':
  n,m,k=map(int,input().strip("\n").split())
  A=list(map(int,input().strip("\n").split()))
  B=list(map(int,input().strip("\n").split()))
  t=sum(B)
  j=m
  ans=0
  for i in range(n+1):
    while j>0 and t>k:
      j-=1
      t-=B[j]
    if t>k:
      break
    ans=max(ans,i+j)
    if i==n:
      break
    t+=A[i]
  print(ans)
### BUGGY CODE ###

from collections import Counter
K, N = map(int, input().split())
mod = 998244353
frac = [1]*5010
for i in range(2,5010):
    frac[i] = i * frac[i-1]%mod
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*pow(frac[b], mod-2, mod)*pow(frac[a-b], mod-2, mod)%mod
A = Counter()
def calc(x):
    if A[x]:
        return A[x]
    res = 0
    for i in range(N//2+1):
        res = (res + (-1)**i*comb(x, i)*comb(N+K-1-2*i, N-2*i))%mod
    A[x] = res
    return res
for j in range(2, 2*K+1):
    print(calc(min(j, (2*K+2-j))//2))

### FIXED CODE ###

from collections import Counter
K, N = map(int, input().split())
mod = 998244353
frac = [1]*5010
for i in range(2,5010):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*5010
for i in range(5010):
    fraci[i] = pow(frac[i], mod-2, mod)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod
A = Counter()
def calc(x):
    if A[x]:
        return A[x]
    res = 0
    for i in range(N//2+1):
        res = (res + (-1)**i*comb(x, i)*comb(N+K-1-2*i, N-2*i))%mod
    A[x] = res
    return res
for j in range(2, 2*K+1):
    print(calc(min(j, (2*K+2-j))//2))
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]
count=0
def niko(x,y,k,ans):
  for i in range(x-2,x+2):
    for j in range(y-2,y+2):
      if 0<=i<w and 0<=j<h:
        if maze[j][i]=="." and (ans[j][i]>k or ans[j][i]==-1):
          ans[j][i]=k
  return ans
ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]

    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if (x==i and y==j):
          continue
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x] or ans[j][i]==-1):
            if (x==i and y==j+1) or (x==i+1 and y==j) or (x==i-1 and y==j) or (x==i and y==j-1):
              qu.append([i,j])
              ans[j][i] = ans[y][x]
            elif ans[j][i]>ans[y][x]+1 or ans[j][i]==-1:
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
#for i in ans:
#  print(*i)
  



### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
### BUGGY CODE ###

# 21:19
n = int(input())
a = list(map(int,input().split()))
ans = 0
count = 1
i = 0
while True:
    if a[i] != count:
        ans += 1
        a.pop(i)
    else:
        count += 1
        i += 1
    if n == ans + i:
        break
if len(a) == 0:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# 21:19
from collections import deque
n = int(input())
a = deque(list(map(int,input().split())))
ans = 0
count = 1
i = 0
while True:
    if a[i] != count:
        ans += 1
        a.popleft()
    else:
        count += 1
        i += 1
    if n == ans + i:
        break
if len(a) == 0:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
import copy
import time
import random

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

D = None
C = None
S = None


def cnt_score(t):
    global D, C, S
    score = 0
    cnt = [-1] * 26

    for i in range(D):
        score += S[i][t[i] - 1]
        minusscore = 0
        cnt[t[i] - 1] = i
        for j in range(26):
            minusscore += (i - cnt[j]) * C[j]
        score -= minusscore
    return score


#def cnt_contest_score(t, contestid):
#    global D, C, S
#    score = 0
#    minusscore = 0
#
#    t = set(t)
#
#    for i in range(D):
#        if i in t:
#            score -= minusscore
#            minusscore = 0
#        else:
#            minusscore += C[contestid]
#
#    score -= minusscore
#
#    return score


def main():
    global D, C, S
    D = int(input())
    C = [int(x) for x in input().split()]
    S = [[int(x) for x in input().split()] for _ in range(D)]

    start = time.time()

    ans = []
    for s in S:
        ans.append(s.index(max(s)) + 1)

    # A = [[None] * COL for j in range(ROW)]

    old_score = cnt_score(ans)
    day = 0
    f = False
    while True:
        new_ans = copy.deepcopy(ans)

        max_sore = old_score
        max_contest = ans[day]
        for i in range(26):
            # time up
            current = time.time()
            if current - start > 1.90:
                f = True
                break

            # main
            new_ans[day] = i + 1
            new_score = cnt_score(new_ans)
            if new_score > old_score:
                max_contest = i + 1
                old_score = new_score
        ans[day] = max_contest
        if f:
            break

        # increment day
        day = (day + 1) % D

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    D = int(input())
    C = [int(x) for x in input().split()]
    S = [[int(x) for x in input().split()] for _ in range(D)]


    for i in range(D):
        print(i % 26 + 1)



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

N, M = map(int, input().split())
ans = 1
if N == 1:
	ans = M

else:
	for i in range(M//N, 0, -1):
		if M%i == 0:
			ans = i
			break

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
d = []
for i in range(1, int(M**0.5)+1):
	if M%i == 0:
		d.append(i)
		d.append(M//i)
d.sort()
for i in range(1,len(d)+1):
	if d[-i] <= M//N:
		print(d[-i])
		exit()
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

u = list(set(A))
c = []
sum = 0
for j in u:
    _ = A.count(j)
    c.append(_)
    sum += int(_ * (_ - 1) / 2)

s = ""
for k in A:
    v = c[u.index(k)]
    s += str(sum - v + 1) + "\n"
print(s)


### FIXED CODE ###

import collections

N = int(input())
A = [int(i) for i in input().split()]

u = collections.Counter(A)
sum = 0
for j, c in u.items():
    sum += int(c * (c - 1) / 2)

s = ""
for k in A:
    s += str(sum - u[k] + 1) + "\n"
print(s)
### BUGGY CODE ###

s,q=[*input()],int(input())
for i in range(q):
  t=input().split()
  if len(t)==1:
    s=s[::-1]
  else:
    if t[1]=='1':
      s.insert(0,t[2])
    else: s.append(t[2])
print(*s,sep='')

### FIXED CODE ###

from collections import deque
s,q=deque([*input()]),int(input())
judge=False
for i in range(q):
  t=input().split()
  if len(t)==1:
    judge = not judge
  else:
    t,f,c=t
    if not judge and f=='1': s.appendleft(c)
    elif not judge and f=='2': s.append(c)
    elif judge and f=='1': s.append(c)
    else: s.appendleft(c)
if judge: s.reverse()
print(*s,sep='')
### BUGGY CODE ###

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

h.sort()
s = []
if k == 0:
    s = h
else:
    for i in range(k):
        s = h[:-k]

print(sum(s))

### FIXED CODE ###

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

h.sort()
s = []
if k == 0:
    s = h
else:
    s = h[:-k]

print(sum(s))
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
i=0
while i<m:
  i+=1
  t=A.index(max(A))
  A[t]=A[t]//2
print(sum(A))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
it = 0
for i in range(M):
    A[it]=A[it]//2
    if it<N-1:
        if A[it]<A[it+1] and A[0]<A[it+1]:
            it+=1
        else:
            A.sort(reverse = True)
            it = 0
    if it == N-1:
        A.sort(reverse = True)
        it = 0
print(sum(A))
### BUGGY CODE ###

s = input()
q = int(input())
hanten = 0
check = 0
for i in range(q):
    l = tuple(map(str, input().split()))
    if l[0] == "1":
        hanten += 1
        check += 1
    else:
        if l[1] == "1":
            if check%2 == 0:
                s = l[2] + s
            else:
                s = s + l[2]
        else:
            if check%2 == 0:
                s = s + l[2]
            else:
                s = l[2] + s

if hanten%2 == 1:
    s = s[::-1]

print(s)

### FIXED CODE ###

s = input()
q = int(input())
hanten = True
atm = ""
kts = ""
for i in range(q):
    l = input().split()
    if l[0] == "1":
        hanten = not hanten
    else:
        if l[1] == "1":
            if hanten:
                atm = l[2] + atm
            else:
                kts = kts + l[2]
        else:
            if hanten:
                kts = kts + l[2]
            else:
                atm = l[2] + atm

ans = atm + s + kts
if hanten == False:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

from collections import deque

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

d = deque()
op = [[-1] * w for i in range(h)]

for i in range(h):
    s = input().rstrip()
    for j in range(len(s)):
        if s[j] == '#':
            d.append((i, j, 0))

while d:
    i, j, step = d.popleft()

    if op[i][j] != -1:
        continue
    else:
        op[i][j] = step

    if i > 0:
        d.append((i-1, j, step+1))
    if i < h-1:
        d.append((i+1, j, step+1))
    if j > 0:
        d.append((i, j-1, step+1))
    if j < w-1:
        d.append((i, j+1, step+1))

print(max([max(op[i]) for i in range(h)]))


### FIXED CODE ###

from collections import deque

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

d = deque()
op = [[-1] * w for i in range(h)]

for i in range(h):
    s = input().rstrip()
    for j in range(len(s)):
        if s[j] == '#':
            d.append((i, j, 0))
            op[i][j] = 0

while d:
    i, j, step = d.popleft()

    for i2, j2 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if 0 <= i2 < h and 0 <= j2 < w:
            if op[i2][j2] == -1:
                d.append((i2, j2, step+1))
                op[i2][j2] = step + 1

print(max([max(op[i]) for i in range(h)]))
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
bcnt=0
for i in range(h):
    bcnt+=s[i].count('#')
dist=[[1000]*w for _ in range(h)]
chk=[[0]*w for _ in range(h)]
r=deque()
r.append([0,0])
dist[0][0]=0
while r:
    x,y=r.popleft()
    chk[y][x]=1
    for dx,dy in d:
        nx=x+dx
        ny=y+dy
        nd=dist[y][x]
        if nx>=0 and nx<=w-1 and ny>=0 and ny<=h-1:
            if chk[ny][nx]==1 or s[ny][nx]=='#':
                continue
            dist[ny][nx]=min(dist[ny][nx],nd+1)
            r.append([nx,ny])
if dist[h-1][w-1]==1000:
    print(-1)
else:
    print(h*w-dist[h-1][w-1]-1-bcnt)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
bcnt=0
for i in range(h):
    bcnt+=s[i].count('#')
dist=[[-1]*w for _ in range(h)]
r=deque()
r.append([0,0])
dist[0][0]=0
while r:
    x,y=r.popleft()
    for dx,dy in d:
        nx=x+dx
        ny=y+dy
        nd=dist[y][x]
        if nx>=0 and nx<=w-1 and ny>=0 and ny<=h-1:
            if dist[ny][nx]>-1 or s[ny][nx]=='#':
                continue
            dist[ny][nx]=nd+1
            r.append([nx,ny])
if dist[h-1][w-1]==-1:
    print(-1)
else:
    print(h*w-dist[h-1][w-1]-1-bcnt)