Problem: Ron is a happy owner of a permutation a of length n.

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

<image>

Ron's permutation is subjected to m experiments of the following type: (r_i, p_i). This means that elements in range [1, r_i] (in other words, the prefix of length r_i) have to be sorted in ascending order with the probability of p_i. All experiments are performed in the same order in which they are specified in the input data.

As an example, let's take a look at a permutation [4, 2, 1, 5, 3] and an experiment (3, 0.6). After such an experiment with the probability of 60\% the permutation will assume the form [1, 2, 4, 5, 3] and with a 40\% probability it will remain unchanged.

You have to determine the probability of the permutation becoming completely sorted in ascending order after m experiments.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100).

The first line of each test case contains two integers n and m (1 ≤ n, m ≤ 10^5) — the length of the permutation and the number of experiments, respectively.

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — contents of the permutation.

The following m lines of each test case each contain an integer r_i and a real number p_i (1 ≤ r_i ≤ n, 0 ≤ p_i ≤ 1) — the length of the prefix and the probability of it being sorted. All probabilities are given with at most 6 decimal places.

It is guaranteed that the sum of n and the sum of m does not exceed 10^5 (∑ n, ∑ m ≤ 10^5).

Output

For each test case, print a single number — the probability that after all experiments the permutation becomes sorted in ascending order. Your answer will be considered correct if its absolute or relative error does not exceed 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Example

Input


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


Output


0.600000
0.720000
0.989500
1.000000

Note

Explanation of the first test case: It can be demonstrated that whether the final permutation is sorted or not depends solely on sorting being performed in the (4, 0.6) experiment.

Solution (in PYTHON3):

Solution:
"""
    Don't see the standings during the contest!!! you will lose motivation.

"""
# ---------------------------------------------------Import Libraries---------------------------------------------------
import sys
import time
import os
from math import sqrt, log, log2, ceil, log10, gcd, floor, pow, sin, cos, tan, pi, inf, factorial
from copy import copy, deepcopy
from sys import exit, stdin, stdout
from collections import Counter, defaultdict, deque
from itertools import permutations
import heapq
from bisect import bisect_left as bl
# If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is r

# ---------------------------------------------------Global Variables---------------------------------------------------
# sys.setrecursionlimit(100000000)
mod = 1000000007
# ---------------------------------------------------Helper Functions---------------------------------------------------
iinp = lambda: int(sys.stdin.readline())
inp = lambda: sys.stdin.readline().strip()
strl = lambda: list(inp().strip().split(" "))
intl = lambda: list(map(int, inp().split(" ")))
mint = lambda: map(int, inp().split())
fint = lambda: map(float, inp().split())
flol = lambda: list(map(float, inp().split(" ")))
flush = lambda: stdout.flush()


def permute(nums):
    def fun(arr, nums, cur, v):
        if len(cur) == len(nums):
            arr.append(cur.copy())
        i = 0
        while i < len(nums):
            if v[i]:
                i += 1
                continue
            else:
                cur.append(nums[i])
                v[i] = 1
                fun(arr, nums, cur, v)
                cur.pop()
                v[i] = 0
                i += 1
            # while i<len(nums) and nums[i]==nums[i-1]:i+=1    # Uncomment for unique permutations
        return arr

    res = []
    nums.sort()
    v = [0] * len(nums)
    return fun(res, nums, [], v)


def subsets(res, index, arr, cur):
    res.append(cur.copy())
    for i in range(index, len(arr)):
        cur.append(arr[i])
        subsets(res, i + 1, arr, cur)
        cur.pop()
    return res


def sieve(N):
    root = int(sqrt(N))
    primes = [1] * (N + 1)
    primes[0], primes[1] = 0, 0
    for i in range(2, root + 1):
        if primes[i]:
            for j in range(i * i, N + 1, i):
                primes[j] = 0
    return primes


def bs(arr, l, r, x):
    if x < arr[0] or x > arr[len(arr) - 1]:
        return -1
    while l <= r:
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            l = mid + 1
        else:
            r = mid - 1
    return -1


def isPrime(n):
    if n <= 1: return False
    if n <= 3: return True
    if n % 2 == 0 or n % 3 == 0: return False
    p = int(sqrt(n))
    for i in range(5, p + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True


# -------------------------------------------------------Functions------------------------------------------------------

def solve():
    n,m=mint()
    # print(n,m)
    arr=intl()
    i=n-1
    ans=1
    flag=0
    while i>=0:
        if arr[i]!=i+1:
            break
        i-=1
    # print(i)
    if i==-1:
        flag=1
    for j in range(m):
        r,p=fint()
        if r-1>=i:
            ans*=(1-p)
    print(1-ans) if not flag else print(1)




# -------------------------------------------------------Main Code------------------------------------------------------
start_time = time.time()
for _ in range(iinp()):
    solve()
    # print("--- %s seconds ---" % (time.time() - start_time))