Consideremos una ciudad cuadrada de tamaño $k \times k$. Hay exactamente una casa en cada celda.

Las personas pueden ir de cualquier celda a una celda vecina (solo por los lados) en 1 unidad de tiempo.

El gobierno decidió construir $n$ puentes rápidos para mejorar la ciudad. Cada puente rápido conecta dos celdas $(x_1, y_1)$ y $(x_2, y_2)$ tales que $x_1 = x_2$ y $y_1 \neq y_2$. Las personas pueden ir de un extremo del puente al otro en $|x_1 - x_2| + |y_1 - y_2| - 1$ unidades de tiempo.

Para analizar qué tan rápido se volvió la ciudad, se le pide calcular la suma de las distancias más cortas entre todos los pares de celdas. Dado que puede ser grande, calcúlela módulo $998\,244\,353$.

Entrada

La primera línea contiene dos enteros $n, k$ ($0 \le n \le 500$, $2 \le k \le 10^9$) — el número de puentes y el tamaño de la ciudad.

Cada una de las siguientes $n$ líneas contiene cuatro enteros $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$). Se garantiza que todas las tuplas $(x_1, y_1, x_2, y_2)$ son diferentes.

Salida

Imprima un solo entero — la respuesta al problema.

Ejemplos

Entrada 1

2 2
1 1 2 2
1 2 2 1

Salida 1

6

Nota

En el primer ejemplo, la distancia más corta entre todos los pares de celdas es 1, por lo que la suma es 6.

Entrada 2

0 1000000000

Salida 2

916520226

Entrada 3

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

Salida 3

946