考虑一个大小为 $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

说明

在第一个样例中，所有单元格对之间的最短距离均为 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