409628: GYM103648 E Bird Watching

You have recently started a bird-watching tour company! After hiring tour guides and stocking up on binoculars, it's time to talk business.

You know of $$$n$$$ excellent trails in the area. Although the birds come and go, trail $$$i$$$ can have anywhere between $$$a_i$$$ and $$$b_i$$$ birds at any point in time.

We consider two trips to be different if they occur on different paths, or if they encounter different numbers of birds.

You currently have $$$m$$$ potential customers, who each have very specific preferences. Customer $$$i$$$ hopes to see between $$$c_i$$$ and $$$d_i$$$ birds on their trips ($$$1 \leq c_i \leq d_i \leq 10^5$$$). You home to tell these customers how many unique trips could satisfy their specifications, to attract them to your business.

Given $$$N$$$, $$$M$$$, and the associated bird quanitities, help each customer determine how many unique trips matching their specifications they could experience.

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^5)$$$, representing the number of known trails, and the number of customers respectively.

The next $$$n$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i \leq b_i \leq 10^5$$$), the number of birds that each trail could have.

The next $$$m$$$ lines contain two integers $$$c_i$$$ and $$$d_i$$$ ($$$1 \leq c_i \leq d_i \leq 10^5$$$), the number of birds each customer hopes to see.

Output $$$m$$$ lines, where the $$$i$$$-th line describes how many unique trips match customer $$$i$$$'s specifications.

3 2
1 8
2 5
5 8
1 3
5 5

5
3