问题描述
小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上,第 i 条线段的左端点在 li,右端点在 ri。小明用 m 个区间去框这些线段,第 i 个区间的范围是 [Li,Ri]。如果一个线段有至少一半的长度被包含在某个区间内,则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?
输入格式
输入共 n+m+1 行。
第一行为两个正整数 n,m。
后面 n 行,每行两个整数 li,ri。
后面 m 行,每行两个整数 Li,Ri。
输出格式
输出共 m 行,每行一个整数。
样例
3 2
1 2
1 3
3 4
1 4
2 4
3
2
评测用例规模与约定
对于 20% 的数据,保证 n,m≤103。
对于 100% 的数据,保证 n,m≤105,li<ri,0<li,ri,Li,Ri≤106,max{ri−li}≤min{Ri−Li}.