Fast Bridges

Time limit2sMemory limit1024 MB

Summary

Given a k by k grid plus n bridges that cut travel time, find the sum of shortest distances over all cell pairs modulo 998244353.

Level: Hard10 of 10
Topics: Shortest path, Sorting, Math, Combinatorics
Solved: No attempts yet

Problem

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

People can walk from any cell to a neighbouring cell (sharing a side) in $1$ unit of time.

The 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)$ with $x_1 \neq x_2$ and $y_1 \neq y_2$ . People can travel from one end of a bridge to the other in $|x_1 - x_2| + |y_1 - y_2| - 1$ units of time.

To analyze how much faster the city became, compute the sum of shortest distances between all pairs of cells. Since the sum can be large, output it modulo $998\,244\,353$ .

Input

The first line contains two integers $n$ and $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 < x_2 \leq k$ , $1 \leq y_1, y_2 \leq k$ , $y_1 \neq y_2$ ). All tuples $(x_1, y_1, x_2, y_2)$ are different.

Output

Print a single integer: the sum of shortest distances between all pairs of cells, modulo $998\,244\,353$ .

Hint

In the first input, the shortest distance between every pair of cells is $1$ , so the sum is $6$ .

Examples3

Example 1
Input
```
2 2
1 1 2 2
1 2 2 1
```
Expected output
```
6
```
Example 2
Input
```
0 1000000000
```
Expected output
```
916520226
```

Example 3

Input

Expected output