C. Случайные события
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рон — счастливый обладатель перестановки $$$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)$$$, зависит, будет ли итоговая перестановка отсортированной.