Clarke and points

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)


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.


The first line contains a integer $T(1 \le T \le 5)$, the number of test case.
For each test case, a line followed, contains two integers $n, seed(2 \le n \le 1000000, 1 \le seed \le 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);


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

Sample Input

2 3 233 5 332

Sample Output

1557439953 1423870062




BestCoder Round #72 (div.2)