#2244. Algorithmic Engagements 2011 Kangury 拍摄

Algorithmic Engagements 2011 Kangury 拍摄

Background

Special for beginners, ^_^

Description

Byteman将要去澳大利亚拍摄袋鼠。准备好一切之后他发现在镜片方面可能要出问题。Byteman有一套不同参数的镜片。每个镜片都有最佳拍摄距离(区间),在这个距离范围之外的袋鼠要么太大以至于无法在照片上完整呈现,要么就太小。

Byteman已经知道了确切的行程。他将按顺序访问一系列的拍摄点。向导已经告诉他,在每个拍摄点出现的袋鼠离拍摄点的距离范围。

现在Byteman想知道应该携带哪个镜片。他觉得,计算每片镜片的最长连续有效拍摄点对他的决定会有帮助。即,最长的一段连续的拍摄点,使得镜片在这些拍摄点都有效。如果存在一个距离,使得它属于镜片的最佳拍摄距离与某个拍摄点袋鼠的出现范围,那么镜片在这个拍摄点有效。注意这些区间都是闭区间,即包含左右两个端点。

Format

Input

第一行为两个整数N,M (1<=N<=50,000,1<=M<=2000),依次代表观察点的数量和镜片的数量。接下来行,每行两个数字ai,bi(1<=ai<=bi<=1),代表这个观察点袋鼠出现的距离范围。接下来行,每行两个数字Ci,Di(1<=Ci<=Di<=1),代表这个镜片的最佳拍摄距离范围。

Output

输出行,每行一个正整数,代表这个镜片的最长连续有效拍摄点的拍摄点数量。

Samples

3 3
2 5
1 3
6 6
3 5
1 10
7 9
2
3
0

Limitation

1s, 1024KiB for each test case.