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
///MEMENTO MEMO, MEMENTO LONG LONG
#include <bits/stdc++.h>

#define DEBUG if(1)
#define COUT cout << "\e[36m"
#define ENDL "\e[39m" << endl
#define VAR(v) " [\e[32m" << #v << "\e[36m=\e[91m" << v << "\e[36m] "

using namespace std;

typedef long long LL;

int n, m, q;
int bound[2];
const int MAXPATT = 8;

array<vector<array<vector<bool>, MAXPATT+1>>, 2> can_go;
//pattern[side][pos][ptt_len][time]


void parse_pattern(string pattern, int x, int y)
{
    for (int i = 0; i < pattern.size(); ++i)
    {
        int light = pattern[i] - '0';
        can_go[(light)%2][(light) ? y : x][pattern.size()][i] = true;
    }
}
void patterns_prep()
{
    
    for (int i = 0; i < 2; ++i)
    {
        can_go[i].resize(bound[i]);
        for(auto& arr : can_go[i])
        {
            for (int j = 0; j < arr.size(); ++j)
            {
                arr[j].resize(j, false);
            }
        }
    }
}

int wait_time(int bck, int side, int pos, const int s_time)
{
    int time = s_time;
    while(true)
    {
        for (int ptt_len = 2; ptt_len <= MAXPATT; ++ptt_len)
        {
            if(can_go[side][pos - bck][ptt_len][time%ptt_len])
            {
                return time-s_time;
            }
        }
        time++;
    }
}

void process_query()
{
    int s_time;
    cin >> s_time;
    int s_x, s_y;
    int e_x, e_y;
    cin >> s_x >> s_y >> e_x >> e_y;
    int bck = ((s_x > e_x)? 1: 0);
    int time = s_time;
    int x = s_x, y = s_y;
    bool hit = false;
    while (x != e_x)
    {
        int wait = wait_time(bck, 0, x, time);
        time += wait;
        if(wait)
        {
            hit = true;
        }
        x += ((bck)? -1 : 1);
    }
    if(hit)
    {
        cout << time << "\n";
        return;
    }
    bck = ((s_y > e_y)? 1: 0);
    while(y != e_y)
    {
        int wait = wait_time(bck, 1, y, time);
        time += wait;
        y  += ((bck)? -1 : 1);
    }
    cout << time << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    bound[0] = n;
    bound[1] = m;
    patterns_prep();

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            string pattern;
            cin >> pattern;
            parse_pattern(pattern, i, j);
        }
    }
    for (int qi = 0; qi < q; ++qi)
    {
        process_query();

    }
}