Рассмотрим квадратный город размера $k \times k$. В каждой клетке находится ровно один дом. Люди могут перемещаться из любой клетки в соседнюю (только по стороне) за 1 единицу времени. Правительство решило построить $n$ быстрых мостов, чтобы улучшить город. Каждый быстрый мост соединяет две клетки $(x_1, y_1)$ и $(x_2, y_2)$ такие, что $x_1 \neq x_2$ и $y_1 \neq y_2$. Люди могут перемещаться из одного конца моста в другой за $|x_1 - x_2| + |y_1 - y_2| - 1$ единиц времени. Чтобы проанализировать, насколько быстрее стал город, вас просят вычислить сумму кратчайших расстояний между всеми парами клеток. Поскольку она может быть большой, найдите её по модулю $998\,244\,353$.

Входные данные

Первая строка содержит два целых числа $n, k$ ($0 \le n \le 500$, $2 \le k \le 10^9$) — количество мостов и размер города. Каждая из следующих $n$ строк содержит четыре целых числа $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.