CF1774G.Segment Covering

ChthollyNotaSeniorious gives DataStructures a number axis with $m$ distinct segments on it. Let $f(l,r)$ be the number of ways to choose an even number of segments such that the union of them is exactly $[l,r]$ , and $g(l,r)$ be the number of ways to choose an odd number of segments such that the union of them is exactly $[l,r]$ .

ChthollyNotaSeniorious asked DataStructures $q$ questions. In each query, ChthollyNotaSeniorious will give DataStructures two numbers $l, r$ , and now he wishes that you can help him find the value $f(l,r)-g(l,r)$ modulo $998\,244\,353$ so that he wouldn't let her down.

The first line of input contains two integers $m$ ( $1 \leq m \leq 2 \cdot 10^5$ ) and $q$ ( $1 \leq q \leq 2 \cdot 10^5$ ) — the number of segments and queries, correspondingly.

The $i$ -th of the next $m$ lines contains two integers $x_i$ and $y_i$ ( $1 \leq x_i < y_i \leq 10^9$ ), denoting a segment $[x_i, y_i]$ .

It is guaranteed that all segments are distinct. More formally, there do not exist two numbers $i, j$ with $1 \le i < j \le m$ such that $x_i = x_j$ and $y_i = y_j$ .

The $i$ -th of the next $q$ lines contains two integers $l_i$ and $r_i$ ( $1 \leq l_i < r_i \leq 10^9$ ), describing a query.

For each query, output a single integer — $f(l_i,r_i)-g(l_i,r_i)$ modulo $998\,244\,353$ .

In the first query, we have to find $f(1, 4) - g(1, 4)$ . The only subset of segments with union $[1, 4]$ is $\{[1, 3], [2, 4]\}$ , so $f(1, 4) = 1, g(1, 4) = 0$ .

In the second query, we have to find $f(1, 5) - g(1, 5)$ . The only subsets of segments with union $[1, 5]$ are $\{[1, 3], [2, 4], [3, 5]\}$ and $\{[1, 3], [3, 5]\}$ , so $f(1, 5) = 1, g(1, 5) = 1$ .