401730: GYM100519 B Bring Your Own Bombs

A sabotage platoon has completed its mission and planted some bombs on an enemy territory. Now they are about to report to their commanders how many enemy units will be destroyed. They have assigned this task to you.

The enemy territory is represented by a tile grid where the enemy platoons are located. Enemy units are standing in platoons that are represented by accurate rectangles, and they do not intersect each other. Each tile contains at most one enemy unit. Bombs have awesome firepower that can destroy all enemy units on the same tile line with the bomb: either horizontal or vertical, but not both. Unfortunately, all bombs are created manually by inexperienced engineers, and therefore, it is very hard to say how and if they explode or not. Only two values are known for certain for each bomb: p₁, the probability that the bomb will explode horizontally, and p₂, the probability that the bomb will explode vertically. It is implicitly known that with probability of 100% - p₁ - p₂ the bomb will not explode at all.

The sabotage platoon only plants the bombs outside the enemy platoons. Given the description of the enemy territory and planted bombs, you are to calculate the expected number of destroyed enemy units.

The first line contains two integers N and M: the number of enemy platoons and bombs respectively (1 ≤ N, M ≤ 10⁵).

The next N lines of input contain the descriptions of enemy platoons, one per line. Each platoon is described by four integers x₁, y₁, x₂, y₂: the coordinates of the tiles at the opposite corners of the rectangle (x₁ ≤ x₂, y₁ ≤ y₂).

Then the next M lines of input contain the description of bombs, one per line. Each bomb is described by integers x, y and numbers p₁, p₂: the coordinates of the tiles with bombs and the quality characteristics of the bombs given as an non-negative integer percentage respectively (p₁ + p₂ ≤ 100).

All coordinates do not exceed 10⁹ by absolute value.

Output must contain a single real number: the answer to the problem with absolute or relative error no more than 10^- 9.

1 1
-1 -1 1 1
0 3 33 33

0.990000000000000

1 2
1 1 5 5
0 2 100 0
2 0 0 100

9.000000000000000

2 2
0 3 2 5
3 0 5 2
1 1 30 60
4 4 50 40

4.980000000000000