Xét một thành phố hình vuông kích thước $k \times k$. Có đúng một ngôi nhà trong mỗi ô.

Mọi người có thể đi từ bất kỳ ô nào sang ô lân cận (chỉ theo cạnh) trong 1 đơn vị thời gian.

Chính phủ quyết định xây dựng $n$ cây cầu tốc độ cao để cải thiện thành phố. Mỗi cây cầu tốc độ cao kết nối hai ô $(x_1, y_1)$ và $(x_2, y_2)$ sao cho $x_1 \neq x_2$ và $y_1 \neq y_2$. Mọi người có thể đi từ đầu này đến đầu kia của cây cầu trong $|x_1 - x_2| + |y_1 - y_2| - 1$ đơn vị thời gian.

Để phân tích xem thành phố đã trở nên nhanh hơn như thế nào, bạn được yêu cầu tính tổng các khoảng cách ngắn nhất giữa tất cả các cặp ô. Vì kết quả có thể rất lớn, hãy tìm kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n, k$ ($0 \le n \le 500, 2 \le k \le 10^9$) — số lượng cầu và kích thước của thành phố.

Mỗi dòng trong $n$ dòng tiếp theo chứa bốn số nguyê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$).

Đảm bảo rằng tất cả các bộ $(x_1, y_1, x_2, y_2)$ đều khác nhau.

Dữ liệu ra

In ra một số nguyên duy nhất — câu trả lời cho bài toán.

Ví dụ

Dữ liệu vào 1

2 2
1 1 2 2
1 2 2 1

Dữ liệu ra 1

6

Ghi chú

Trong ví dụ đầu tiên, khoảng cách ngắn nhất giữa tất cả các cặp ô là 1, vì vậy tổng là 6.

Dữ liệu vào 2

0 1000000000

Dữ liệu ra 2

916520226

Dữ liệu vào 3

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

Dữ liệu ra 3

946