#include <bits/stdc++.h>

using namespace std;

ifstream f ("snack.in");
ofstream g ("snack.out");

/// Datele problemei ------------------------------------------------
int price;
int n;
short bani[5005];
string row;

/// Variabile auxiliare ---------------------------------------------
int suma;
short nrOfOrders;

short nrColoane;
short nrRanduri;

short selectColoana;
short selectRand;

short randITN;
short coloanaITN;

short lStartColumn;
short lStartRow;

short lEndColumn;
short lEndRow;

short defekt;

short snackGrid[30][30];
short snackStock[30][30];
short snackArm[30][30];

int valoareCent[10];
int nrMonede[5005];

vector <short> orders[2];

queue <short> xCoada;
queue <short> yCoada;

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};

/// Antete de functii -----------------------------------------------
void citire();
void citire2();
void citire3();
void citire4();
void citire5();
void populareValCent();
int toNumber(char);
void indexToNumbers(string);

/// Functii implementate --------------------------------------------

void rezolvare1() {
    if (suma < price) {
        g << "MISSING" << ' ';
        g << abs(suma - price);
    }
    else {
        g << "CHANGE" << ' ';
        g << abs(suma - price);
    }
}

void rezolvare2(int suma, int price) {
    int rest;
    populareValCent();

    if (suma < price) {
        g << "MISSING" << ' ';
        g << price - suma;
    }
    else {
        g << "CHANGE ";

        rest = suma - price;
        for (int i = 8; i >= 1; --i) {
            nrMonede[i] = rest/valoareCent[i];
            rest -= nrMonede[i]*valoareCent[i];

//            cout << valoareCent[i] << '\n';
//            cout << rest/valoareCent[i] << '\n';
//            cout << nrMonede[i]*valoareCent[i] << '\n';
        }
        for (int i = 1; i <= 8; ++i) {
            g << nrMonede[i] << ' ';
        }

    }
}

rezolvare3() {
    rezolvare2(suma, price);
}

rezolvare4() {
    int curentColoana;
    int curentRand;

    int cashAdunat = 0;

    for (int i = 0; i < nrOfOrders; ++i) {
        curentColoana = orders[1][i];
        curentRand = orders[2][i];

        if (snackStock[curentColoana][curentRand] > 0) {
            cashAdunat += snackGrid[curentColoana][curentRand];
            --snackStock[curentColoana][curentRand];
        }
    }

    g << cashAdunat;
}

void rezolvare5() {
    int xCurent, yCurent;
    int xNou, yNou;

    xCoada.push(lStartRow);
    yCoada.push(lStartColumn);

    snackArm[lStartRow][lStartColumn] = 1;

    while (!xCoada.empty() && snackArm[lEndRow][lEndColumn] == 0) {
        xCurent = xCoada.front();
        yCurent = yCoada.front();

        xCoada.pop();
        yCoada.pop();

        for (int i = 1; i <= 8; ++i) {

            xNou = xCurent + dx[i];
            yNou = yCurent + dy[i];
            if (snackArm[xNou][yNou] == 0) {
                xCoada.push(xNou);
                yCoada.push(yNou);

                snackArm[xNou][yNou] = 1 + snackArm[xCurent][yCurent];
            }
        }
    }

    for (int i = 1; i <= nrRanduri; ++i) {
        for (int j = 1; j <= nrColoane; ++j) {
            if (snackArm[i][j] < 10) {
                cout << ' ' << snackArm[i][j] << ' ';
            }
            else {
                cout << ' ' << snackArm[i][j] ;
            }
        }
        cout << "\n";
    }

    g << snackArm[lEndRow][lEndColumn] - 1;

}

bool inMatrice(short xNou, short yNou) {
    if (!(1 <= xNou && xNou <= nrRanduri))
        return false;
    if (!(1 <= yNou && yNou <= nrColoane))
        return false;
    return true;
}
/// Main ////////////////////////////////////////////////////////////

void rezolvare6() {
    int xCurent, yCurent;
    int xNou, yNou;

    xCoada.push(lStartRow);
    yCoada.push(lStartColumn);

    snackArm[lStartRow][lStartColumn] = 1;

    while (!xCoada.empty() && snackArm[lEndRow][lEndColumn] == 0) {
        xCurent = xCoada.front();
        yCurent = yCoada.front();

        xCoada.pop();
        yCoada.pop();

        for (int i = 0; i < defekt; ++i) {

            xNou = xCurent + dy[i];
            yNou = yCurent + dx[i];
            if (snackArm[xNou][yNou] == 0 && inMatrice(xNou, yNou)) {
                xCoada.push(xNou);
                yCoada.push(yNou);

                snackArm[xNou][yNou] = 1 + snackArm[xCurent][yCurent];
                //snackArm[xNou][yNou] = i;
            }
        }

        for (int i = defekt + 1; i < 8; ++i) {

            xNou = xCurent + dy[i];
            yNou = yCurent + dx[i];
            if (snackArm[xNou][yNou] == 0 && inMatrice(xNou, yNou)) {
                xCoada.push(xNou);
                yCoada.push(yNou);

                snackArm[xNou][yNou] = 1 + snackArm[xCurent][yCurent];
                //snackArm[xNou][yNou] = i;
            }
        }
    }

    for (int i = 1; i <= nrRanduri; ++i) {
        for (int j = 1; j <= nrColoane; ++j) {
            if (snackArm[i][j] < 10) {
                cout << ' ' << snackArm[i][j] << ' ';
            }
            else {
                cout << ' ' << snackArm[i][j] ;
            }
        }
        cout << "\n";
    }

    g << snackArm[lEndRow][lEndColumn] - 1;
}

