题目描述

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

这是一个 $n \times 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 \& (2^B - 1)$。其中 $\&$ 表示二进制按位且运算，xorshift64() 的参考代码如下：

unsigned long long seed;
int B;

// xorshift64 算法，不能修改
unsigned long long xorshift64(){
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}

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

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

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

如果你仍不会生成数据，下面的这一份代码已经实现好了所有的数据读入/生成，你可以直接使用在你的代码中。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 全局变量 seed 和 B
unsigned long long seed;
int B;

// xorshift64 算法，不能修改
unsigned long long xorshift64(){
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	
    int n, q;
    cin >> n >> q;
	
    cin >> seed >> B;
	
    vector<vector<ll>> ea(n+1, vector<ll>(n+1, 0)); // 横向边权：从 (i,j) 到 (i,j+1)， j=1..n-1
    vector<vector<ll>> eb(n+1, vector<ll>(n+1, 0)); // 纵向边权：从 (i,j) 到 (i+1,j)， i=1..n-1
	
    // 生成横向边权：遍历 i=1..n, j=1..n-1
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n-1; j++){
            xorshift64();
            ea[i][j] = seed & ((1ULL << B) - 1);
        }
    }
	
    // 生成纵向边权：遍历 i=1..n-1, j=1..n
    for (int i = 1; i <= n-1; i++){
        for (int j = 1; j <= n; j++){
            xorshift64();
            eb[i][j] = seed & ((1ULL << B) - 1);
        }
    }
    // 你可以从这里开始编写你的代码
    return 0;
}

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

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

输出格式

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

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

5
4
7
9

提示

数据规模与约定

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

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

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

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