You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Input

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of intervals and the number of queries, respectively.

Each of the next $n$ lines contains two integer numbers $l_i$ and $r_i$ ($0 \le l_i < r_i \le 5 \cdot 10^5$) — the given intervals.

Each of the next $m$ lines contains two integer numbers $x_i$ and $y_i$ ($0 \le x_i < y_i \le 5 \cdot 10^5$) — the queries.

Output

Print $m$ integer numbers. The $i$-th number should be the answer to the $i$-th query: either the minimal number of intervals you have to take so that every point (not necessarily integer) from $x_i$ to $y_i$ is covered by at least one of them or -1 if you can't choose intervals so that every point from $x_i$ to $y_i$ is covered.

2 3
1 3
2 4
1 3
1 4
3 4

1
2
1

3 4
1 3
1 3
4 5
1 2
1 3
1 4
1 5

1
1
-1
-1

Note

In the first example there are three queries:

1. query $[1; 3]$ can be covered by interval $[1; 3]$;
2. query $[1; 4]$ can be covered by intervals $[1; 3]$ and $[2; 4]$. There is no way to cover $[1; 4]$ by a single interval;
3. query $[3; 4]$ can be covered by interval $[2; 4]$. It doesn't matter that the other points are covered besides the given query.

In the second example there are four queries:

1. query $[1; 2]$ can be covered by interval $[1; 3]$. Note that you can choose any of the two given intervals $[1; 3]$;
2. query $[1; 3]$ can be covered by interval $[1; 3]$;
3. query $[1; 4]$ can't be covered by any set of intervals;
4. query $[1; 5]$ can't be covered by any set of intervals. Note that intervals $[1; 3]$ and $[4; 5]$ together don't cover $[1; 5]$ because even non-integer points should be covered. Here $3.5$, for example, isn't covered.