G. Segment Covering
brute force; combinatorics; constructive algorithms; data structures; dp; trees
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\).