Рон — счастливый обладатель перестановки $$$a$$$ длины $$$n$$$.
Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ — не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Над перестановкой Рона ставится $$$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}$$$.
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
0.600000 0.720000 0.989500 1.000000
Для первого набора входных данных можно показать, что только от того, выполнится ли сортировка с помощью правила $$$(4, 0.6)$$$, зависит, будет ли итоговая перестановка отсортированной.
