1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>

const size_t bit_size = 1048576;
const size_t mod_size = 840;

std::vector<std::vector<short>> edge[mod_size];
std::vector<std::bitset<bit_size>> tab[mod_size];

void make_component(std::bitset<bit_size> &output, std::vector<std::pair<int, std::string> > *city, bool *vis, int &it, size_t &time) {
	for (size_t i = 0; i < city[it].size(); ++i) {
		if (vis[city[it][i].first]) continue;

		if (std::abs(it - city[it][i].first) == 1) {
			if (city[it][i].second[time % city[it][i].second.length()] == '1') {
				vis[city[it][i].first] = true;
				output[city[it][i].first] = 1;
				make_component(output, city, vis, city[it][i].first, time);
			}
		}
		else {
			if (city[it][i].second[time % city[it][i].second.length()] == '0') {
				vis[city[it][i].first] = true;
				output[city[it][i].first] = 1;
				make_component(output, city, vis, city[it][i].first, time);
			}
		}
	}
	return;
}

void BFS(int &time, int it, int end, bool &find, long long &score, short deep, std::set<std::pair<short, short> > &que) {
	que.erase(que.begin());
	if (find) return;
	if (tab[(time + deep) % mod_size][it][end] == 1) {
		find = true;
		score = deep;
		return;
	}
	
	for (size_t i = 0; i < edge[(time + deep) % mod_size][it].size(); ++i)
		que.insert(std::make_pair(deep + 1, edge[(time + deep) % mod_size][it][i]));

	while (!que.empty())
		BFS(time, que.begin()->second, end, find, score, que.begin()->first, que);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	
	int q, a, b;
	std::cin >> a >> b >> q;
	const int n = a, m = b;
	
	std::string **cross = new std::string *[n];
	for (int i = 0; i < n; ++i)
		cross[i] = new std::string [m];

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) 
			std::cin >> cross[i][j];

	std::vector<std::pair<int, std::string> > city[(n + 1) * (m + 1)];
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			city[i * (m + 1) + j].push_back(std::make_pair(i * (m + 1) + j + 1, cross[i][j])); // 0 1
			city[i * (m + 1) + j + 1].push_back(std::make_pair(i * (m + 1) + j, cross[i][j])); // 1 0
			city[i * (m + 1) + j].push_back(std::make_pair((i + 1) * (m + 1) + j, cross[i][j])); // 0 3
			city[(i + 1) * (m + 1) + j].push_back(std::make_pair(i * (m + 1) + j, cross[i][j])); // 3 0
			city[(i + 1) * (m + 1) + j].push_back(std::make_pair((i + 1) * (m + 1) + j + 1, cross[i][j])); // 3 4
			city[(i + 1) * (m + 1) + j + 1].push_back(std::make_pair((i + 1) * (m + 1) + j, cross[i][j])); // 4 3
			city[i * (m + 1) + j + 1].push_back(std::make_pair((i + 1) * (m + 1) + j + 1, cross[i][j])); // 1 4
			city[(i + 1) * (m + 1) + j + 1].push_back(std::make_pair(i * (m + 1) + j + 1, cross[i][j])); // 4 1
		}

	for (int i = 0; i < n; ++i)
		delete [] cross[i];
	delete [] cross;

	for (size_t i = 0; i < mod_size; ++i) {
		bool *vis = new bool [(n + 1) * (m + 1)];
		for (int i = 0; i < (n + 1) * (m + 1); ++i)
			vis[i] = false;

		for (int j = 0; j < (n + 1) * (m + 1); ++j)
			if (!vis[j]) {
				vis[j] = true;
				std::bitset<bit_size> component;
				component.reset();
				component[j] = 1;
				make_component(component, city, vis, j, i);
				tab[i].push_back(component);
			}

		delete [] vis;
	}

	for (size_t i = 0; i < mod_size; ++i) {
		for (size_t j = 0; j < tab[i].size(); ++j) {
			std::vector<short> zero;
			edge[i].push_back(zero);
			for (size_t k = 0; k < tab[(i + 1) % mod_size].size(); ++k) {
				std::bitset<bit_size> temp = tab[i][j] & tab[(i + 1) % mod_size][k];
				if (temp.any())
					edge[i][j].push_back(k);
			}
		}
	}


	while (q > 0) {
		long long t;
		int a, b, c, d;
		std::cin >> t >> a >> b >> c >> d;
		
		int it;
		for (size_t i = 0; i < tab[t % mod_size].size(); ++i)
			if (tab[t % mod_size][i][a * (m + 1) + b] == 1) {
				it = i;
				break;
			}
		long long score = 0;
		bool find = false;
		std::set<std::pair<short, short> > que;
		que.insert(std::make_pair(0, 0));
		int time = t % mod_size;
		BFS(time, it, c * (m + 1) + d, find, score, 0, que);
		std::cout << t + score << '\n';
		--q;
	}

	return 0;
}