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

S = input()
Q = int(input())

for _ in range(Q):
    query = input().split()

    if query[0] == '1':
        # reverse
        S = S[::-1]

    else:
        # add character

        # at head
        if query[1] == '1':
            S = query[2] + S

        # at tail
        else:
            S = S + query[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())

forward = True
que0 = []
que1 = []

for _ in range(Q):
    query = input().split()

    if query[0] == '1':
        forward = not forward

    else:
        head = (query[1] == '1')
        if head ^ forward:
            que1.append(query[2])
        else:
            que0.append(query[2])

S = ''.join(que0[::-1]) + S + ''.join(que1)

if forward:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

from collections import deque

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

D = deque([1], N)
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      count += sum(D[i-k] for k in range(l, min(i, r) + 1))
  D.append(count % 998244353)
print(D[-1])

### FIXED CODE ###

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

D = [1]
M = 100
memo = []
memo2 = []
for i in range(1, N):
  count = 0
  for l, r in LR:
    if l <= i:
      l1 = i - min(i, r)
      r1 = i - l + 1
      l2 = (l1 + M - 1) // M
      r2 = r1 // M
      l3 = (l2 + M - 1) // M
      r3 = r2 // M
      if r3 > l3:
        count += sum(D[l1:l2*M]) + sum(memo[l2:l3*M]) + sum(memo2[l3:r3]) + sum(memo[r3*M:r2]) + sum(D[r2*M:r1])
      elif r2 > l2:
        count += sum(D[l1:l2*M]) + sum(memo[l2:r2]) + sum(D[r2*M:r1])
      else:
        count += sum(D[l1:r1])
  D.append(count % 998244353)
  if len(D) % M == 0:
    memo.append(sum(D[-M:]))
    if len(memo) % M == 0:
      memo2.append(sum(memo[-M:]))
print(D[-1])
### BUGGY CODE ###

N,M=map(int,input().split())
LA=list(map(int,input().split()))
for m in range(M):
    B,C=map(int,input().split())
    for b in range(B):
        LA.append(C)
LA.sort(reverse=True)
print(sum(LA[0:N]))

### FIXED CODE ###

N,M=map(int,input().split())
LA=list(map(int,input().split()))
L=[]
for i in LA:
    L.extend([[1,i]])
for m in range(M):
    B,C=map(int,input().split())
    L.extend([[B,C]])
L.sort(key=lambda _:_[1] ,reverse=True)

