J. Fast Bridges
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Let us consider a square city of size $$$k \times k$$$. There is exactly one house in each cell.

People can go from any cell to neighbouring cell (only by side) in $$$1$$$ unit of time.

Government decided to build $$$n$$$ fast bridges to make the city better. Each fast bridge connects two cells $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ such that $$$x_1 \neq x_2$$$ and $$$y_1 \neq y_2$$$. People can go from one end of the bridge to another in $$$|x_1 - x_2| + |y_1 - y_2| - 1$$$ units of time.

To analyze how the city became faster, you are asked to calculate the sum of shortest distances between all pairs of cells. Since it can be large, find it modulo $$$998\,244\,353$$$.

Input

The first line contains two integers $$$n$$$, $$$k$$$ ($$$0 \leq n \leq 500$$$, $$$2 \leq k \leq 10^9$$$) — the number of bridges and the size of the city.

Each of the next $$$n$$$ lines contains four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \leq x_1 \lt x_2 \leq k$$$, $$$1 \leq y_1, y_2 \leq k$$$, $$$y_1 \neq y_2$$$). It is guaranteed that all tuples $$$(x_1, y_1, x_2, y_2)$$$ are different.

Output

Print a single integer — the answer to the problem.

Examples
Input
2 2
1 1 2 2
1 2 2 1
Output
6
Input
0 1000000000
Output
916520226
Input
5 5
1 1 3 3
3 3 5 1
3 3 4 5
3 3 5 4
1 5 3 3
Output
946
Note

In the first example, the shortest distance between all pairs of cells is $$$1$$$, so the sum is $$$6$$$.