$k \times k$ の正方形の都市を考える。各セルにはちょうど1軒の家がある。 人々は、隣接するセル（辺を共有するセル）へ1単位時間で移動できる。

政府は都市をより便利にするために $n$ 本の高速道路を建設することにした。各高速道路は2つのセル $(x_1, y_1)$ と $(x_2, y_2)$ を結ぶ。人々は橋の一端からもう一端へ $|x_1 - x_2| + |y_1 - y_2| - 1$ 単位時間で移動できる。

都市がどれだけ速くなったかを分析するために、すべてのセルのペア間の最短距離の総和を計算せよ。値が非常に大きくなる可能性があるため、998 244 353 で割った余りを求めよ。

入力

1行目には、橋の数 $n$ と都市のサイズ $k$ が与えられる ($0 \le n \le 500, 2 \le k \le 10^9$)。 続く $n$ 行の各行には、4つの整数 $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 である。