CF138C.Mushroom Gnomes - 2

One day Natalia was walking in the woods when she met a little mushroom gnome. The gnome told her the following story:

Everybody knows that the mushroom gnomes' power lies in the magic mushrooms that grow in the native woods of the gnomes. There are n trees and m magic mushrooms in the woods: the i-th tree grows at a point on a straight line with coordinates a__i and has the height of h__i, the j-th mushroom grows at the point with coordinates b__j and has magical powers z__j.

But one day wild mushroommunchers, the sworn enemies of mushroom gnomes unleashed a terrible storm on their home forest. As a result, some of the trees began to fall and crush the magic mushrooms. The supreme oracle of mushroom gnomes calculated in advance the probability for each tree that it will fall to the left, to the right or will stand on. If the tree with the coordinate x and height h falls to the left, then all the mushrooms that belong to the right-open interval [x - h, x), are destroyed. If a tree falls to the right, then the mushrooms that belong to the left-open interval (x, x + h] are destroyed. Only those mushrooms that are not hit by a single tree survive.

Knowing that all the trees fall independently of each other (i.e., all the events are mutually independent, and besides, the trees do not interfere with other trees falling in an arbitrary direction), the supreme oracle was also able to quickly calculate what would be the expectation of the total power of the mushrooms which survived after the storm. His calculations ultimately saved the mushroom gnomes from imminent death.

Natalia, as a good Olympiad programmer, got interested in this story, and she decided to come up with a way to quickly calculate the expectation of the sum of the surviving mushrooms' power.

一天，娜塔莉亚正在森林中散步，偶遇了一位小蘑菇地精。地精向她讲述了如下故事：

众所周知，蘑菇地精的力量源于生长在其故乡森林中的魔法蘑菇。森林中有 $n$ 棵树和 $m$ 个魔法蘑菇：第 $i$ 棵树生长在一条直线上的坐标 $a_i$ 处，高度为 $h_i$；第 $j$ 个蘑菇生长在坐标 $b_j$ 处，其魔力值为 $z_j$。

然而某天，蘑菇地精的死敌——野生蘑菇吞噬者，向他们的家园森林发动了一场可怕的风暴。结果，部分树木开始倾倒并压毁魔法蘑菇。蘑菇地精至高先知预先计算出了每棵树向左倾倒、向右倾倒或保持直立的概率。若一棵位于坐标 $x$、高度为 $h$ 的树向左倾倒，则所有位于右开区间 $[x - h,\, x)$ 内的蘑菇都将被摧毁；若该树向右倾倒，则所有位于左开区间 $(x,\, x + h]$ 内的蘑菇将被摧毁。只有未被任何一棵树击中的蘑菇才能幸存下来。

已知所有树木的倾倒相互独立（即所有事件彼此独立，且一棵树的倾倒不会影响其他树向任意方向倾倒），至高先知还迅速计算出了风暴过后幸存蘑菇总魔力值的期望值。这一计算最终使蘑菇地精免于灭顶之灾。

身为一名优秀的信息学奥赛选手，娜塔莉亚对这个故事产生了浓厚兴趣，并决定设计一种方法，以快速计算风暴过后幸存蘑菇魔力值总和的期望值。

The first line contains two integers n and m (1 ≤ n ≤ 105, 1 ≤ m ≤ 104) — the number of trees and mushrooms, respectively.

Each of the next n lines contain four integers — a__i, h__i, l__i, r__i (|a__i| ≤ 109, 1 ≤ h__i ≤ 109, 0 ≤ l__i, r__i, l__i + r__i ≤ 100) which represent the coordinate of the i-th tree, its height, the percentage of the probabilities that the tree falls to the left and to the right, respectively (the remaining percentage is the probability that the tree will stand on).

Each of next m lines contain two integers b__j, z__j (|b__j| ≤ 109, 1 ≤ z__j ≤ 103) which represent the coordinate and the magical power of the j-th mushroom, respectively.

An arbitrary number of trees and mushrooms can grow in one point.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^5$，$1 \leq m \leq 10^4$），分别表示树的数量和蘑菇的数量。

接下来的 $n$ 行中，每行包含四个整数：$a_i$、$h_i$、$l_i$、$r_i$（$|a_i| \leq 10^9$，$1 \leq h_i \leq 10^9$，$0 \leq l_i,\, r_i$，且 $l_i + r_i \leq 100$），分别表示第 $i$ 棵树的坐标、高度，以及该树向左倒、向右倒的概率百分比（剩余百分比即为该树保持直立的概率）。

再接下来的 $m$ 行中，每行包含两个整数 $b_j$、$z_j$（$|b_j| \leq 10^9$，$1 \leq z_j \leq 10^3$），分别表示第 $j$ 个蘑菇的坐标及其魔法力量。

任意数量的树和蘑菇均可生长在同一个位置。

Print a real number — the expectation of the total magical power of the surviving mushrooms. The result is accepted with relative or absolute accuracy 10 - 4.

输出一个实数——幸存蘑菇的总魔法值的期望值。结果在相对误差或绝对误差 $10^{-4}$ 范围内均被接受。

It is believed that the mushroom with the coordinate x belongs to the right-open interval [l, r) if and only if l ≤ x < r. Similarly, the mushroom with the coordinate x belongs to the left-open interval (l, r] if and only if l < x ≤ r.

In the first test the mushroom survives with the probability of 50%, depending on where the single tree falls.

In the second test the mushroom survives only if neither of the two trees falls on it. It occurs with the probability of 50%  ×  50% = 25%.

Pretest №12 is the large test with 105 trees and one mushroom.

人们认为，坐标为 $x$ 的蘑菇属于右开区间 $[l, r)$ 当且仅当 $l ≤ x < r$。类似地，坐标为 $x$ 的蘑菇属于左开区间 $(l, r]$ 当且仅当 $l < x ≤ r$。

在第一个测试中，蘑菇存活的概率为 50%，该概率取决于唯一一棵树倒下的位置。

在第二个测试中，蘑菇仅当两棵树均未倒在其上时才能存活。这种情况发生的概率为 $50\% × 50\% = 25\%$。

预测试 №12 是一个大规模测试，包含 $10^5$ 棵树和 1 个蘑菇。