Pegs and Legs 是一个圆盘在近乎垂直的板上向下滑动的游戏。板的底部有一些供圆盘落入的位置，称为“腿”（legs）。如果圆盘落入某个腿中，你将获得该腿对应的分数。

你从顶部开始，将圆盘投掷到某个“投掷点”钉子（peg）上，或者直接投掷到某个“投掷点”腿中。当圆盘撞击到一个钉子时，会发生以下三种情况之一：（1）圆盘以概率 $\ell$ 向左落下，（2）圆盘以概率 $r$ 向右落下，或者（3）圆盘以概率 $1 - \ell - r$ 卡住。每个钉子的概率可能不同。如果圆盘向左或向右落下，它将落到另一个钉子或腿上。如果圆盘卡住了，你必须再次从顶部的某个投掷点将其投下。下图展示了第 3 个样例输入，其中两个深色的钉子是投掷点。

由于重力的原因，除非再次投掷，否则圆盘不可能撞击同一个钉子超过一次。游戏持续进行，直到圆盘落入一个腿中，此时你将获得该腿的分数。玩家能获得的最高期望分数是多少？

输入格式

第一行包含两个整数 $L$ ($1 \le L \le 100\,000$)，表示腿的数量，以及 $P$ ($1 \le P \le 100\,000$)，表示钉子的数量。腿的编号为 $1$ 到 $L$，钉子的编号为 $L + 1$ 到 $L + P$。

接下来的 $L$ 行按顺序描述了各个腿。每行包含一个整数 $v$ ($1 \le v \le 1\,000\,000$)，表示该腿的分值。

接下来的 $P$ 行按顺序描述了各个钉子。每行首先包含两个实数 $\ell$ ($0 < \ell < 1$)，表示圆盘撞击该钉子后向左落下的概率，以及 $r$ ($0 < r < 1$)，表示圆盘向右落下的概率 ($\ell + r \le 1$)，随后是两个整数 $x$ ($1 \le x \le L + P$) 和 $y$ ($1 \le y \le L + P$)，分别表示圆盘向左落下和向右落下后所撞击的钉子或腿的编号。保证 $x$ 和 $y$ 的编号均小于当前钉子的编号。

所有实数均精确到小数点后 3 位。如果没有任何钉子会落入某个钉子或腿，则该钉子或腿被称为投掷点。

保证从任何钉子（无论是否为投掷点）出发，圆盘在到达该钉子后最终卡住的概率最多为 $0.9999$。

输出格式

显示玩家能获得的最高期望分数。答案的绝对误差或相对误差不超过 $10^{-6}$ 即可被接受。

样例

输入格式 1

2 4
344969
539194
0.508 0.318 1 1
0.990 0.009 1 3
0.807 0.041 3 1
0.225 0.617 4 4

输出格式 1

539194.0000000000

输入格式 2

2 8
684841
506003
0.277 0.692 1 1
0.007 0.864 2 1
0.783 0.067 2 1
0.962 0.026 3 1
0.580 0.171 4 4
0.997 0.003 1 6
0.548 0.207 8 7
0.537 0.238 5 7

输出格式 2

684556.2033270609

输入格式 3

3 3
11
12
10
0.500 0.500 1 2
0.800 0.100 1 4
0.600 0.400 4 3

输出格式 3

11.0555555556