Clarke and points

克拉克是一名精神分裂患者。某一天克拉克变成了一位几何研究学者。  
他研究一个有趣的距离，曼哈顿距离。点$A(x_A, y_A)$和点$B(x_B, y_B)$的曼哈顿距离为$|x_A-x_B|+|y_A-y_B|$。  
现在他有$n$个这样的点，他需要找出两个点$i, j$使得曼哈顿距离最大。  

第一行是一个整数$T(1 \le T \le 5)$，表示数据组数。  
每组数据第一行为两个整数$n, seed(2 \le n \le 1000000, 1 \le seed \le 10^9)$，表示点的个数和种子。  

$n$个点的坐标是这样得到的：

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);

对于每组数据输出一行，表示最大的曼哈顿距离。

2
3 233
5 332

1557439953
1423870062