Problem E
Eyeballing Extraterrestials

Nevada has been working hard to incentivise companies to move their offices there, both by active forest restoration and tax incentives. And it has worked! Companies moved their main offices there, and people soon followed suit.

Most families decided to buy houses along the Nevada state route $375$ (SR $375$), which for our purposes can be considered a long non-branching road. This previously desolate highway is now the location of $N$ houses, some possibly vacant, all on the same side of the road. All the $F$ families that live here have a lot of money. So much money, in fact, that they all have a vacation house as well. Because they all now love Nevada so much, they have obviously decided to have their vacation house along the SR $375$ as well. The home of family $i$ is located at $loc_{H,i}$ and their vacation house is located at $loc_{V,i}$.

Lately, a lot of explosions and alien sounds have come from Area $51$. Although this family neighbourhood isn’t too religious about the entire alien thing, they are all a bit cautious. What if there actually are aliens escaping, and what if they manage to kidnap and steal the identities of one of the families? Or maybe they will just occupy a vacant house without us noticing?

“The Surveillance Camera Company” (SCC) has for that reason seen great potential for selling a lot of cameras to this recently rich suburban area. They have managed to encourage all the families to “observe” and “take care of” their neighbours by watching them through surveillance cameras.

More specifically, they’ve gone to family $i = 1$ and asked what kind of camera package they want: They can either pick one that will cover the nearest $H_ i$ houses near their home (excluding their own), or one that covers the nearest $V_ i$ houses near their vacation home (again excluding their own). Every family always picks one package, the one for the house with the least cameras already placed near their neighbour’s houses on average. If there is a tie, they prefer to have the cameras near their homes.

Mathematically speaking, if $h_{i,j}$ is the $j$th closest house to family $i$’s home, and $v_{i,j}$ is the $j$th closest house to their vacation house, then they will pick the home package if and only if

Of course, all $M_ i$ family members want their own surveillance camera to watch on, so they buy and place $M_ i$ cameras for each neighbouring house they want to “observe”. Then, the surveillance camera seller continues on to the next family ($i + 1$) until all the families have bought a camera set.

A vague, yet menacing government agency has heard about the sales of these cameras. They wonder if the security’s tight enough that they need to add in additional measures, or if the neighbourhood “watch” is sufficient enough. For that reason, they need to detect whether there are enough cameras near a range of continuous houses, and they need your help.

Input

The first line contains two integers, $N$ and $F$: The number of houses and the number of families.

Then follow $F$ lines, one for each family. Each line contains $5$ integers: $M_ i$, $loc_{H,i}$, $H_ i$, $loc_{V,i}$ and $V_ i$, as described in the problem statement above.

Finally, a line with an integer $Q$ follows, representing the number of queries the vague, yet menacing government agency wants to perform. Then $Q$ lines follow, each containing two integers $Q_{start,i}$ and $Q_{end,i}$, representing the query “how many cameras are there in the house range $[Q_{start,i},Q_{end,i}]$?”.

Output

For each query, print out the total number of cameras in that particular house range after all cameras have been installed.

Limits

• $2 < N \leq 200\, 000$

• $0 < F < 100\, 000$

• $0 < loc_{H,i}, loc_{V,i} \leq N$

• $0 < H_ i, V_ i < N$, and $H_ i$ and $V_ i$ are divisible by $2$

• $0 < M_ i < 10$

• $0 < Q < 20\, 000$

• $0 < Q_{start,i} \leq Q_{end,i} \leq N$

• Families can live with other families in the same house. They can even live at someone’s vacation house, and can share a vacation house with another family.

Sample Explanation

Figure 1: Each step of the camera installation in Sample Input 1. H is the family’s home, h is their closest neighbours, V is their vacation home, and v is their closest vacation home neighbours

10 3
3 1 4 6 2
2 2 4 7 4
9 7 2 7 4
4
1 3
4 6
7 7
6 10

6
19
0
24