#include <climits>
#include <vector>
#include <queue>
using namespace std;
/*
lemma: I will solve subtasks 1 and 2
proof:
*/
queue<vector<int>> q;
long long ans=0;
vector<vector<int>> visitted, exists; // both are [y][x]
vector<vector<bool>> DONE;
void bfs(int I, int x, int y, int curdist, int oy, int ox){
//cout<<"bfs called..\n";
ans %= 1000000000;
vector<int> nxt(6);
curdist++;
nxt[0]=I;
nxt[3]=curdist;
nxt[4]=oy;
nxt[5]=ox;
// coords is [x,y]
visitted[y][x] = I;
if(exists[y+1][x+1] && visitted[y+1][x+1] != I){
if(y >= oy && x >= ox){
ans += curdist;
//bfs(I, x+1, y+1, curdist, oy, ox);
}
nxt[1]=x+1;
nxt[2]=y+1;
q.push(nxt);
}
//cout<<"first check complete..\n";
if(exists[y+1][x-1] && visitted[y+1][x-1] != I){
if(y >= oy && x >= ox){
ans += curdist;
//bfs(I, x-1, y+1, curdist, oy, ox);
}
nxt[1]=x-1;
nxt[2]=y+1;
q.push(nxt);
}
//cout<<"2nd check complete..\n";
if(exists[y-1][x+1] && visitted[y-1][x+1] != I){
//cout<<"3rd check outer alert\n";
if(y >= oy && x >= ox){
//cout<<"3rd check inner alert\n";
ans += curdist;
//bfs(I, x+1, y-1, curdist, oy, ox);
}
nxt[1]=x+1;
nxt[2]=y-1;
q.push(nxt);
}
//cout<<"3rd check complete..\n";
if(exists[y-1][x-1] && visitted[y-1][x-1] != I){
if(y >= oy && x >= ox){
ans += curdist;
//bfs(I, x-1, y-1, curdist, oy, ox);
}
nxt[1]=x-1;
nxt[2]=y-1;
q.push(nxt);
}
//cout<<"returning..\n";
return;
}
int DistanceSum(int N, int *X, int *Y) {
DONE = vector<vector<bool>>(N+1, vector<bool>(N+1, 0));
visitted = vector<vector<int>>(N+5, vector<int>(N+1, 0));
exists = vector<vector<int>>(N+5, vector<int>(N+1, 0));
// find min X and Y values, to translate the graph to start at (1,1)
int minX=INT_MAX-1, minY=INT_MAX-1;
for(int i=0; i<N; i++){
minX = min(minX, X[i]);
minY = min(minY, Y[i]);
}
for(int i=0; i<N; i++){
exists[Y[i]-minY+1][X[i]-minX+1] = 1;
}
vector<int> cur;
for(int i=0; i<N; i++){
bfs(i, X[i]-minX+1, Y[i]-minY+1, 0, X[i]-minX+1, Y[i]-minY+1);
while(!q.empty()){
cur = q.front();
q.pop();
bfs(cur[0], cur[1], cur[2], cur[3], cur[4], cur[5]);
}
}
ans %= 1000000000;
return ans;
}
/*
int main(){
int Y[11] = {2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5};
int X[11] = {5, 6, 3, 6, 3, 4, 5, 6, 3, 4, 6};
//cout<<DistanceSum(10, X, Y)<<"\n";
return 0;
}
*/