int main()
{
    //citire();
    //citire2();
    //citire3();
    //citire4();
    citire5();
    //rezolvare1();
    //rezolvare2();
    //rezolvare3();
    //rezolvare4();
    //rezolvare5();
    rezolvare6();
    return 0;
}

/// Main - end ////////////////////////////////////////////////////////////

/// Citiri si altele ------------------------------------------------

void citire5() {
    citire4();
    f >> defekt;
}

void citire4() {
    f >> row;
    indexToNumbers(row);

    nrColoane = coloanaITN;
    nrRanduri = randITN;

    cout << nrColoane << " " << nrRanduri << '\n';

    f >> row;
    indexToNumbers(row);

    lStartColumn = coloanaITN;
    lStartRow = randITN;

    cout << lStartColumn << " " << lStartRow<< '\n';

    f >> row;
    indexToNumbers(row);

    lEndColumn = coloanaITN;
    lEndRow = randITN;

    cout << lEndColumn << " " << lStartColumn << '\n';
}

void citire3() {
    f >> row;
    nrColoane = row[0] - 64;
    nrRanduri = toNumber(row[1]);
    if (row[2] != 0) {
        nrRanduri *= 10;
        nrRanduri += toNumber(row[2]);
    }

    cout << nrColoane << ' ' << nrRanduri << '\n';

    for (int i = 1; i <= nrColoane; ++i) {
        for (int j = 1; j <= nrRanduri; ++j) {
            f >> snackGrid[i][j];
            cout << snackGrid[i][j] << ' ';
        }
        cout << '\n';
    }

    cout << "\n";

    for (int i = 1; i <= nrColoane; ++i) {
        for (int j = 1; j <= nrRanduri; ++j) {
            f >> snackStock[i][j];
            cout << snackStock[i][j] << " ";
        }
        cout << "\n";
    }

    cout << "\n";

    f >> nrOfOrders;
    for (int i = 1; i <= nrOfOrders; ++i) {
        f >> row;
        indexToNumbers(row);
        orders[1].push_back(coloanaITN);
        orders[2].push_back(randITN);

        cout << coloanaITN << " " << randITN << "\n";
    }
}

void citire2() {
    f >> row;
    nrColoane = row[0] - 64;
    nrRanduri = toNumber(row[1]);
    if (row[2] != 0) {
        nrRanduri *= 10;
        nrRanduri += toNumber(row[2]);
    }

    cout << nrColoane << ' ' << nrRanduri << '\n';

    for (int i = 1; i <= nrColoane; ++i) {
        for (int j = 1; j <= nrRanduri; ++j) {
            f >> snackGrid[i][j];
            cout << snackGrid[i][j] << ' ';
        }
        cout << '\n';
    }

    f >> row;
    selectColoana = row[0] - 64;
    selectRand = toNumber(row[1]);
    if (row[2] != 0) {
        selectRand *= 10;
        selectRand += toNumber(row[2]);
    }

    price = snackGrid[selectColoana][selectRand];

    cout << selectColoana << ' ' << selectRand << '\n';

    f >> n;
    for (int i = 1; i <= n; ++i) {
        f >> bani[i];
        suma += bani[i];
    }
    cout << suma << '\n';
}

void populareValCent() {
    valoareCent[1] = 1;
    valoareCent[2] = 2;
    valoareCent[3] = 5;
    valoareCent[4] = 10;
    valoareCent[5] = 20;
    valoareCent[6] = 50;
    valoareCent[7] = 100;
    valoareCent[8] = 200;
}

void citire() {
    f >> price;
    f >> n;
    for (int i = 1; i <= n; ++i) {
        f >> bani[i];
        suma += bani[i];
    }

}

int toNumber(char a) {
    return a-48;
}

void indexToNumbers(string row) {
    randITN = row[0] - 64;
    coloanaITN = toNumber(row[1]);
    if (row[2] != 0) {
        coloanaITN *= 10;
        coloanaITN += toNumber(row[2]);
    }
}