빠른 다리

$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 \leq n \leq 500$, $2 \leq k \leq 10^9$). $n$은 다리의 수, $k$는 도시의 크기다.

이어지는 $n$개의 줄에는 네 정수 $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$). 모든 튜플 $(x_1, y_1, x_2, y_2)$는 서로 다르다.

모든 칸 쌍의 최단 거리 합을 $998\,244\,353$으로 나눈 나머지 한 정수를 출력한다.

첫 번째 입력에서는 모든 칸 쌍의 최단 거리가 1이므로 합은 6이다.