City Influence

Time limit2sMemory limit64 MB

Summary

Add N weighted rectangles on a billion by billion grid and print the sum of squared cell values modulo 1,000,000,007.

Level: Medium7 of 10
Topics: Segment tree, Sorting, Prefix sum
Solved: No attempts yet

Problem

A new city is being built. Seen from above the city is a plane, and that plane is cut into $10^9 \times 10^9$ cells of equal size. The top left cell is $(1, 1)$ and the bottom right cell is $(10^9, 10^9)$ . Every cell carries a number that records the influence on that cell, and every number starts at $0$ .

The city will contain many public facilities, so before construction the planners estimated the influence each facility spreads around it. One estimate has this form.

Add $p$ to every cell $(x, y)$ with $a \le x \le c$ and $b \le y \le d$ .

After all estimates are applied, the influence of one cell is the square of the number written on it, and the influence of the city is the sum of the influence of all cells.

Suppose there are these two estimates.

Add $1$ to every cell $(x, y)$ with $1 \le x \le 2$ and $1 \le y \le 3$ .
Add $2$ to every cell $(x, y)$ with $1 \le x \le 3$ and $2 \le y \le 3$ .

Cells $(1, 1)$ and $(2, 1)$ then hold $1$ , cells $(1, 2)$ , $(1, 3)$ , $(2, 2)$ , $(2, 3)$ hold $3$ , cells $(3, 2)$ and $(3, 3)$ hold $2$ , and every other cell holds $0$ . The influence of the city is $1^2 \times 2 + 3^2 \times 4 + 2^2 \times 2 = 46$ .

Given $N$ estimates, write a program that computes the influence of the city after all of them are applied.

Input

The first line contains the number of estimates $N$ ( $1 \le N \le 10^5$ ).

Each of the next $N$ lines contains $a$ , $b$ , $c$ , $d$ , $p$ ( $1 \le a \le c \le 10^9$ , $1 \le b \le d \le 10^9$ , $1 \le p \le 100$ ) separated by spaces. Each line is one estimate as described above.

Output

Print the influence of the city after all estimates are applied. The answer can be very large, so print it modulo 1,000,000,007.

Examples7

Example 1
Input
```
2
1 1 2 3 1
1 2 3 3 2
```
Expected output
```
46
```
Example 2
Input
```
1
1 1 1 1 1
```
Expected output
```
1
```
Example 3
Input
```
1
7 9 7 9 100
```
Expected output
```
10000
```
Example 4
Input
```
1
1 1 1000000000 1000000000 1
```
Expected output
```
49
```
Example 5
Input
```
2
2 2 3 3 3
2 2 3 3 4
```
Expected output
```
196
```
Example 6
Input
```
2
1 1 2 2 5
3 1 4 2 5
```
Expected output
```
200
```
Example 7
Input
```
3
1 1 6 6 1
2 2 5 5 2
3 3 4 4 3
```
Expected output
```
272
```