## Editorial for Bedao Regular Contest 05 - SQRSUM

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author:

#### Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 1e5+5;
const int LOG = 20;
const ll MOD = 1e9+7;
const ll INF = 1e15+5;
const int SQRT = 44721;

int n, m, q;
vector<vector<ll>> mat, pref;
vector<vector<vector<ll>>> ver, hor, corner_1, corner_2;
vector<pii> color[MAX];

ll rect(int x1, int y1, int x2, int y2) {
return pref[x2][y2]-pref[x1-1][y2]-pref[x2][y1-1]+pref[x1-1][y1-1];
}

void precompute() {
fo(i, 1, n) {
fo(j, 1, m) {
pref[i][j] = mat[i][j]+pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
}
}

fo(i, 1, n) {
fo(j, 1, m) {
int temp = min(i, j);
ver[i][j].assign(temp+1, 0);
if(temp > 1) ver[i][j][1] = rect(i-1, j-1, i, j);
fo(k, 2, temp-1) ver[i][j][k] = rect(i-k, j-k, i, j)-rect(i-k+1, j-k+1, i-1, j-1)+ver[i][j][k-1]+ver[i-1][j-1][k-1]-ver[i-1][j-1][k-2];
}
}
// corner_1
fo(i, 1, n) {
fo(j, 1, m) {
int temp = min(i, j);
corner_1[i][j].assign(temp, 0);
fo(k, 1, temp-1) corner_1[i][j][k] = ver[i][j][k]+corner_1[i][j-1][k-1];
}
}
// corner_2
fo(i, 1, n) {
fo(j, 1, m) {
int temp = min(i, j);
corner_2[i][j].assign(temp, 0);
fo(k, 1, temp-1) corner_2[i][j][k] = ver[i][j][k]+corner_2[i-1][j][k-1];
}
}
//hor
fo(i, 1, n) {
fo(j, 1, m) {
int temp = min(i, j);
hor[i][j].assign(temp+1, 0);
fo(k, 1, temp-1) hor[i][j][k] = ver[i][j][k]+hor[i][j-1][k];
}
}
//ver
fo(i, 1, n) {
fo(j, 1, m) {
int temp = min(i, j);
fo(k, 1, temp-1) ver[i][j][k] = ver[i][j][k]+ver[i-1][j][k];
}
}
}

ll get(int c1, int c2) {
ll res = 0;
foa(p1, color[c1]) {
foa(p2, color[c2]) {
int x1 = min(p1.fi, p2.fi), y1 = min(p1.se, p2.se), x2 = max(p1.fi, p2.fi), y2 = max(p1.se, p2.se);
int dx = x2-x1, dy = y2-y1;
if(dx == 0 || dy == 0) continue;
if(dx < dy) {
x1 += dx;
y1 += dx;
res ^= hor[x2][y2][dx]-hor[x1][y1-1][dx]+corner_1[x1][y1-1][dx-1]+corner_2[x2-1][y2][dx-1];
}
else {
x1 += dy;
y1 += dy;
res ^= ver[x2][y2][dy]-ver[x1-1][y1][dy]+corner_2[x1-1][y1][dy-1]+corner_1[x2][y2-1][dy-1];
}
}
}
return res;
}

signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("SQRSUM.INP", "r", stdin);
//    freopen("SQRSUM.OUT", "w", stdout);
cin >> n >> m >> q;
mat.assign(n+1, vector<ll>(m+1, 0));
pref.assign(n+1, vector<ll>(m+1, 0));
ver.assign(n+1, vector<vector<ll>>(m+1, vector<ll>()));
hor.assign(n+1, vector<vector<ll>>(m+1, vector<ll>()));
corner_1.assign(n+1, vector<vector<ll>>(m+1, vector<ll>()));
corner_2.assign(n+1, vector<vector<ll>>(m+1, vector<ll>()));
fo(i, 1, n) {
fo(j, 1, m) {
cin >> mat[i][j];
}
}
fo(i, 1, n) {
fo(j, 1, m) {
int c;
cin >> c;
color[c].pb(mk(i, j));
}
}

precompute();
while(q--) {
int c1, c2;
cin >> c1 >> c2;
cout << get(c1, c2) << "\n";
}
}

/*
3 3 1
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
1 2 3
4 5 6
7 8 9
1 9
*/