小可可和小多来到了一个网格图上进行最短路训练。

这是一个 $n × n$ 的网格图，对于点 $(x, y)$，如果 $y < n$，则它向 $(x, y + 1)$ 有一条有向边，边权为 $ea_{x,y}$；如果 $x < n$，则它向 $(x + 1, y)$ 有一条有向边，边权为 $eb_{x,y}$。小可可需要在很短的时间内找到从 $(1, 1)$ 到 $(n, n)$ 的最短路。

然而，小多会捣乱 $q$ 次：小雪会删去图中的一条边，然后小可可就需要重新计算 $(1, 1)$ 到 $(n, n)$ 的最短路。当小可可计算完成后，小多就会恢复这条边。即：每次小多删掉的边只会影响到这一次小可可的计算。

小可可坚持尝试不借助外力，自己每次计算出答案。可惜小可可不是机器人，没过一会儿他就晕倒了。于是，计算最短路的任务就落到了你的头上。

输入格式

为避免过大的输入量，网格图边的边权将在程序内生成。

第一行两个正整数 $n, q$，表示网格的大小和小多捣乱的次数。

第二行两个整数 $seed$ 和 $B$，为辅助数据生成的变量。请保证它们为全局变量且 $seed$ 是 $64$ 位无符号整形变量。

接下来按照从第一行到第 $n$ 行，第一列到第 $n-1$ 列的顺序生成 $ea_{i,j}$ :每次生成时先调用一次 xorshift64()，再将 $ea_{i,j}$ 赋值为 seed&(2B − 1)。其中 & 表示二进制按位且运算，xorshift64() 在题目最后给出。

再接下来按照从第一行到第 $n-1$ 行，第一列到第 $n$ 列的顺序生成 $eb_{i,j}$：每次生成时先调用一次xorshift64()，再将 $eb_{i,j}$ 赋值为 seed&(2B − 1)。

请严格按照上述过程生成数据，中途不能自行改变 $seed$ 和 $B$ 的值，否则数据将错误生成。

接下来 q 行，每行四个整数 $x, y, x' , y'$，表示小多捣乱删掉的一条边。保证 $x ' = x, y' = y + 1$ 或 $y' = y, x' = x + 1$。

再次提醒，请不要自行改动 $seed，B$，xorshift64() 函数和程序读入/生成数据的顺序。

此数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

输出格式

输出 $q$ 行，每行一个整数，表示删掉给定边后 $(1, 1)$ 到 $(n, n)$ 的最短路。

样例 #1

样例输入 #1

4 4
10583998785722269293 2
2 2 2 3
2 3 3 3
1 2 2 2
1 1 1 2

样例输出 #1

5
4
7
9

提示

数据规模与约定

对于 $20\%$ 的数据，满足 $n, q \le 5, B = 1$；

对于 $40\%$ 的数据，满足 $n, q \le 300$；

对于 $70\%$ 的数据，满足 $n \le 300$；

对于 100% 的数据，有 $2 \le n \le 5000, 1 \le q \le 10^{5}, 1 \le B \le 30, 1 \le x, y, x', y' \le n$。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 1;
const int inff = 1e18 + 1;
int n, q;
unsigned long long seed, b;
int e[N][N], e_[N][N];
int f[N][N], f1[N][N];
int ans;
inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

void xorshift64() {
	seed ^= seed << 13;
	seed ^= seed >> 7;
	seed ^= seed << 17;
}

void build() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < n; j++) {
			xorshift64();
			e[i][j] = seed & ((1 << b) - 1);
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			xorshift64();
			e_[i][j] = seed & ((1 << b) - 1);
		}
	}
}

void solve() {
	for (int i = 1; i <= n; i++) f[i][0] = f[0][i] = inff;
	f[0][1] = 0;
	for (int i = 2; i <= n; i++) f[1][i] = f[1][i - 1] + e[1][i - 1];
	for (int i = 2; i <= n; i++) f[i][1] = f[i - 1][1] + e_[i - 1][1];
	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= n; j++) {
			f[i][j] = min(f[i][j - 1] + e[i][j - 1], f[i - 1][j] + e_[i - 1][j]);
		}
	}
//	for (int i = 2; i <= n; i++) {
//			for (int j = 2; j <= n; j++) {
//			cout << f[i][j] << endl;
//			}
	for (int i = 1; i <= n; i++) f1[n + 1][i] = f1[i][n + 1] = inff;
	f1[n + 1][n] = 0;
//		}
	for (int i = n - 1; i >= 1; i--) f1[n][i] = f1[n][i + 1] + e[n][i];
	for (int i = n - 1; i >= 1; i--) f1[i][n] = f1[i + 1][n] + e_[i][n];
	for (int i = n; i >= 1; i--) {
		for (int j = n; j >= 1; j--) {
			f1[i][j] = min(f1[i][j + 1] + e[i][j], f1[i + 1][j] + e_[i][j]);
		}
	}
//	for (int i = n - 1; i >= 1; i--) {
//			for (int j = n - 1; j >= 1; j--) {
//				cout << f1[i][j] << endl;
//			}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr);
	n = read(), q = read();
	seed = read(), b = read();
//	cin >> seed >> b;
	build();
	solve();
	for (int i = 1; i <= q; i++) {
		int x, y, x_, y_;
		ans = inff;
		x = read(), y = read(), x_ = read(), y_ = read();
//		cin >> x >> y >> x_ >> y_;
		if (x == x_) {
			for (int i = 1; i <= n; i++) {
				if (i != x) {
					ans = min(ans, f[i][y] + e[i][y] + f1[i][y_]);
				}
			}
		}
		if (y == y_) {
			for (int i = 1; i <= n; i++) {
				if (i != y) {
					ans = min(ans, f[x][i] + e_[x][i] + f1[x_][i]);
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

超时了，求助（在哪改）