skrzyzowania

#include <iostream>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>


using namespace std;

constexpr int lcm = 840;

constexpr int levels = 15;

class tablica3d{
    vector<int16_t> data;
public:
    size_t mp1;
    size_t m_lc;
    tablica3d( size_t Mp1, size_t LCM, size_t levs ){
        mp1 = Mp1;
        m_lc = Mp1 * LCM;
        data.resize(mp1*LCM*levs);
    }
    int16_t& at(size_t x, size_t time, size_t level){
        return data[ x + mp1*time + m_lc * level  ];
    }
};



int marsz_w_przod(  tablica3d & ruch_w_przod, int x_start, int x_stop, int time ){

    while (ruch_w_przod.at(x_start,time%lcm,0) < x_stop ){
        int level = levels-1;
        while( (ruch_w_przod.at(x_start,time%lcm,level)>=x_stop) /*&& (level!=0)*/  ){
            level--;
        }
        x_start = ruch_w_przod.at(x_start,time%lcm,level);
        time += (1<<level);
    }
    return time;
}
int marsz_w_tyl(  tablica3d &ruch_w_tyl, int x_start, int x_stop, int time ){

    while (ruch_w_tyl.at(x_start,time%lcm,0) > x_stop ){
        int level = levels-1;
        while( (ruch_w_tyl.at(x_start,time%lcm,level)<=x_stop) /*&& (level!=0)*/  ){
            level--;
        }
        x_start = ruch_w_tyl.at(x_start,time%lcm,level);
        time += (1<<level);
    }
    return time;
}

void skroty( tablica3d &ruch){
    size_t m = ruch.mp1-1;

    for (int level=1; level<levels; level++){
        for (int t=0; t<lcm; t++){
            for (size_t x = 0; x<=m; x++){
                ruch.at(x,t,level) = ruch.at( ruch.at(x,t,level-1) ,(t + (1<<(level-1)))%lcm ,level-1);
            }
        }
    }

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m,q;
    cin>>n>>m>>q;

    vector<vector<string>> skrz (n,vector<string> (m,"")) ;

    for (int y=0; y<n; y++){
        for (int x=0; x<m; x++){
            cin>>skrz[y][x];   ///0 oznacza blok pionowy
        }
    }

    vector<vector<bool>> blok_pion (m, vector<bool> (lcm,true));

    vector<vector<bool>> blok_poziom (n, vector<bool> (lcm, true));

    for (int y=0; y<n; y++){   //da sie zoptymalizowac
        for (int x=0; x<m; x++){
            for (int t=0; t<lcm; t++){
                char znak = skrz[y][x][ t%(skrz[y][x].length()) ];
                if (znak=='0'){//przestaje blokować poziomo
                    blok_poziom[y][t]=false;
                }else{
                    blok_pion[x][t]=false;
                }
            }
        }
    }

//    vector < vector< vector<int16_t> > > ruch_w_prawo( m+1, vector< vector<int16_t> > (lcm,
//         vector<int16_t>(levels,0))  );
    tablica3d ruch_w_prawo(m+1,lcm,levels);
    tablica3d ruch_w_lewo(m+1,lcm,levels);
    tablica3d ruch_w_dol(n+1,lcm,levels);
    tablica3d ruch_w_gore(n+1,lcm,levels) ;


    for( int t=0; t<lcm; t++ ){//jak powszechnie wiadomo....
        int dojde  = m;
        ruch_w_prawo.at(m,t,0) = dojde;
        for (int x = m-1; x>=0; x--){
            if (blok_pion[x][t])
                dojde = x;
            ruch_w_prawo.at(x,t,0) = dojde;
        }
    }

    for( int t=0; t<lcm; t++ ){//...pisanie 10 razy tego samego kodu...
        int dojde  = 0;
        ruch_w_lewo.at(0,t,0) = dojde;
        for (int x = 1; x<=m; x++){
            if (blok_pion[x-1][t])
                dojde = x;
            ruch_w_lewo.at(x,t,0) = dojde;
        }
    }

    for( int t=0; t<lcm; t++ ){//..znaczaca zmniejsza prawdopodobienstwo..
        int dojde  = n;
        ruch_w_dol.at(n,t,0) = dojde;
        for (int y = n-1; y>=0; y--){
            if (blok_poziom[y][t])
                dojde = y;
            ruch_w_dol.at(y,t,0) = dojde;
        }
    }

    for( int t=0; t<lcm; t++ ){//..walniecia glupiego buga
        int dojde  = 0;
        ruch_w_gore.at(0,t,0) = dojde;
        for (int y = 1; y<=n; y++){
            if (blok_poziom[y-1][t])
                dojde = y;
            ruch_w_gore.at(y,t,0) = dojde;
        }
    }

    skroty(ruch_w_prawo);
    skroty(ruch_w_lewo);
    skroty(ruch_w_dol);
    skroty(ruch_w_gore);


    for (int test =0; test < q; test++){//brute
        int time, y_start, x_start, y_stop, x_stop;

        cin >> time>>y_start >> x_start >> y_stop >> x_stop ;

        int t_pion=time;
        int t_poziom=time;
        if (y_stop > y_start){
            t_pion=marsz_w_przod( ruch_w_dol, y_start, y_stop, time );
        }else if (y_stop < y_start){
            t_pion = marsz_w_tyl( ruch_w_gore, y_start, y_stop, time );
        }

        if (x_stop > x_start){
            t_poziom=marsz_w_przod( ruch_w_prawo, x_start, x_stop, time );
        }else if (x_stop < x_start){
            t_poziom = marsz_w_tyl( ruch_w_lewo, x_start, x_stop, time );
        }

        cout << max(t_pion, t_poziom)<<'\n';

    }

    return 0;
}