G. Покрытие отрезками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

ChthollyNotaSeniorious дает DataStructures числовую ось с $$$m$$$ различными отрезками на ней. Пусть $$$f(l,r)$$$  — количество способов выбрать четное число отрезков так, чтобы их объединение было равно $$$[l,r]$$$, а $$$g(l,r)$$$  — количество способов выбрать нечетное число отрезков так, чтобы их объединение было равно $$$[l,r]$$$.

ChthollyNotaSeniorious задал DataStructures $$$q$$$ вопросов. В каждом вопросе ChthollyNotaSeniorious дает DataStructures два числа $$$l, r$$$, и хочет, чтобы вы помогли ему найти значение $$$f(l,r)-g(l,r)$$$ по модулю $$$998\,244\,353$$$, чтобы он не подвел ее.

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

Первая строка ввода содержит два целых числа $$$m$$$ ($$$1 \leq m \leq 2 \cdot 10^5$$$) и $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$)  — количество отрезков и запросов, соответственно.

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \leq x_i < y_i \leq 10^9$$$), обозначающие отрезок $$$[x_i, y_i]$$$.

Гарантируется, что все отрезки попарно различны. Более формально, не существует двух чисел $$$i, j$$$ при $$$1 \le i < j \le m$$$ таких, что $$$x_i = x_j$$$ и $$$y_i = y_j$$$.

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i < r_i \leq 10^9$$$), описывающие запрос.

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

Для каждого запроса выведите одно целое число  — $$$f(l_i,r_i)-g(l_i,r_i)$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
4 2
1 3
4 6
2 4
3 5
1 4
1 5
Выходные данные
1
0
Примечание

В первом запросе мы должны найти $$$f(1, 4) - g(1, 4)$$$. Единственное подмножество отрезков с объединением $$$[1, 4]$$$ это $$$\{[1, 3], [2, 4]\}$$$, поэтому $$$f(1, 4) = 1, g(1, 4) = 0$$$.

Во втором запросе нам нужно найти $$$f(1, 5) - g(1, 5)$$$. Единственными подмножествами отрезков с объединением $$$[1, 5]$$$ являются $$$\{[1, 3], [2, 4], [3, 5]\}$$$ и $$$\{[1, 3], [3, 5]\}$$$, поэтому $$$f(1, 5) = 1, g(1, 5) = 1$$$.