#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 1e18, MOD = 1e9 + 7;
vector<pair<ll, ll>> cord = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void solve() {
ll r, c, n;
cin >> r >> c >> n;
ll sr, sc, gr, gc;
cin >> sr >> sc >> gr >> gc;
sr--, sc--, gr--, gc--;
vector<vector<char>> a(r, vector<char>(c));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> a[i][j];
}
}
if (r > c) {
swap(r, c);
swap(sr, sc); swap(gr, gc);
vector<vector<char>> nw(r, vector<char>(c));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
nw[i][j] = a[j][i];
}
}
a = nw;
}
if (n >= r) {
queue<pair<ll, ll>> bfs;
bfs.emplace(sr, sc);
vector<vector<int>> used(r, vector<int>(c, 0));
used[sr][sc] = 1;
ll mn = sc, mx = sc;
while (!bfs.empty()) {
auto [i, j] = bfs.front();
bfs.pop();
mn = min(mn, j); mx = max(mx, j);
for (auto [fx, fy] : cord) {
ll x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x][y] == '#') continue;
if (used[x][y]) continue;
used[x][y] = 1;
bfs.emplace(x, y);
}
}
ll col = 0;
ll lf = sc + 1, rf = sc - 1;
while (!used[gr][gc]) {
ll nwl = max(0ll, mn - n), nwr = min(c - 1, mx + n);
for (int i = 0; i < r; i++) {
for (ll j = nwl; j < lf; j++) used[i][j] = 1;
for (ll j = rf + 1; j <= nwr; j++) used[i][j] = 1;
}
col++;
lf = nwl, rf = nwr;
for (int i = 0; i < r; i++) {
bfs.emplace(i, lf);
bfs.emplace(i, rf);
}
while (!bfs.empty()) {
auto [i, j] = bfs.front();
bfs.pop();
mn = min(mn, j); mx = max(mx, j);
for (auto [fx, fy] : cord) {
ll x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x][y] == '#') continue;
if (used[x][y]) continue;
used[x][y] = 1;
bfs.emplace(x, y);
}
}
}
cout << col << "\n";
return;
}
vector<vector<int>> used(r, vector<int>(c, 0));
ll col = 0;
queue<pair<ll, ll>> bfs;
bfs.emplace(sr, sc);
used[sr][sc] = 1;
vector<pair<ll, ll>> elems;
while (!bfs.empty()) {
auto [i, j] = bfs.front();
bfs.pop();
elems.emplace_back(i, j);
for (auto [fx, fy] : cord) {
ll x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x][y] == '#') continue;
if (used[x][y]) continue;
used[x][y] = 1;
bfs.emplace(x, y);
}
}
vector<vector<int>> nxt;
if (n < 100) {
nxt.assign(r, vector<int>(c + 1));
for (int i = 0; i < r; i++) {
iota(nxt[i].begin(), nxt[i].end(), 0);
}
}
auto get_nxt = [&](auto& self, int i, int j) -> int {
return nxt[i][j] == j ? j : nxt[i][j] = self(self, i, nxt[i][j]);
};
vector<vector<int>> add;
if (n >= 100) {
add.assign(r + 2, vector<int>(c + 2, 0));
}
while (!used[gr][gc]) {
if (n >= 100) {
for(int i = 0; i <= r + 1; ++i) {
fill(add[i].begin(), add[i].end(), 0);
}
for (auto [x, y]: elems) {
ll x1 = max(0ll, x - (n - 1)), y1 = max(0ll, y - n);
ll x2 = min(r - 1, x + (n - 1)), y2 = min(c - 1, y + n);
add[x1 + 1][y1 + 1]++;
if (x2 + 1 < r && y2 + 1 < c) add[x2 + 2][y2 + 2]++;
if (y2 + 1 < c) add[x1 + 1][y2 + 2]--;
if (x2 + 1 < r) add[x2 + 2][y1 + 1]--;
if (x - n >= 0) {
x1 = x - n, y1 = max(0ll, y - (n - 1));
x2 = x - n, y2 = min(c - 1, y + (n - 1));
add[x1 + 1][y1 + 1]++;
if (x2 + 1 < r && y2 + 1 < c) add[x2 + 2][y2 + 2]++;
if (y2 + 1 < c) add[x1 + 1][y2 + 2]--;
if (x2 + 1 < r) add[x2 + 2][y1 + 1]--;
}
if (x + n < r) {
x1 = x + n, y1 = max(0ll, y - (n - 1));
x2 = x + n, y2 = min(c - 1, y + (n - 1));
add[x1 + 1][y1 + 1]++;
if (x2 + 1 < r && y2 + 1 < c) add[x2 + 2][y2 + 2]++;
if (y2 + 1 < c) add[x1 + 1][y2 + 2]--;
if (x2 + 1 < r) add[x2 + 2][y1 + 1]--;
}
}
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
add[i][j] += add[i - 1][j] + add[i][j - 1] - add[i - 1][j - 1];
if (add[i][j] && !used[i - 1][j - 1]) {
bfs.emplace(i - 1, j - 1);
used[i - 1][j - 1] = 1;
}
}
}
} else {
for (auto [x, y] : elems) {
for (int i = max(0ll, x - n); i <= min(r - 1, x + n); i++) {
ll lf = max(0ll, y - n), rf = min(c - 1, y + n);
if (abs(x - i) == n) {
lf = max(0ll, y - n + 1), rf = min(c - 1, y + n - 1);
}
for (int j = get_nxt(get_nxt, i, lf); j <= rf; j = get_nxt(get_nxt, i, j)) {
if (!used[i][j]) {
used[i][j] = 1;
bfs.emplace(i, j);
}
nxt[i][j] = get_nxt(get_nxt, i, j + 1);
}
}
}
}
vector<pair<ll, ll>> nw;
while (!bfs.empty()) {
auto [i, j] = bfs.front();
bfs.pop();
nw.emplace_back(i, j);
for (auto [fx, fy] : cord) {
ll x = i + fx, y = j + fy;
if (x < 0 || y < 0 || x == r || y == c || a[x][y] == '#') continue;
if (used[x][y]) continue;
used[x][y] = 1;
bfs.emplace(x, y);
}
}
elems = nw;
col++;
}
cout << col << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int q = 1;
while (q--) {
solve();
}
}
