#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iomanip>
#include <utility>
#include <queue>
#include <algorithm>
#include <iterator>


using namespace std;

class Node {
public:
	Node () : i(0), j(0), state(0), sec(0), previ(0), prevj(0), key(0) {}
	Node (int i1, int j1, int st, int sc, int pi, int pj, int kk) {
		i = i1;
		j = j1;
		state = st;
		sec = sc;
		previ = pi;
		prevj = pj;
		key = kk;
	}
	int i, j;
	int state;
	int sec;
	int previ;
	int prevj;
	int key;
};

class Prev {
public:
	Prev() : i(0), j(0), state(0), key(0) {}
	Prev(int ii, int jj, int st, int k) : i(ii), j(jj), state(st), key(k) {}
	int i, j, state, key;
};

ifstream file;
vector<string> hra;
vector < vector <bool> > used;
vector < vector <bool> > inq;
vector < vector <Prev> > prevv;
vector <pair <pair<int, int>, pair<int, int> > > out;

pair<int, int> startv;
pair<int, int> endv;

queue<Node> q;

void load();
void inic();
bool bfs();
void add_neigh(Node & x);
void write_path();

int n, m;
int n2, m2;