$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

참고

첫 번째 예제에서, 모든 칸의 쌍 사이의 최단 거리는 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