#include "mosaic.h"
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

vector <int> a[200005];
vector<ll> mosaic(vector<int> X, vector<int> Y,vector<int> U, std::vector<int> D,vector<int> L,vector<int> R) {
    int n = SZ(X),q = SZ(U);
    rep(i,0,q - 1){
        U[i]++;D[i]++;L[i]++;R[i]++;    
    }
    rep(i,1,n){
        if(i <= 4) a[i].resize(n + 1);
        else a[i].resize(5);
    }
    rep(i,1,n){
        a[1][i] = X[i - 1];
        a[i][1] = Y[i - 1];
    }
    rep(i,2,n){
        int up = min(n,4);
        if(i <= 4) up = n;
        rep(j,2,up){
            if(!a[i - 1][j] && !a[i][j - 1]) a[i][j] = 1;
            else a[i][j] = 0;
        }
//        rep(j,2,up) cerr << a[i][j] << " ";
//        cerr << endl;
    }
    vector <ll> ans(q);
    rep(i,0,q - 1){
        if(min(U[i],L[i]) <= 4){
            ans[i] = a[U[i]][L[i]];
            continue;
        }
        int rr = min((U[i] - 3) / 2,(L[i] - 3) / 2);
        U[i] -= 2 * rr;L[i] -= 2 * rr;
        assert(min(U[i],L[i]) <= 4 && max(U[i],L[i]) >= 1);
        ans[i] = a[U[i]][L[i]];
    }
    return ans;
}
/*
g++ mosaic.cpp grader2.cpp -o grader.exe -Wall -Wshadow -O2 -std=c++14
*/