ans=0
n=0
x=0
while x<=N-1:
    y=0
    while y<=L[n][0]-1:
        ans+=L[n][1]
        y+=1
        x+=1
        if x==N:
            break
        else:
            pass
    n+=1

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

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    A = list(map(int, input().split()))

    B = [(A[i], i) for i in range(N)]
    B.sort(key = lambda x: x[0], reverse = True)

    DP = [[0] * (N + 1) for _ in range(N + 1)]

    for i in range(N):
        a = B[i][0]
        tmp = B[i][1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

    ans = 0
    for i in range(N + 1):
        ans = max(ans, DP[i][N - i])

    print (ans)

    # for tmp in DP:
    #     print (tmp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

B = [(A[i], i) for i in range(N)]
B.sort(key = lambda x: x[0], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(N):
    a = B[i][0]
    tmp = B[i][1]
    for x in range(i + 1):
        DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
        DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

ans = 0
for i in range(N + 1):
    ans = max(ans, DP[i][N - i])

print (ans)

# for tmp in DP:
#     print (tmp)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

INF = float('inf')
dist = [INF]*n # dfsの条件式の書き換えに注意

ans = [-1]*(n)

def dfs(now):
    for next_v in es[now]:
        if dist[next_v] > dist[now]+1:
            dist[next_v] = dist[now]+1
            ans[next_v] = now+1
            dfs(next_v)

start = 0
dist[start]=0 #初期化
dfs(start)

print('Yes')
print(*ans[1:],sep='\n')


### FIXED CODE ###

import heapq
n,m = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(m)]

es = [[] for i in range(n)]
for x,y in src:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

INF = float('inf')
ds = [INF] * n
ans = [-1]*(n)

def dijkstra(start, dists):
    dists[start] = 0
    hq = [(0,start)]
    heapq.heapify(hq)
    while hq:
        dist,v = heapq.heappop(hq)
        for to in es[v]:
            if dist+1 >= dists[to]: continue
            dists[to] = dist+1
            ans[to]=v+1
            heapq.heappush(hq, (dist+1,to))

dijkstra(0,ds)

print('Yes')
print(*ans[1:],sep='\n')
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
FB = [0 for _ in range(N//2)]
SB = A[N//2:N]
B = FB + SB
S = [i for i in range(1,N//2+1)]
FH = A[0:N//2]
for i in range(1,len(FH)+1):
    s = 0
    for j in range(2,N//S[-i]+1):
        s += B[S[-i]*j-1]
    if s % 2 != FH[-i]:
        FB[-i] = 1
    B = FB + SB
ans = []
for i in range(N):
    if B[i] == 1:
        ans.append(i+1)
print(len(ans))
print(*ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
FB = [0 for _ in range(N//2)]
SB = A[N//2:N]
B = FB + SB
S = [i for i in range(1,N//2+1)]
FH = A[0:N//2]
for i in range(1,len(FH)+1):
    s = 0
    for j in range(2,N//S[-i]+1):
        s += B[S[-i]*j-1]
    if N % 2 == 0:
        if s % 2 != FH[-i]:
            B[-i-N//2] = 1
    else:
        if s % 2 != FH[-i]:
            B[-i-N//2-1] = 1            
ans = []
for i in range(N):
    if B[i] == 1:
        ans.append(i+1)
print(len(ans))
print(*ans)
### BUGGY CODE ###



import itertools
n = int(input())
a = list(map(int, input().split(" ")))

ans = 0
for i, j in itertools.combinations(range(n), 2):
    ans += (a[i] * a[j]) % (10**9+7)

print(ans % (10**9 + 7))

### FIXED CODE ###

import itertools
x = 10**9 + 7
n = int(input())
a = list(map(lambda i: i % x , map(int, input().split(" "))))
sum_a = []
prev = 0
for i in a:
    sum_a.append(prev + i)
    prev = prev + i

ans = 0
for i in range(n):
    ans += (a[i] * (sum_a[n-1] - sum_a[i] )) % x
print(ans % x)
### BUGGY CODE ###

import heapq

x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p = sorted(p, reverse = True)[:x]
q = sorted(q, reverse = True)[:y]
r = sorted(r, reverse = True)

for i in range(min(x+y, len(r))):
  if min(p) >= min(q) and r[0] > min(q):
    heapq.heapify(q)
    heapq.heappop(q)
    q.append(r[0])
    r.pop(0)
  elif min(q) >= min(p) and r[0] > min(p):
    heapq.heapify(p)
    heapq.heappop(p)
    p.append(r[0])
    r.pop(0)

print(sum(p) + sum(q))

### FIXED CODE ###

import heapq

x,y,a,b,c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p = sorted(p, reverse = True)[:x]
q = sorted(q, reverse = True)[:y]
r = sorted(r, reverse = True)

pqr = p + q + r
pqr = sorted(pqr, reverse = True)[:x+y]

print(sum(pqr))
### BUGGY CODE ###

n = int(input())
alist = sorted([int(v) for v in input().split()], reverse=True)

last = 0
count = 0
for i, a in enumerate(alist):
    if a == last:
        continue
    last = a
    res = True
    for b in alist[i + 1:]:
        if a % b == 0:
            res = False
            break
    if res:
        count += 1

print(count)


### FIXED CODE ###

from collections import Counter

n = int(input())
alist = [int(v) for v in input().split()]
dup_set = {k for k, v in Counter(alist).items() if v >= 2}
alist = sorted(set(alist))
adict = {a: False for a in alist}
a_max = alist[-1]
max_ind = -1

count = 0
if 1 in adict:
    count = 0 if 1 in dup_set else 1
else:
    for a, f in adict.items():
        if f:
            continue
        if a not in dup_set:
            count += 1
        for k in range(a, a_max + 1, a):
            if k in adict:
                adict[k] = True
                if k == a_max:
                    max_ind -= 1
                    if abs(max_ind) <= len(alist):
                        a_max = alist[max_ind]

print(count)
### BUGGY CODE ###

N = int(input())
S = [s for s in input()]
ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    idx = 0
    for j, s in enumerate(S):
        if v[idx] == s:
            idx += 1
            if idx < 3 and v[idx] not in S[j+1:]:
                break
        if idx == 3:
            ans += 1
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    idx = 0
    c = 0
    idx_now = 0
    for j in range(3):
        idx = S[idx_now:].find(v[j])
        if idx == -1:
            break
        else:
            idx_now += idx + 1
            c += 1
    if c == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
s = [1] * (n + 1)
if 1 in a:
    s[1] = 0
for i in range(2, n + 1):
    if i in a:
        s[i] = 0
    else:
        if s[i - 2] == 0 and s[i - 1] == 0:
            print(0)
            exit()
        else:
            s[i] = s[i - 1] + s[i - 2]   
print(s[n] % 1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
s = [1] * (n + 1)
for i in range(m):
    a = int(input())
    s[a] = 0
for i in range(2, n + 1):
    if s[i] == 0:
        continue
    else:
        if s[i - 2] == 0 and s[i - 1] == 0:
            print(0)
            exit()
        else:
            s[i] = s[i - 1] + s[i - 2]   
print(s[n] % 1000000007)
### 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
for s in lis:
    flag = 0
    for i in range(N-2):
        if flag:break
        if S[i] == s[0]:
            if s[1] not in S[i+1:]:continue
            elif s[2] not in S[i+2:]:continue
            else:
                for j in range(i+1,N-1):
                    if S[j] == s[1]:
                        if s[2] in S[j+1:]:
                            ans += 1
                            flag = 1
                            break
                        else:continue
                    else:continue
        else:continue
# print(lis[10:20])
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 ###

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

A_dict = {str(i):0 for i in set(A)}
for a in A:
  A_dict[str(a)] += 1
del A
  
def get_A_key_from_value(dic, value):
  for i, j in dic.items():
    if j == value:
      break
  return i
  
ans = 0
while True:
  if len(A_dict) <= K:
    break
  ans += min(A_dict.values())
  del A_dict[get_A_key_from_value(A_dict,min(A_dict.values()))]
print(ans)  

### FIXED CODE ###

#読み込み
N, K = map(int, input().split())
A = list(map(int, input().split()))
#処理回数
reduce_type = len(set(A)) - K
#削除する数の選定
A_dict = {str(i):0 for i in set(A)}
for a in A:
  A_dict[str(a)] += 1
del A
list_del_num = sorted(list(A_dict.values()))[:reduce_type]
#計算
ans = sum(list_del_num)
print(ans)
### BUGGY 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()

### 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()
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

s = set(a)
l = len(s)
l2 = 0 if len([a.count(x) for x in s]) % 2 else 1
print(l - l2)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

s = set(a)
l = len(s)
l2 = 0 if l % 2 else 1
print(l - l2)
### BUGGY CODE ###

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

p = [0] * N

for i in range(N):
    p[i] = (P[i] + 1) / 2

ans = 0

for i in range(N - K + 1):
    ans = max(ans, sum(p[i: i + K]))
    
print(ans)

### FIXED CODE ###

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

a = [0] * (N - K + 1)
a[0] = sum(P[:K])
for i in range(1, N - K + 1):
    a[i] = a[i - 1] - P[i - 1] + P[i + K - 1]
    
print((max(a) + K) / 2)
### BUGGY CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
A=np.array(A)
v=0
j=0
k=0
for i in reversed(range(0, N+1)):
  j+=A[i]/(2**i)
  if i==N:
    k=A[i]
  else:
    k=min(k+A[i],2**min(i,27)-np.sum(np.array([A[k]*(2**min((i-k),27)) for k in range(i)])))
  v+=k

if j>1:
  print(-1)
else:
  print(int(v))

### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.sum(A)-np.cumsum(np.append(0, A[:len(A)-1]))
v=0
k=0
for i in range(N+1):
  if i==0:
    if N==0 and A[0]==1:
      k=1
    elif A[0]==0:
      k=1
    else:
      print(-1)
      break
  elif i==N:
    if B[i]<=2*(k-A[i-1]):
      k=B[i]
    else:
      k=0
      print(-1)
      break
  else:
    k=min(2*(k-A[i-1]),B[i])
    if k<=0:
      print(-1)
      break
  v+=k
if k>0:
  print(v)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
    B, C = list(map(int, input().split()))
    sum_ = 0
    for j in range(len(A)):
        if A[j] == B:
            A[j] = C
        sum_ += A[j]
    print(sum_)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
count = [0 for i in range(110000)]
sum_ = sum(A)
for i in range(N):
  count[A[i]] += 1

Q=int(input())
for i in range(Q):
  b,c = map(int,input().split())
  count[c] += count[b]
  sum_ += (c-b)*count[b]
  count[b] = 0
  print(sum_)
### BUGGY CODE ###

import sys
N = int(input())
a = [int(input()) for i in range(N)]
d = [0]
b = 0
c = 0
while True:
    if b == 1:
        print(c)
        sys.exit()
    c += 1
    b = a[b] - 1
    if b in d:
        print('-1')
        sys.exit()
    d.append(b)

### FIXED CODE ###

import sys
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
b = [0] * N
i = 0
c = 1
while True:
    if b[i] == 1:
        print(-1)
        sys.exit()
    b[i] = 1
    i = a[i] - 1
    if i == 1:
        print(c)
        sys.exit()
    c += 1
### BUGGY CODE ###

import math

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


ans = 0
res = 1
flag = False
for b in a:
    if b == 0:
        flag = True
        break
    ans += math.log10(b)
    res *= b

if flag:
    print(0)
else:
    if ans > 18:
        print(-1)
    else:
        res2 = res - 1000000000000000000
        if res2 > 0:
            print(-1)
        else:
            print(res)


### FIXED CODE ###

n = int(input())

a = list(map(int, input().split()))
a.sort()

ans = 1

for b in a:
    if b == 0:
        ans = 0
        break
    else:
        ans *= b
        if ans > pow(10, 18):
            ans = -1
            break

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

h, w, m = map(int, input().split())
table = [[0 for i in range(w)] for i in range(h)]
sum_rows = [0 for i in range(h)]
sum_cols = [0 for i in range(w)]
for i in range(m):
    h_, w_ = map(int, input().split())
    table[h_-1][w_-1] = 1
    sum_rows[h_-1] += 1
    sum_cols[w_-1] += 1

m_rows = [i for i, val in enumerate(sum_rows) if val == max(sum_rows)]
m_cols = [i for i, val in enumerate(sum_cols) if val == max(sum_cols)]
flag = 0
for i in m_rows:
    for j in m_cols:
        if table[i][j] == 0:
            flag = 1
if flag:
    print(max(sum_cols)+max(sum_rows))
else:
    print(max(sum_cols)+max(sum_rows)-1)

### FIXED CODE ###

h, w, m = map(int, input().split())
table = []
sum_rows = [0 for i in range(h)]
sum_cols = [0 for i in range(w)]
for i in range(m):
    h_, w_ = map(int, input().split())
    table.append((h_, w_))
    sum_rows[h_-1] += 1
    sum_cols[w_-1] += 1

r = max(sum_rows)
c = max(sum_cols)
ans_ = (r + c)
count = 0
for i in range(m):
    if ans_ == (sum_rows[table[i][0]-1]+sum_cols[table[i][1]-1]):
        count += 1

if count == (sum_rows.count(r) * sum_cols.count(c)):
    print(ans_-1)
else:
    print(ans_)
### BUGGY CODE ###

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

for i in range(N-1):
    for j in range(i+1, N):
        ans += (A[i] * A[j]) 

print(ans % 1000000007)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A2 = list(map(lambda x: x ** 2, A))

sumA = sum(A)
sumA2 = sum(A2)

ans = (((sumA ** 2) - sumA2) // 2) % 1000000007

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

import math
n,m,v,p=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
def is_ok(N,m,v,p):
    counter=0
    howadd=0
    not_avoid=0
    judge=lists[N]+m
    for k in range(n-1,-1,-1):
        if k!=N:
            if judge<lists[k]:
                counter+=m
                howadd+=1
                not_avoid+=1
            elif judge==lists[k] and howadd<p-1:
                counter+=m
                howadd+=1
            elif judge==lists[k] and howadd==p-1:
                pass
            elif judge>lists[k] and howadd<p-1:
                howadd+=1
                counter+=m
            elif judge>lists[k] and howadd==p-1:
                counter+=min(judge-lists[k],m)    
    if not_avoid>=p:
            return False
    elif not_avoid<p:
        if counter<(m)*(v-1):
            return False
        elif counter>=(m)*(v-1):
            return True
start=0
end=n-1
for _ in range(30):
    c=(start+end)/2
    if is_ok(math.floor(c),m,v,p):
        end=c
    elif not (is_ok(math.floor(c),m,v,p)):
        start=c       
print(n-math.floor(end))
                

### FIXED CODE ###

import math
n,m,v,p=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
def is_ok(N,m,v,p):
    counter=0
    howadd=0
    not_avoid=0
    judge=lists[N]+m
    for k in range(n-1,-1,-1):
        if k!=N:
            if judge<lists[k]:
                counter+=m
                howadd+=1
                not_avoid+=1
            elif judge==lists[k] and howadd<p-1:
                counter+=m
                howadd+=1
            elif judge==lists[k] and howadd==p-1:
                pass
            elif judge>lists[k] and howadd<p-1:
                howadd+=1
                counter+=m
            elif judge>lists[k] and howadd==p-1:
                counter+=min(judge-lists[k],m)    
    if not_avoid>=p:
            return False
    elif not_avoid<p:
        if counter<(m)*(v-1):
            return False
        elif counter>=(m)*(v-1):
            return True
start=0
end=n-1
for _ in range(30):
    c=(start+end)/2
    if is_ok(math.floor(c),m,v,p):
        end=c
    elif not (is_ok(math.floor(c),m,v,p)):
        start=c       
print(n-math.floor(end))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            elif dp[x+dx*j][y+dy*j]==dp[x][y]+1:continue###
            elif dp[x+dx*j][y+dy*j]<=dp[x][y]:break###
    
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w,k=map(int, input().split())
x1,y1,x2,y2=map(int, input().split())
x1-=1;y1-=1;x2-=1;y2-=1
c=[input() for _ in range(h)]
INF=10**14
dp=[[INF for _ in range(w)] for _ in range(h)]
dp[x1][y1]=0
from collections import deque
q=deque()

q.append((x1,y1))
dxy=[(1,0),(0,1),(-1,0),(0,-1)]

while q:
    x,y=q.popleft()
    for dx,dy in dxy:
        for j in range(1,k+1):
            if not 0<=x+dx*j<h:break
            if not 0<=y+dy*j<w:break
            if c[x+dx*j][y+dy*j]=='@':break
            if dp[x+dx*j][y+dy*j]>dp[x][y]+1:
                dp[x+dx*j][y+dy*j]=dp[x][y]+1
                q.append((x+dx*j,y+dy*j))
            elif dp[x+dx*j][y+dy*j]==dp[x][y]+1:continue###
            elif dp[x+dx*j][y+dy*j]<=dp[x][y]:break###
    
            
            if x+dx*j==x2 and y+dy*j==y2:
                print(dp[x2][y2])
                exit()

        
print(-1)
### BUGGY CODE ###

n=int(input(""))
k=1
li=list(map(int,input("").split(" ")))
if 0 in li:
    print("0")
else:
    for i in li:
        k*=int(i)
    if k>1000000000000000000:
        print("-1")
    else:
        print(k)


### FIXED CODE ###

n=int(input(""))
k=1
li=list(map(int,input("").split(" ")))
if 0 in li:
    print("0")
else:
    for i in li:
        k*=int(i)
        if k>1000000000000000000:
            print("-1")
            break
    else:
        print(k)
### BUGGY CODE ###

from itertools import permutations

n , l = input().split()
n = int(n)
l = int(l)
s = [input() for _ in range(n)]

p = list(permutations(s,n))
result = []
for i in p:
	ss = ''
	for n in i:
		ss += n
	result.append(ss)
result.sort()
print(result[0])

### FIXED CODE ###

n , l = map(int , input().split())
s = sorted([input() for _ in range(n)])
print(''.join(s))
### BUGGY CODE ###

inf = 10**9

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

ls = [list(map(int,input().split())) for _ in range(n)]

amax = max(a for a,b in ls)

dp = [inf]*(h+amax)
dp[0] = 0

for i in range(1,h+amax):
  m = inf
  for a,b in ls:
    tmp = dp[max(0,i-a)] + b
    m = min(m,tmp)
  dp[i] = m

print(min(dp[h:]))

### FIXED CODE ###

n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))