## Problem Description

Clarke is a patient with multiple personality disorder. One day he turned into a learner of geometric.
He did a research on a interesting distance called Manhattan Distance. The Manhattan Distance between point $A(x_A,y_A)$ and point $B(x_B,y_B)$ is $|x_A−x_B|+|y_A−y_B|$.
Now he wants to find the maximum distance between two points of n points.

## Input

The first line contains a integer $T(1≤T≤5)$, the number of test case.
For each test case, a line followed, contains two integers n,seed $(2≤n≤1000000,1≤seed≤10^9)$, denotes the number of points and a random seed.
The coordinate of each point is generated by the followed code.

long long seed;
inline long long rand(long long l, long long r) {
static long long mo=1e9+7, g=78125;
return l+((seed*=g)%=mo)%(r-l+1);
}

// ...

cin >> n >> seed;
for (int i = 0; i < n; i++)
x[i] = rand(-1000000000, 1000000000),
y[i] = rand(-1000000000, 1000000000);

## Output

For each test case, print a line with an integer represented the maximum distance.

2
3 233
5 332

1557439953
1423870062

## Translation

The Manhattan Distance between point $A(x_A,y_A)$ and point $B(x_B,y_B)$ is $|x_A−x_B|+|y_A−y_B|$.

## Analysis

$$|x_A−x_B|+|y_A−y_B|$$

$$x_A-x_B+y_A-y_B \\ x_B-x_A+y_A-y_B \\ x_A-x_B+y_B-y_A \\ x_B-x_A+y_B-y_A$$

## Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1000005;
const long long INF=1e9;
int T,n,x[maxn],y[maxn];
long long seed;
long long A[maxn],B[maxn],maxa,mina,maxb,minb;

// A[i]=Xi+Yi;
// B[i]=Xi-Yi;

inline long long rand(long long l, long long r) {
static long long mo=1e9+7, g=78125;
return l+((seed*=g)%=mo)%(r-l+1);
}

inline void build(int n,int seed){
for (int i=0;i<n;i++)
x[i]=rand(-1000000000,1000000000),
y[i]=rand(-1000000000,1000000000),
A[i]=x[i]+y[i],maxa=max(maxa,A[i]),mina=min(mina,A[i]),
B[i]=x[i]-y[i],maxb=max(maxb,B[i]),minb=min(minb,B[i]);
}

inline void init(){
maxa=maxb=-INF;
mina=minb=INF;
}

int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}

int main(){