406886: GYM102599 E M~--- многомерность

E. M — многомерностьограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Многие в детстве играют с кубиками, затем все в школе изучают геометрию и встречаются с такими простыми объектами, как параллелепипеды. Но ведь изучать геометрию в трехмерном пространстве — это так скучно! Даже четырехмерным пространством уже никого не удивишь! Поэтому в этой задаче мы предлагаем вам изучить параллелепипеды в $$$M$$$-мерном пространстве. Чувствуете, как интересно?

Определим $$$M$$$-мерный параллелепипед как набор отрезков $$$[a_1, b_1], [a_2, b_2], \ldots, [a_M, b_M]$$$, где $$$a_i < b_i$$$ для всех $$$i = 1 \ldots M$$$. Для простоты будем считать, что все $$$a_i$$$ и $$$b_i$$$ являются целыми.

Скажем, что точка с координатами $$$(x_1, x_2, \ldots, x_M)$$$ лежит внутри параллелепипеда, если выполнены неравенства:

$$$a_1 \leq x_1 \leq b_1,$$$ $$$a_2 \leq x_2 \leq b_2,$$$ $$$\dots$$$ $$$a_M \leq x_M \leq b_M.$$$

Вам даны $$$N$$$ $$$M$$$-мерных параллелепипедов. Требуется посчитать, сколько точек с целочисленными координатами лежат внутри ровно $$$N-1$$$ параллелепипеда. Так как ответ может быть большим, выведите остаток от деления количества точек на число $$$998\,244\,353$$$.

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

В первой строке записаны два числа $$$N$$$ и $$$M$$$ ($$$2 \leq N \leq 2 \cdot 10^5, 1 \leq M \leq 2 \cdot 10^5, 2 \leq N \cdot M \leq 2 \cdot 10^5$$$) — количество параллелепипедов и размерность пространства соответственно.

Каждая из следующих $$$N$$$ строк задает параллелепипед. В каждой строке через пробел записаны $$$2 \cdot M$$$ чисел в следующем порядке: $$$a_1, b_1, a_2, b_2, \ldots, a_M, b_M$$$ ($$$-10^6 \leq a_i < b_i \leq 10^6$$$ для всех $$$i$$$).

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

Выведите одно число — остаток от деления количества точек, лежащих внутри ровно $$$N-1$$$ параллелепипеда, на число $$$998\,244\,353$$$.

ПримерыВходные данные

2 2
2 4 1 5
1 4 4 6

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

15

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

4 1
1 6
2 4
6 7
2 9

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

4

Примечание

Рисунок к первому примеру, в котором даны два прямоугольника. Необходимо посчитать все целочисленные точки, которые лежат внутри (или на границе) ровно одного прямоугольника. В данном примере таких точек 15. Все эти точки отмечены на рисунке.

Во втором примере $$$M=1$$$, значит параллелепипеды являются обыкновенными отрезками на прямой.