题目描述

小Z在练习街头的套圈游戏，为了简化，仅进行一维直线上的套圈。

现有 $n$ 个奖品，每个奖品所处的位置分别为 $l_i\sim r_i$。小Z扔出了 $m$ 个“圈”，每个圈扔到的位置为 $x_i\sim y_i$。

为了让自己练习成果更好看，小Z决定某个物品只要至少一半被套住了，就算成功。询问小Z的每个“圈”套住了几个奖品。

输入格式

输入共 $n + m + 1$ 行。

第一行为两个正整数 $n, m$。

后面 $n$ 行，每行两个整数 $l_i, r_i$，表示每个奖品的范围。

后面 $m$ 行，每行两个整数 $x_i, y_i$，表示小Z扔出去的圈的位置。

输出格式

输出共 $m$ 行，每行一个整数，表示每个“圈”套住的奖品数。

输入输出样例

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

3
2

样例 $\tt \#1$说明

第一个“圈”：$[1,4]$ 套住了第一个奖品 $[1,2]$、第二个奖品 $[1,3]$、第三个奖品 $[3,4]$

第二个“圈”：$[2,4]$ 套住了第二个奖品 $[1,3]$、第三个奖品 $[3,4]$

数据范围

• 对于 $20\%$ 的数据，保证 $n, m \le 10^3$。
• 对于 $100\%$ 的数据，保证 $n, m ≤ 10^5$，$l_i < r_i$，$0 < l_i, r_i, x_i, y_i \le 10^6$，$\max \{r_i − l_i\} \le \min \{y_i − x_i\}$。