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

n = int(input())
s = input()

R = [0]*n # R[i] := i文字目より右にある'R'の個数
G = [0]*n
B = [0]*n

# R
for i in range(n-2, -1, -1):
    if s[i+1] == 'R':
        R[i] = R[i+1] + 1
    else:
        R[i] = R[i+1]
# G
for i in range(n-2, -1, -1):
    if s[i+1] == 'G':
        G[i] = G[i+1] + 1
    else:
        G[i] = G[i+1]
# B
for i in range(n-2, -1, -1):
    if s[i+1] == 'B':
        B[i] = B[i+1] + 1
    else:
        B[i] = B[i+1]

cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] != s[j]:
            Set = set((s[i], s[j]))
            if Set == set(('R', 'G')):
                cnt += B[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'B':
                        cnt -= 1
            elif Set == set(('G', 'B')):
                cnt += R[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'R':
                        cnt -= 1
            else:
                cnt += G[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'G':
                        cnt -= 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

R = [0]*n # R[i] := i文字目より右にある'R'の個数
G = [0]*n
B = [0]*n

# R
for i in range(n-2, -1, -1):
    if s[i+1] == 'R':
        R[i] = R[i+1] + 1
    else:
        R[i] = R[i+1]
# G
for i in range(n-2, -1, -1):
    if s[i+1] == 'G':
        G[i] = G[i+1] + 1
    else:
        G[i] = G[i+1]
# B
for i in range(n-2, -1, -1):
    if s[i+1] == 'B':
        B[i] = B[i+1] + 1
    else:
        B[i] = B[i+1]

cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] != s[j]:
            Set = set((s[i], s[j]))
            if Set == set(('R', 'G')):
                cnt += B[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'B':
                        cnt -= 1
            elif Set == set(('G', 'B')):
                cnt += R[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'R':
                        cnt -= 1
            else:
                cnt += G[j]
                if j+(j-i) < n:
                    if s[j+(j-i)] == 'G':
                        cnt -= 1
print(cnt)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
cnt=0
for i in range(n):
    if min(A[:i+1])==A[i]:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
cnt=0
x=A[0]
for i in range(n):
    if A[i]<=x:
        cnt+=1
        x=min(x,A[i])
print(cnt)
### BUGGY CODE ###

n,k = map(int,input().split())
xyl = []
for _ in range(n):
    x,y = map(int,input().split())
    xyl.append((x,y))

ans = float("inf")
for i in range(n):
    for j in range(i+1, n):
        for h in range(n):
            for g in range(h+1, n):
                x1 = min(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                x2 = max(xyl[i][0], xyl[j][0], xyl[h][0], xyl[g][0])
                y1 = min(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][1])
                y2 = max(xyl[i][1], xyl[j][1], xyl[h][1], xyl[g][1])
                cnt = 0
                for p in range(n):
                    if x1 <= xyl[p][0] <= x2 and  y1 <= xyl[p][1] <= y2:
                        cnt += 1
                        if cnt == k:
                            ans = min(ans, (x2 - x1) * (y2 - y1))
                            continue




print(ans)


### FIXED CODE ###

N, K = list(map(int, input().split()))
P = sorted([tuple(map(int, input().split())) for _ in range(N)])

ans = 1e30
for lx in range(N):
    for rx in range(lx+K, N+1):
        Q = sorted(P[lx:rx], key=lambda x:x[1])
        for ly in range(len(Q)):
            R = Q[ly:ly+K]
            if len(R)>=K: ans = min(ans, (P[rx-1][0]-P[lx][0])*(R[-1][1]-R[0][1]))
print(ans)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
lst = list(map(int, input().split()))
max = 0
a = 0
for i in range(n-k+1):
  for j in range(k):
    a += lst[i+j]
  if max < a:
    max = a
  a = 0
print((max+k)/2)

### FIXED CODE ###

n, k = list(map(int, input().split()))
lst = list(map(int, input().split()))
sum = 0
for j in range(k):
  sum += lst[j]
max = sum
for i in range(n-k):
  sum = sum-lst[i]+lst[i+k]
  if max < sum:
    max = sum
print((max+k)/2)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
# l = list()
# r = list()
s_list = list()
for i in range(q):
    l_i, r_i = map(int, input().split())
    # l.append(l_i)
    # r.append(r_i)
    s_list.append(s[l_i-1:r_i])

for i in range(q):
    print(s_list[i].count('AC'))



### FIXED CODE ###

def main():
    # n, q = map(int, input().split())
    # s = input()
    # # l = list()
    # # r = list()
    # s_list = list()
    # # s_tuple = tuple()
    # for _ in range(q):
    #     l_i, r_i = map(int, input().split())
    #     # l.append(l_i)
    #     # r.append(r_i)
    #     s_list.append(s[l_i - 1:r_i])
    #     # s_tuple = s_tuple + tuple(s[l_i - 1:r_i])
    # 
    # s_tuple = tuple(s_list)
    # 
    # for i in s_tuple:
    #     print(i.count('AC'))
    N, Q = map(int, input().split())
    S = input()
    cnt = [0] * (N + 1)
    for i in range(N):
        cnt[i + 1] = cnt[i] + (1 if S[i:i+2] == 'AC' else 0)
    for i in range(Q):
        l, r = map(int, input().split())
        print(cnt[r - 1] - cnt[l - 1])


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

def main():
    s = [-1 if c == '?' else int(c) for c in list(input())]
    MOD = 10 ** 9 + 7
    n = len(s)
    dp = [[0] * 13 for _ in range(n)]

    if s[n-1] == -1:
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][s[n-1]] = 1
    for i in range(1, n):
        i10 = 10 ** i % 13
        c = s[n-i-1]
        for k in range(13):
            if c == -1:
                for j in range(10):
                    m = (i10 * j + k) % 13
                    dp[i][m] += dp[i-1][k]
                    dp[i][m] %= MOD
            else:
                m = (i10 * c + k) % 13
                dp[i][m] += dp[i-1][k]
                dp[i][m] %= MOD
    print(dp[n-1][5])


main()


### FIXED CODE ###

def main():
    s = [-1 if c == '?' else int(c) for c in list(input())]
    MOD = 10 ** 9 + 7
    n = len(s)
    dp = [[0] * 13 for _ in range(n)]

    if s[n-1] == -1:
        for j in range(10):
            dp[0][j] = 1
    else:
        dp[0][s[n-1]] = 1
    i10 = 1
    for i in range(1, n):
        i10 = (10 * i10) % 13
        c = s[n-i-1]
        for k in range(13):
            if c == -1:
                for j in range(10):
                    m = (i10 * j + k) % 13
                    dp[i][m] += dp[i-1][k]
                    dp[i][m] %= MOD
            else:
                m = (i10 * c + k) % 13
                dp[i][m] += dp[i-1][k]
                dp[i][m] %= MOD
    print(dp[n-1][5])


main()
### BUGGY CODE ###

n,x,y = map(int,input().split())

r = [[] for i in range(n)]

for i in range(n):
    if i==0:
        r[i].append(i+1)
    elif i==n-1:
        r[i].append(n-2)
    else:
        r[i].append(i-1)
        r[i].append(i+1)

#x,yの間に道を追加
x,y = x-1,y-1

r[x].append(y)
r[y].append(x)

from collections import deque

q = deque([0])

dist = [-1]*n
dist[0]=0

ans=[]
for p in range(n):
    
    dist = [-1]*n
    dist[p]=0
    q = deque([p])

    while q:
        v = q.popleft()

        for j in r[v]:
            if dist[j]==-1:
                dist[j] = dist[v] + 1
                q.append(j)
    
    ans.append(dist)


d={}
for k in range(1,n+1):
    d[k]=0


for i in range(n):
    for j in range(i+1,n):
        d[ans[i][j]]+=1

for k in range(n-1):
    print(d[k+1])


### FIXED CODE ###

n,x,y = map(int,input().split())

x,y = x-1,y-1

d={}
for k in range(1,n):
    d[k]=0


for i in range(n):
    for j in range(i+1,n):
     
        dist=min(abs(i-j) , abs( i - x ) + 1 + abs(y - j) ,abs( i - y ) + 1 + abs(x - j))

        d[dist]+=1

for k in range(1,n):
    print(d[k])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

def f(data, q, cnd):
    res = 0
    for i in range(q):
        a, b, c, d = data[i]
        if int(cnd[b])-int(cnd[a]) == c:     
            res += d
    return res

def main():
    n, m, q = map(int, readline().split())
    data = []
    for _ in range(q):
        a, b, c, d = map(int, readline().split())
        a-=1
        b-=1
        data.append((a, b, c, d))  
    
    cnd = []
    dq = deque() 
    for i in range(1, m+1):
        dq.append(i)
    while len(dq)>0:
        v = dq.popleft() 
        u = v%10 
        for i in range(u, m+1):
            nx = v*10+i
            if len(str(nx)) == n:
                cnd.append(str(nx))
            else:
                dq.append(nx)
    ans = 0
    for i in cnd:
        ans = max(ans, f(data, q, i))
    print(ans) 
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement


def getPoint(data, A, q):
    res = 0
    for i in range(q):
        a, b, c, d = data[i]
        if A[b]-A[a] == c:
            res += d
    return res

def main():
    n, m, q = map(int, readline().split())    
    data = []
    for _ in range(q):
        a, b, c, d = map(int, readline().split())
        a-=1
        b-=1
        data.append((a, b, c, d))
    p = [int(i) for i in range(1, m+1)]
    ans = 0
    for A in combinations_with_replacement(p, n):
        ans = max(getPoint(data, A, q), ans)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

#C問題
N = int(input())

M = 3500
flag = 0
for k in range(1,3500):
    for h in range(1,3500):
        bunbo = 4*k*h-k*N-h*N
        bunshi = N*k*h
        if bunbo != 0 and bunshi%bunbo == 0:
            w = bunshi//bunbo
            if w >= 0:
            	print(k,h,w)
            	flag = 1
            	break
    if flag == 1:
        break
            


### FIXED CODE ###

#C問題
N = int(input())

M = 3500
flag = 0
for k in range(1,3500):
    for h in range(1,3500):
        bunbo = 4*k*h-k*N-h*N
        bunshi = N*k*h
        if bunbo != 0 and bunshi%bunbo == 0:
            w = bunshi//bunbo
            if w >= 0:
            	print(k,h,w)
            	flag = 1
            	break
    if flag == 1:
        break
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for i in range(n):
  x = a.index(i+1)
  ans[i] = str(x+1)
print(" ".join(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
for i in range(n):
  ans[a[i]-1] += i+1
  ans[a[i]-1] = str(ans[a[i]-1])
print(" ".join(ans))
### BUGGY CODE ###

N, M = map(int,input().split())
lst=[None]*M
for i in range(M):
    p, S=input().split()
    lst[i]=(int(p), S)

#print(N, M, lst)
#count AC
AC_count = 0
WA_count = 0
AC_check=[None]*N
for i in range(M-1,-1,-1):
    #print(i)
    if lst[i][1]=='AC':
        AC_check[lst[i][0]-1]=i
#print(AC_check)


for i in range(1, N+1):
    if AC_check[i-1]!=None:
        AC_count += 1
        WA_count+=lst[:AC_check[i-1]].count((i, 'WA'))

print(AC_count, WA_count)

### FIXED CODE ###

N, M = map(int,input().split())
lst=[None]*M
for i in range(M):
    p, S=input().split()
    lst[i]=(int(p), S)

stop_set=set()

WA_count=0
AC_count=0
from collections import defaultdict
WA_dict = defaultdict(lambda: 0)

for el in lst:
    if not el[0] in stop_set:
        if el[1]=='AC':
            AC_count+=1
            stop_set.add(el[0])
        else:
            WA_dict[el[0]] +=1
#print(dict(WA_dict))

new_set=set(WA_dict.keys())&stop_set
#print(new_set)
WA_count=sum([WA_dict[i] for i in new_set])
print(AC_count, WA_count)
### BUGGY CODE ###

import bisect

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

SUM = 0
for i,a in enumerate(A):
    for j,b in enumerate(A[i+1:]):
        SUM += bisect.bisect_left(A[i+j+2:], a+b)

print(SUM)


### FIXED CODE ###

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

for i in range(N-1,0,-1):
    l = 0
    r = i -1
    while(l< r):
        if (A[l] + A[r] >A[i]):
            count += (r-l)
            r -= 1
        else:
            l += 1
print(count)
### BUGGY CODE ###

def string_formation(s,q,ql):
    len_ql = len(ql)
    for i in range(len_ql):
        t = ql[i][0]
        #print(br)
        if t == "1":
            s = list(reversed(s))
            #print(s)
        elif t == "2":
            f = ql[i][1]
            c = list(ql[i][2])
            if f == "1":
                s = c + s
            elif f == "2":
                s = s + c
    return s

if __name__ == '__main__':
    s = input()
    q = int(input())
    ql = [list(input().split()) for _ in range(q)]

    ans = string_formation(list(s),q,ql)
    print(''.join(ans))


### FIXED CODE ###

from collections import deque

def msf(s,queries):
    queue = deque(s)
    addl = queue.appendleft
    addr = queue.append
    is_reversed = 0

    for query in queries:
        if query[0] == '1':
            is_reversed ^= 1
            addl,addr = addr,addl
        elif query[0] == '2':
            f = query[1]
            c = query[2]
            if f == '1':
                addl(c)
            elif f == '2':
                addr(c)
    return ''.join(queue) if not is_reversed else ''.join(reversed(queue))

if __name__ == '__main__':
    s = list(input())
    q = int(input())
    ql = [input().split() for i in range(q)]
    print(msf(s,ql))
### BUGGY CODE ###

N, K = map(int, input().split())
li = [list(map(int, input().split())) for n in range(N)]

a = []

for i in li:
  b = [i[0]] * i[1]
  a.extend(b)

a.sort()

print(a[K-1])

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)

N, K = map(int, input().split())
li = [list(map(int, input().split())) for n in range(N)]

for i in li:
  d[i[0]] += i[1]
  
count = 0
new = sorted(d)

for i in new:
  count += d[i]
  
  if count >= K:
    print(i)
    break
### BUGGY CODE ###

from bisect import bisect_left

N=int(input())
A=list()
for i,a in enumerate(input().split(),1):
  A.append((int(a),i))
A.sort()

t=0
k=[a[0] for a in A]
for i in range(0,bisect_left(k,N)):
  for j in range(0,bisect_left(k,N-A[i][0])):
    if A[i][0]+A[j][0]==abs(A[i][1]-A[j][1]):
      t+=1
print(t//2)


### FIXED CODE ###

import collections

N=int(input())
L,R=[0]*N,[0]*N
for i,a in enumerate(input().split()):
  L[i],R[i]=i+int(a)+1,i+1-int(a)

l=collections.Counter(L)
r=collections.Counter(R)
t=0
for i in l.keys():
  t+=l[i]*r[i]

print(t)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    B,C=map(int,input().split())
    for j in range(B):
        A.append(C)
A.sort(reverse=True)
sum=0
for i in range(N):
    sum+=A[i]
print(sum)

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
D=[]
for i in range(M):
    (B,C)=map(int,input().split())
    D.append((C,B))
D.append((0,0))
D.sort(reverse=True)
i=0
j=0
count=0
sum=0
while count<N:
    if A[i]>=D[j][0]:
        sum+=A[i]
        i+=1
        count+=1
    else:
        sum+=D[j][0]*(min(N-count,D[j][1]))
        count+=D[j][1]
        j+=1
print(sum)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**7)
N, T = map(int, input().split())
A = []
for _ in range(N):
  a, b = map(int,input().split())
  A.append((a, b))
A.sort(key=lambda x: x[1], reverse=True)
A.sort(key=lambda x: x[0])
ans = []
max_point = [-1 for _ in range(T)]
def solve(point, x, unvisit_list):
  if x >= T or len(unvisit_list) == 0:
    ans.append(point)
    return 0
  elif max_point[x] > point:
    return 0
  else:
    max_point[x] = point
    for k in range(len(unvisit_list)):
      new_unvisit = unvisit_list[:k] + unvisit_list[k+1:]
      solve(point+unvisit_list[k][1], x + unvisit_list[k][0], new_unvisit)

while A:
  item = A[0]
  del A[0]
  solve(item[1], item[0], A)
print(max(ans))

### FIXED CODE ###

N, T = map(int, input().split())
A = []
for _ in range(N):
  a, b = map(int,input().split())
  A.append((a, b))
A.sort(key=lambda x: x[0])

newdp = [0 for _ in range(T)]
ans = 0
from collections import deque
A = deque(A)
visited = [0]
while A:
  olddp = tuple(newdp)
  newdp = list(newdp)
  X = A.popleft()
  a = X[0]
  b = X[1]
  for v in visited:
    if v + a > T-1:
      ans = max(ans, olddp[v]+b)
    else:

      if newdp[v+a] == 0:
        visited.append(v+a)
      newdp[v+a] = max(olddp[v] + b, newdp[v+a])


if ans == 0:
  print(max(olddp))
else:
  print(ans)
### BUGGY CODE ###

N = int(input())
S = [s for s in input()]
lis = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
ans = 0
from collections import defaultdict
d = defaultdict(list)
for i,s in enumerate(S):
    d[s].append(i)
for s in lis:
    flag = 0
    for i in range(N-2):
        if flag:break
        if S[i] == s[0]:
            for j in d[s[1]]:
                if j > i:
                    if d[s[2]] and max(d[s[2]]) > j:
                        ans += 1
                        flag = 1
                        break
print(ans)

### FIXED CODE ###

N = int(input())
S = [s for s in input()]
lis = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
ans = 0
from collections import defaultdict
d = defaultdict(list)
for i,s in enumerate(S):
    d[s].append(i)

for s in lis:
    if d[s[0]]:
        i = min(d[s[0]])
        if d[s[1]]:
            for j in d[s[1]]:
                if j > i:
                    if d[s[2]]:
                        if max(d[s[2]]) > j:
                            ans += 1
                            break
                    break
        else:continue
    else:continue
                            
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
a = []

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

def prime_factorize(n):
  global a
  tmp = []
  while n % 2 == 0:
    if 2 not in a:
      tmp.append(2)
      n //= 2
    else:
      return False
  f = 3
  while f * f <= n:
    if n % f == 0:
      if f not in a:
        tmp.append(f)
        n //= f
      else:
        return False
    else:
      f += 2
  if n != 1:
    if n not in a:
      tmp.append(n)
    else:
      return False
  a = list(set(a+tmp))
  return True

flag = True
for i in range(N):
  ans = prime_factorize(A[i])
  if not ans:
    flag = False
    break
if flag:
  print('pairwise coprime')
elif gcd_list(A) == 1:
  print('setwise coprime')
else:
  print('not coprime')

### FIXED CODE ###

import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
a = set()

def gcd_list(numbers):
  return reduce(math.gcd, numbers)

def prime_factorize(n):
  global a
  tmp = []
  while n % 2 == 0:
    if 2 not in a:
      tmp.append(2)
      n //= 2
    else:
      return False
  f = 3
  while f * f <= n:
    if n % f == 0:
      if f not in a:
        tmp.append(f)
        n //= f
      else:
        return False
    else:
      f += 2
  if n != 1:
    if n not in a:
      tmp.append(n)
    else:
      return False
  a |= set(tmp)
  return True

flag = True
for i in range(N):
  ans = prime_factorize(A[i])
  if not ans:
    flag = False
    break
if flag:
  print('pairwise coprime')
elif gcd_list(A) == 1:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().strip())
l = [ int(x) for x in sys.stdin.readline().strip().split() ]
l.sort()
c = 0
n1 = n - 1
for i in range(n-2):
    li = l[i]
    for j in range(i+1,n1):
        k = bisect_left(l,l[j]+li,lo=j)
        c += k-j-1
#
print(c)


### FIXED CODE ###

#!/usr/bin/env python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().strip())
l = list(map(int,sys.stdin.readline().strip().split()))
    
l.sort()
c = 0
n1 = n - 1
for i in range(n-2):
    li = l[i]
    for j in range(i+1,n1):
        k = bisect_left(l,l[j]+li,lo=j)
        c += k-j-1
#
print(c)
### BUGGY CODE ###

from collections import deque
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def generate_v2_b(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]:
                continue
            dist[v2] = dist[v]
            next_v.append(v2)

        for v2 in generate_v2_b(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)

    return dist


ans = bfs(start)[goal]
print(-1 if ans == INF else ans)


### FIXED CODE ###

import heapq
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        if (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            d = 0
        else:
            d = 1
        yield d, x*w+y


def dijkstra(init_v):
    next_v = [(0, init_v)]
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


ans = dijkstra(start)[goal]
print(-1 if ans == INF else ans)
### BUGGY CODE ###

s = input().strip()
k = int(input())
subs = set()
ds = {}

for i, c in enumerate(s):
  if c in ds:
    ds[c].append(i)
  else:
    ds[c] = [i]

for c, il in sorted(ds.items(), key=lambda x: x[0]):
  subs |= set([c])
  i = 2
  while il[0]+i <= len(s):
    for j in il:
      if j + i > len(s):
        break
      subs.add(s[j:j+i])
    i += 1
  if len(subs) >= k:
    break
print(list(sorted(subs))[k-1])


### FIXED CODE ###

s = input().strip()
k = int(input())
subs = set()
for i in range(1, 6):
  for j in range(0, len(s)-i+1):
    subs |= set([s[j:j+i]])
print(list(sorted(subs))[k-1])