In this HackerEarth Xor Rectangle problem solution, You have an array of N integers S1, S2, ... SN. Consider a N x N matrix such that Aij = Si XOR SJ.
You have been given Q queries. Each query consists of four integers x1, y1, x2, y2 which denotes a submatrix with (x1, y1) as their top-left corner and (x2, y2) as their bottom-right corner such that x1 <= x2 and y1 <= y2. For each query, you have to print the summation of all integers lying in queried submatrix.

## HackerEarth Xor Rectangle problem solution.

```#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
int s[1000011][32];
int p[1000011];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for(int i=1;i<=N;i++) {
cin >> p[i];
for(int j=0;j<20;j++) {
if(p[i]&(1<<j)) {
s[i][j]++;
}
s[i][j]+=s[i-1][j];
}
}
ll o1,o2,z1,z2;
int Q,x1,y1,x2,y2;
cin >> Q;
while(Q--) {
cin >> x1 >> y1 >> x2 >> y2;
ll ans = 0;
rep(j,20) {
o1 = s[x2][j]-s[x1-1][j];
z1 = x2-x1+1 - o1;
o2 = s[y2][j]-s[y1-1][j];
z2 = y2-y1+1 - o2;
ans+=(o1*z2+o2*z1)*(1LL<<j);
}
cout << ans << "\n";
}
}```

### Second solution

```#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define ends asdgahhfdsfshdshfd

#define eps 1e-11
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

#define ldouble long double

using namespace std;

long long INF = 1e9;
const int N = 1200031;

int tests,n;
int ar[N],s[N][22];

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

cin>>n;

for (int i=1;i<=n;i++)
{
cin>>ar[i];
for (int j=0;j<20;j++)
{
s[i][j]=s[i-1][j];
if (ar[i]&(1<<j))
s[i][j]+=1;
}
}

cin>>tests;
for (;tests;--tests)
{
int a,b,c,d;
cin>>a>>c>>b>>d;

long long ans=0;
for (int bit=0;bit<20;bit++)
{
int cnt1=s[b][bit]-s[a-1][bit];
int cnt2=(b-a+1)-cnt1;
int cnt3=s[d][bit]-s[c-1][bit];
int cnt4=(d-c+1)-cnt3;
ans+=(1ll<<bit)*cnt1*cnt4+(1ll<<bit)*cnt2*cnt3;
}
cout<<ans<<"\n";
}

return 0;
}```