考慮一個大小為 $k \times k$ 的方形城市，每個格子裡恰好有一棟房子。 人們可以在 1 個單位時間內從任何一個格子移動到相鄰的格子（僅限上下左右）。

政府決定建造 $n$ 座快速橋樑來改善城市交通。每座快速橋樑連接兩個格子 $(x_1, y_1)$ 和 $(x_2, y_2)$，其中 $x_1 \neq x_2$ 且 $y_1 \neq y_2$。人們可以在 $|x_1 - x_2| + |y_1 - y_2| - 1$ 個單位時間內從橋樑的一端移動到另一端。

為了分析城市交通改善的程度，請計算所有格子對之間最短距離的總和。由於數值可能很大，請輸出其對 $998\,244\,353$ 取模後的結果。

輸入格式

第一行包含兩個整數 $n, k$ ($0 \le n \le 500, 2 \le k \le 10^9$)，分別代表橋樑的數量與城市的大小。

接下來的 $n$ 行，每行包含四個整數 $x_1, y_1, x_2, y_2$ ($1 \le x_1 < x_2 \le k, 1 \le y_1, y_2 \le k, y_1 \neq y_2$)。 保證所有元組 $(x_1, y_1, x_2, y_2)$ 皆不相同。

輸出格式

輸出一個整數，代表問題的答案。

範例

輸入格式 1

2 2
1 1 2 2
1 2 2 1

輸出格式 1

6

輸入格式 2

0 1000000000

輸出格式 2

916520226

輸入格式 3

5 5
1 1 3 3
3 3 5 1
3 3 4 5
3 3 5 4
1 5 3 3

輸出格式 3

946

說明

在第一個範例中，所有格子對之間的最短距離皆為 1，因此總和為 6。