Problem G
Garbage Tracking

Talulla has been hired to fix an issue for Sgudal Cleaning - a company that specialises in making garbage cleaning robots for the city New Glasgow. Instead of collecting garbage from the streets, the cleaning robots now dump garbage instead! In fact, the cleaning robots now emit a fixed amount of garbage between two intersections. Fortunately, Sgudal Cleaning now has managed to stop all the robots from doing more harm.

To understand the extent of the garbage problem, Talulla has made a program to find out the total amount of garbage there is in a particular area of the city. This looked hard at first, but fortunately, New Glasgow is designed as a perfect grid, and the robots walk in rectangular paths in the city. The sections Talulla is asked to look at are rectangular as well.

Talulla has completed her version of the program, but wants to ensure she has implemented it correctly. She has therefore asked you to implement a version to compare it with.

Figure 1: The city grid in Sample Input 1, after the robots have dumped their garbage. The origin is marked by a dot, and the highlighted rectangle represents the last query.

Input

The first line consists of two integers $R$ and $Q$, the total number of robot movements and queries.

Then follow $R$ lines, each describing a robot’s path. Each line contains $5$ integers $x_ i$, $y_ i$, $w_ i$, $h_ i$, $c_ i$. A robot has completed a rectangular walk, starting at the intersection at $(x_ i, y_ i)$. The walk went $w_ i$ blocks east, $h_ i$ blocks north, $w_ i$ blocks west and finally $h_ i$ blocks south, dumping $c_ i$ kg of garbage between each intersection it visited.

Finally, $Q$ lines follow, one line for each query. Each line contains $4$ integers $x_ i$ $y_ i$ $w_ i$ $h_ i$. Sgudal Cleaning wants to know how much garbage there is in the $w_ i \times h_ i$ block rectangle, where the lower left corner is the intersection at $(x_ i, y_ i)$.

As the input may be very large, you should consider buffering it.

Output

For each query, print out the amount of garbage in kg there is in the given rectangle, including the edges.

Limits

• $1 \leq R, Q \leq 200\, 000$

• $x_ i$, $y_ i$, $w_ i$, $h_ i$ and $c_ i$ are all integers.

• $-2\, 250 \leq x_ i, y_ i < 2\, 250$

• $-2\, 250 < x_ i + w_ i, y_ i + h_ i \leq 2\, 250$

• $0 < c_ i \leq 1\, 200$

3 8
0 0 3 4 3
-1 -1 3 3 1
2 0 1 1 5
-1 -1 2 2
0 0 2 2
1 1 1 2
0 0 2 2
1 1 1 3
2 2 1 1
2 0 1 1
2 0 1 2

10
21
2
21
5
3
27
31