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
#include "bits/stdc++.h" // Ignacy Boehlke
using namespace std;     // XIII LO Szczecin
template<class A, class B> ostream& operator << (ostream& os, const pair<A, B>& p) {return os << '{' << p.first << ", " << p.second << '}';}
template<class T> auto operator << (ostream& os, const T& v) -> decltype(v.begin(), os) {os << '{';for (auto i : v) os << i << ", ";return os << '}';}
#ifdef DEBUG
#define D(x...) x
#else
#define D(x...)
#endif
#define LN(x) D(cerr << #x << ": " << x << ' ')
#define LOG(x) D(cerr << #x << ": " << x << '\n')
#define ssize(x) ((int)x.size())
#define FOR(a, b, c) for(int a = (b); a <= (c); ++a)
#define REP(a, b) FOR(a, 0, b - 1)
#define ALL(x) (x).begin(), (x).end()
#define fi first
#define se second
using ll = long long;
constexpr int MAX = 840;
using Light = bitset<MAX>;

void getlight(Light& l) {
    int c, sz = 0;
    while ((c = getchar_unlocked()) != '0' && c != '1') {}
    l[sz++] = (c == '1');
    while ((c = getchar_unlocked()) == '0' || c == '1') l[sz++] = (c == '1');
    FOR(i, sz, MAX - 1) l[i] = l[i - sz];
}

int gi() {
    int c;
    while ((c = getchar_unlocked()) < '0' || '9' < c) {}
    int ret = c - '0';
    while ('0' <= (c = getchar_unlocked()) && c <= '9') ret = ret * 10 + c - '0';
    return ret;
}

void putint(int x) {
    vector<char> str;
    str.reserve(10);
    do {
        str.push_back((char)(x % 10 + '0'));
        x /= 10;
    } while (x);
    reverse(ALL(str));
    for (char c : str) putchar_unlocked(c);
}

using pii = pair<int, int>;
vector<int> res, st = {0}, t;
void dfs(int v, int h, vector<vector<pair<int, pii>>>& queue, vector<Light>& lines) {
    auto it = lower_bound(ALL(queue[h]), make_pair(v, make_pair(0, 0)));
    for (; it != queue[h].end() && it->fi == v; ++it) {
        res[it->se.fi] = max(res[it->se.fi], t[it->se.fi] + st.back() - st[ssize(st) - it->se.se - 1]);
        LN(h); LN(*it); LOG(st);
    }
    if (h == ssize(lines) || lines[h][v]) return;
    st.emplace_back(st.back());
    do {
        dfs(v, h + 1, queue, lines);
        v = (v ? v - 1 : MAX - 1);
        ++st.back();
    } while(lines[h][v]);
    st.pop_back();
}

int main() {
    int n = gi(), m = gi(), q = gi(); 
    res.resize(q);
    t.resize(q);
    vector<Light> rows(n), cols(m);
    REP(i, n) rows[i].flip();
    REP(i, m) cols[i].flip();
    Light in;
    REP(i, n) REP(j, m) {
        getlight(in);
        rows[i] &= in;
        cols[j] &= ~in;
    }
    vector<vector<pair<int, pii>>> rowd(n + 1), rowu(n + 1), colr(m + 1), coll(m + 1);

    REP(i, q) {
        res[i] = t[i] = gi();
        int y1 = gi(), x1 = gi(), y2 = gi(), x2 = gi();
        if (y1 < y2)      rowd[n - y1].emplace_back(t[i] % MAX, make_pair(i, y2 - y1));
        else if (y1 > y2) rowu[y1].emplace_back(t[i] % MAX, make_pair(i, y1 - y2));
        if (x1 < x2)      colr[m - x1].emplace_back(t[i] % MAX, make_pair(i, x2 - x1));
        else if (x1 > x2) coll[x1].emplace_back(t[i] % MAX, make_pair(i, x1 - x2));
    }

    REP(i, n + 1) sort(ALL(rowd[i])), sort(ALL(rowu[i]));
    REP(i, m + 1) sort(ALL(colr[i])), sort(ALL(coll[i]));
    LOG(rowd); LOG(rowu); LOG(colr); LOG(coll);

    REP(i, MAX) dfs(i, 0, rowu, rows);
    reverse(ALL(rows));
    REP(i, MAX) dfs(i, 0, rowd, rows);
    REP(i, MAX) dfs(i, 0, coll, cols);
    reverse(ALL(cols));
    REP(i, MAX) dfs(i, 0, colr, cols);

    REP(i, q) putint(res[i]), putchar_unlocked('\n');
}