output_description: Print the minimum number of strokes Snuke takes to travel from the square
  (x_1,y_1) to (x_2,y_2), or print `-1` if the travel is impossible.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W K
      x_1 y_1 x_2 y_2
      c_{1,1}c_{1,2} .. c_{1,W}
      c_{2,1}c_{2,2} .. c_{2,W}
      :
      c_{H,1}c_{H,2} .. c_{H,W}
attempt: #!/usr/bin/env python3
  # fast input
  from heapq import heappop, heappush
  import sys
  
  input = sys.stdin.buffer.readline
  INF = 10**10
  # INF = float("inf")
  
  
  def main(H, W, K, x1, y1, x2, y2, mapdata):
      start = x1 * W + y1
      goal = x2 * W + y2
  
      NUM_DIR = 4
      distances = [(INF, 0)] * (H * W * NUM_DIR)
      key = start * NUM_DIR
      distances[key] = (0, 0)
      distances[key + 2] = (0, 0)
  
      shortest_path = [0] * (H * W * NUM_DIR)
      shortest_path[key] = 0
  
      queue = [((0, 0), key), ((0, 0), key + 2)]
      DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
      while queue:
          (d, frac), pos_dir = heappop(queue)
          pos, direction = divmod(pos_dir, NUM_DIR)
          x, y = divmod(pos, W)
          dist = distances[pos_dir]
          if dist < (d, frac):
              continue
          if pos == goal:
              break
  
          dx, dy = DIRS[direction]
          nx = x + dx
          ny = y + dy
          # dp("nx, ny", nx, ny)
          if mapdata[nx * W + ny]:
              if frac == 0:
                  newd = d + 1
                  newfrac = -K + 1
              else:
                  newd = d
                  newfrac = frac + 1
              newdist = (newd, newfrac)
              to = (nx * W + ny) * NUM_DIR + direction
  
              if distances[to] > newdist:
                  # found shorter path
                  distances[to] = newdist
                  heappush(queue, (newdist, to))
                  shortest_path[to] = pos_dir
  
          if direction < 2:
              # facing X axis
              dir = 2
              nx = x
              ny = y + 1
              if mapdata[nx * W + ny]:
                  newdist = (d + 1, -K + 1)
  
                  to = (nx * W + ny) * NUM_DIR + dir
                  if distances[to] > newdist:
                      # found shorter path
                      distances[to] = newdist
                      heappush(queue, (newdist, to))
                      shortest_path[to] = pos_dir
  
              dir = 3
              nx = x
              ny = y - 1
              if mapdata[nx * W + ny]:
                  newdist = (d + 1, -K + 1)
  
                  to = (nx * W + ny) * NUM_DIR + dir
                  if distances[to] > newdist:
                      # found shorter path
                      distances[to] = newdist
                      heappush(queue, (newdist, to))
                      shortest_path[to] = pos_dir
          if direction > 1:
              # facing Y axis
              dir = 0
              nx = x + 1
              ny = y
              if mapdata[nx * W + ny]:
                  newdist = (d + 1, -K + 1)
  
                  to = (nx * W + ny) * NUM_DIR + dir
                  if distances[to] > newdist:
                      # found shorter path
                      distances[to] = newdist
                      heappush(queue, (newdist, to))
                      shortest_path[to] = pos_dir
  
              dir = 1
              nx = x - 1
              ny = y
              if mapdata[nx * W + ny]:
                  newdist = (d + 1, -K + 1)
  
                  to = (nx * W + ny) * NUM_DIR + dir
                  if distances[to] > newdist:
                      # found shorter path
                      distances[to] = newdist
                      heappush(queue, (newdist, to))
                      shortest_path[to] = pos_dir
  
      result = min(distances[goal * NUM_DIR : goal * NUM_DIR + NUM_DIR])
      if result[0] == INF:
          # unreachable
          return -1
      else:
          return result[0]
  
  
  # print(sys.argv)
  if sys.argv[-1] == "ONLINE_JUDGE":
      print("compiling")
      from numba.pycc import CC
  
      cc = CC("my_module")
      cc.export("main", "i8(i8,i8,i8,i8,i8,i8,i8,b1[:])")(main)
      cc.compile()
      exit()
  else:
      H, W, K = map(int, input().split())
      x1, y1, x2, y2 = map(int, input().split())
  
      from my_module import main
      import numpy as np
  
      C = np.zeros((H + 2, W + 2), np.bool_)
      data = np.frombuffer(sys.stdin.buffer.read(), "S1")
      # print(data)
      data = data.reshape(H, -1)
      # print(data)
      data = data[:, :W] == b"."
      # print(data)
      C[1:-1, 1:-1] = data
      C = C.ravel()
      H += 2
      W += 2
  
      print(main(H, W, K, x1, y1, x2, y2, C))
  
problem_description: Statement
  
  Snuke, a water strider, lives in a rectangular pond that can be seen as a grid
  with H east-west rows and W north-south columns. Let (i,j) be the square at
  the i-th row from the north and j-th column from the west.
  
  Some of the squares have a lotus leaf on it and cannot be entered. The square
  (i,j) has a lotus leaf on it if c_{ij} is `@`, and it does not if c_{ij} is
  `.`.
  
  In one stroke, Snuke can move between 1 and K squares (inclusive) toward one
  of the four directions: north, east, south, and west. The move may not pass
  through a square with a lotus leaf. Moving to such a square or out of the pond
  is also forbidden.
  
  Find the minimum number of strokes Snuke takes to travel from the square
  (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is
  impossible, point out that fact.
samples: [{"input": "3 5 2\n    3 2 3 4\n    .....\n    .@..@\n    ..@..", "output": "5\n    \n\nInitially, Snuke is at the square (3,2). He can reach the square (3, 4) by\nmaking five strokes as follows:\n\n  * From (3, 2), go west one square to (3, 1).\n\n  * From (3, 1), go north two squares to (1, 1).\n\n  * From (1, 1), go east two squares to (1, 3).\n\n  * From (1, 3), go east one square to (1, 4).\n\n  * From (1, 4), go south two squares to (3, 4).\n\n* * *"}, {"input": "1 6 4\n    1 1 1 6\n    ......", "output": "2\n    \n\n* * *"}, {"input": "3 3 1\n    2 1 2 3\n    .@.\n    .@.\n    .@.", "output": "-1"}]