#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
static char buf[1000 << 20];
void* operator new(size_t s) {
static size_t i = sizeof buf;
assert(s < i);
return (void*)&buf[i -= s];
}
void operator delete(void*) {}
const int UNTIL = 3000001;
vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
int csqrt[UNTIL], fsqrt[UNTIL];
void init() {
csqrt[1] = fsqrt[1] = 1;
for (int i = 2; i < UNTIL; ++i) {
fsqrt[i] = fsqrt[i - 1];
while ((fsqrt[i] + 1) * (fsqrt[i] + 1) <= i) ++fsqrt[i];
csqrt[i] = fsqrt[i];
if (fsqrt[i] * fsqrt[i] < i) ++csqrt[i];
}
}
struct VEB {
int u, mn, mx, sz;
VEB *summary;
vector<VEB*> galaxy;
inline int high(int k) { return k / sz; }
inline int low(int k) { return k % sz; }
inline int index(int k, int kk) { return k * sz + kk; }
VEB(int u) : u(u) {
mn = INT_MAX, mx = INT_MIN;
if (u <= 2) summary = nullptr, galaxy.resize(0, nullptr);
else {
int ngalaxy = csqrt[u];
sz = (u + ngalaxy - 1) / ngalaxy;
summary = new VEB(ngalaxy);
galaxy.resize(ngalaxy, nullptr);
for (int i = 0; i < ngalaxy - 1; ++i) galaxy[i] = new VEB(sz);
galaxy[ngalaxy - 1] = new VEB(u - (ngalaxy - 1) * sz);
}
}
void insert(int x) {
if (mn == INT_MAX) mn = mx = x;
else {
if (x < mn) swap(x, mn);
if (x > mx) mx = x;
if (u <= 2) return;
int i = high(x), j = low(x);
if (galaxy[i]->mn == INT_MAX) summary->insert(i);
galaxy[i]->insert(j);
}
}
void erase(int x) {
if (mn == INT_MAX) return;
if (mn == mx) {
mn = INT_MAX, mx = INT_MIN;
return;
}
if (u <= 2) {
if (x != mx) mn = mx;
else if (x == mn) mn = INT_MAX, mx = INT_MIN;
else if (x == 0) mn = 1;
else mx = 0;
return;
}
if (x == mn) {
int i = summary->mn;
if (i == INT_MAX) {
mn = INT_MAX, mx = INT_MIN;
return;
}
x = mn = index(i, galaxy[i]->mn);
}
int i = high(x), j = low(x);
galaxy[i]->erase(j);
if (galaxy[i]->mn == INT_MAX) summary->erase(i);
if (x == mx) {
if (summary->mx == INT_MIN) mx = mn;
else {
i = summary->mx;
mx = index(i, galaxy[i]->mx);
}
}
}
int lower_bound(int x) {
if (x <= mn) return mn;
if (u <= 2) {
if (x <= mx) return mx;
return INT_MAX;
}
int i = high(x), j = low(x);
if (j <= galaxy[i]->mx) j = galaxy[i]->lower_bound(j);
else {
i = summary->lower_bound(i + 1);
j = galaxy[i]->mn;
}
return index(i, j);
}
};
VEB* build_veb(int u) {
VEB* root = new VEB(u);
for (int i = 0; i < u; ++i) root->insert(i);
return root;
}
struct Sustree {
int n, m;
vector<VEB*> has;
Sustree() {}
Sustree(int n, int m) : n(n), m(m), has(2 * n, nullptr) {}
inline void build() {
for (int i = 1; i < 2 * n; ++i) has[i] = build_veb(m + 1);
}
inline void upd(int x, int y) {
has[x += n]->erase(y);
for (; x > 1; x >>= 1)
if (has[x]->lower_bound(y) != y && has[x ^ 1]->lower_bound(y) != y)
has[x >> 1]->erase(y);
}
inline pii qry(int x1, int y1, int x2, int y2) {
x1 = max(x1, 0), y1 = max(y1, 0), x2 = min(x2, n - 1), y2 = min(y2, m - 1);
int l = x1, r = x2 + 1, idx = -1;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
if (has[l]->lower_bound(y1) <= y2) {
idx = l;
break;
}
l++;
}
if (r & 1) {
--r;
if (has[r]->lower_bound(y1) <= y2) {
idx = r;
break;
}
}
}
if (idx < 0) return {-1, -1};
while (idx < n) {
idx <<= 1;
if (has[idx]->lower_bound(y1) > y2) ++idx;
}
return {idx - n, has[idx]->lower_bound(y1)};
}
};
int main() {
init();
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int r, c, n; cin >> r >> c >> n;
int sx, sy; cin >> sx >> sy; --sx, --sy;
int gx, gy; cin >> gx >> gy; --gx, --gy;
vector<string> arr(r);
for (int i = 0; i < r; ++i) cin >> arr[i];
if (r > c) {
vector<string> arr2(c);
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
arr2[j] += arr[i][j];
}
}
swap(arr, arr2);
swap(r, c);
swap(sx, sy);
swap(gx, gy);
}
// . = empty
// # = wall
Sustree sus(r, c); sus.build();
// cout << sus.qry(1, 0, 1, 0).first << endl;
// exit(0);
vector<vector<int>> dists(r, vector<int>(c, INT_MAX));
dists[sx][sy] = 0;
sus.upd(sx, sy);
vector<pii> q; q.push_back({sx, sy});
queue<pii> rq; for (pii _p : q) rq.push(_p);
while (rq.size()) {
pii front = rq.front(); rq.pop();
int xx = front.first, yy = front.second;
for (int d = 0; d < 4; ++d) {
int nx = xx + dx[d], ny = yy + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
rq.push({nx, ny});
q.push_back({nx, ny});
dists[nx][ny] = dists[xx][yy];
sus.upd(nx, ny);
}
}
while (q.size()) {
// cout << "part 1 " << endl;
vector<pii> nq;
for (pii p : q) {
// cout << p.first << ' ' << p.second << "s" << endl;
int x = p.first, y = p.second;
if (x > 0 && dists[x - 1][y] <= dists[x][y]) {
// query down:
int cur;
while ((cur = sus.qry(x + n, y - n + 1, x + n, y + n - 1).second) != -1) {
nq.push_back({x + n, cur});
dists[x + n][cur] = dists[x][y] + 1;
sus.upd(x + n, cur);
}
if (x + n - 1 < r && y - n >= 0 && dists[x + n - 1][y - n] == INT_MAX) {
nq.push_back({x + n - 1, y - n});
dists[x + n - 1][y - n] = dists[x][y] + 1;
sus.upd(x + n - 1, y - n);
}
if (x + n - 1 < r && y + n < c && dists[x + n - 1][y + n] == INT_MAX) {
nq.push_back({x + n - 1, y + n});
dists[x + n - 1][y + n] = dists[x][y] + 1;
sus.upd(x + n - 1, y + n);
}
} else if (y < r - 1 && dists[x][y + 1] <= dists[x][y]) {
// query left:
int cur;
while ((cur = sus.qry(x - n + 1, y - n, x + n - 1, y - n).first) != -1) {
nq.push_back({cur, y - n});
dists[cur][y - n] = dists[x][y] + 1;
sus.upd(cur, y - n);
}
if (y - n + 1 >= 0 && x - n >= 0 && dists[x - n][y - n + 1] == INT_MAX) {
nq.push_back({x - n, y - n + 1});
dists[x - n][y - n + 1] = dists[x][y] + 1;
sus.upd(x - n, y - n + 1);
}
if (y - n + 1 >= 0 && x + n < r && dists[x + n][y - n + 1] == INT_MAX) {
nq.push_back({x + n, y - n + 1});
dists[x + n][y - n + 1] = dists[x][y] + 1;
sus.upd(x + n, y - n + 1);
}
} else {
// query all:
// cout << p.first << ' ' << p.second << "m" << endl;
for (int i = -n; i <= n; i += 2 * n) {
int cx = x + i, cyl = y - n + 1, cyr = y + n - 1, cur;
while ((cur = sus.qry(cx, cyl, cx, cyr).second) != -1) {
nq.push_back({cx, cur});
dists[cx][cur] = dists[x][y] + 1;
sus.upd(cx, cur);
}
}
pii cur;
while ((cur = sus.qry(x - n + 1, y - n, x + n - 1, y + n)).first != -1) {
// cout << cur.first << ' ' << cur.second << endl;
int nx = cur.first, ny = cur.second;
nq.push_back({nx, ny});
dists[nx][ny] = dists[x][y] + 1;
sus.upd(nx, ny);
}
}
// cout << p.first << ' ' << p.second << "e" << endl;
}
queue<pii> rq; for (pii _p : nq) rq.push(_p);
while (rq.size()) {
pii front = rq.front(); rq.pop();
int xx = front.first, yy = front.second;
for (int d = 0; d < 4; ++d) {
int nx = xx + dx[d], ny = yy + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
rq.push({nx, ny});
nq.push_back({nx, ny});
dists[nx][ny] = dists[xx][yy];
sus.upd(nx, ny);
}
}
q = nq;
}
cout << dists[gx][gy] << '\n';
return 0;
}
