codeforces#P1774G. Segment Covering

    ID: 33487 远端评测题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>brute forcecombinatoricsconstructive algorithmsdata structuresdptrees

Segment Covering

Description

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$.

Input

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.

Output

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

4 2
1 3
4 6
2 4
3 5
1 4
1 5
1
0

Note

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$.