Ron 很高兴拥有长度为 $$$n$$$ 的排列 $$$a$$$。
长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
Ron 的排列受到以下类型的 $$$m$$$ 实验的影响:($$$r_i$$$, $$$p_i$$$)。这意味着$$$[1, r_i]$$$范围内的元素(换句话说,长度为$$$r_i$$$的前缀)必须以$$$p_i$$$的概率按升序排序。所有实验均按照输入数据中指定的顺序进行。
作为示例,让我们看一下排列 $$$[4, 2, 1, 5, 3]$$$ 和实验 ($$$3, 0.6$$$)。经过 $$$60\%$$$ 概率的实验后,排列将采用 $$$[1, 2, 4, 5, 3]$$$ 的形式,并且以 $$$40\%$$$ 概率保持不变。
您必须在 $$$m$$$ 实验之后确定排列完全按升序排序的概率。
输入
每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(1 \le n, m \le 10^5)$$$ - 分别表示排列的长度和实验的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le n)$$$ — 排列的内容。
每个测试用例的以下 $$$m$$$ 行均包含一个整数 $$$r_i$$$ 和一个实数 $$$p_i$$$ $$$(1 \le r_i \le n, 0 \le p_i \le 1)$$$ - 前缀的长度及其被排序的概率。所有概率最多保留 $$$6$$$ 小数位。
保证$$$n$$$和$$$m$$$的总和不超过$$$10^5$$$ ($$$\sum n, \sum m \le 10^5$$$)。
输出
对于每个测试用例,打印一个数字 - 在所有实验之后排列按升序排序的概率。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
4 4 3 4 3 2 1 1 0.3 3 1 4 0.6 5 3 4 2 1 3 5 3 0.8 4 0.6 5 0.3 6 5 1 3 2 4 5 6 4 0.9 5 0.3 2 0.4 6 0.7 3 0.5 4 2 1 2 3 4 2 0.5 4 0.1
输出 #1
0.600000 0.720000 0.989500 1.000000
注意
第一个测试用例的说明:可以证明最终排列是否排序仅取决于 $$$(4, 0.6)$$$ 实验中执行的排序。