题目描述

规划师 Nora 负责评估一座方形城市的新交通方案。这座城市由 $k\times k$ 个方格组成，每个方格中恰好有一户居民。

居民可以从一个方格走到与它有公共边的相邻方格，每走一步需要 $1$ 单位时间。

为了缩短通勤时间，政府决定修建 $n$ 座快桥。每座快桥连接两个方格 $(x_1,y_1)$ 与 $(x_2,y_2)$，并满足 $x_1\ne x_2$ 且 $y_1\ne y_2$。通过快桥从一端到另一端所需时间为

现在需要评估快桥建成后的城市效率。请计算所有不同方格对之间的最短距离之和。由于答案可能很大，请输出它对 $998244353$ 取模后的结果。

输入格式

第一行包含两个整数 $n,k$，分别表示快桥数量和城市边长。

接下来 $n$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一座连接 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的快桥。

保证所有四元组 $(x_1,y_1,x_2,y_2)$ 两两不同。

输出格式

输出一行一个整数，表示答案。

数据范围

• $0\le n\le 500$；
• $2\le k\le 10^9$；
• $1\le x_1<x_2\le k$；
• $1\le y_1,y_2\le k$；
• $y_1\ne y_2$。

样例 1

输入

2 2
1 1 2 2
1 2 2 1

输出

6

解释

在这个样例中，任意两个不同方格之间的最短距离都是 $1$，因此总和为 $6$。

样例 2

输入

0 1000000000

输出

916520226

样例 3

输入

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

输出

946