Description

Format

Input

Output

输出共 q 行，每行一个整数表示答案。

Samples

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

1
0

样例2 interval2.in interval2.out

Limitation

1s, 512MiB for each test case.