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 JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main
{
    public static long MIN(long a,long b)
    {
        if(a<b)
            return a;
        return b;
    }
    public static int MAX(int a,int b)
    {
        if(a>b)
            return a;
        return b;
    }
    public static int BS(int[] x,int val,int n)
    {
       // int n = x.length;
        int l=0,h=n-1,ans=0;
        while(l<=h)
        {
            int mid = (l+h)/2;
            if(x[mid]<=val)
            {
                ans=mid;
                l=mid+1;
            }
            else
                h=mid-1;
        }
        return ans;
    }
    public static boolean check(int[][] ans,int[][] a,int n,int m,BufferedWriter bw) throws IOException
    {
        int[] r = new int[n];
        int[] c = new int[m];
        for(int i=0;i<n;i++)
        {
            int val = 0;
            for(int j=0;j<m;j++)
            {
                val = val|ans[i][j];
            }
            r[i] = val;
        }
        for(int j=0;j<m;j++)
        {
            int val = 0;
            for(int i=0;i<n;i++)
            {
                val = val|ans[i][j];
            }
            c[j] = val;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(a[i][j]!=(r[i]|c[j]))
                    return false;
            }
        }
        return true;
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while(t-->0)
        {
            String[] inp = br.readLine().split(" ");
            int n = Integer.parseInt(inp[0]);
            int m = Integer.parseInt(inp[1]);
            String[] inp3 = br.readLine().split(" ");
            int[] a = new int[n];
            for(int i=0;i<n;i++)
                a[i] = Integer.parseInt(inp3[i]);
            int[] op = new int[m];
            double[] p = new double[m];
            for(int i=0;i<m;i++)
            {
                String[] inp2 = br.readLine().split(" ");
                op[i] = Integer.parseInt(inp2[0]);
                p[i] = Double.parseDouble(inp2[1]);
            }
            int j=n-1;
            for(j=n-1;j>=0;j--)
            {
                if(a[j]!=j+1)
                    break;
            }
            j=j+1;
            Queue<Double> q = new LinkedList<Double>();
            int size=0;
            for(int i=0;i<m;i++)
            {
                if(op[i]>=j)
                {
                    q.add(p[i]);
                    size++;
                }
            }
           // bw.write(j+"\n");
            if(j==0)
                bw.write("1.000000\n");
            else
            {
                while(size>1)
                {
                    double v1 = q.remove();
                    double v2 = q.remove();
                    double ans = v1 + v2 - v1*v2;
                    q.add(ans);
                    size--;
                }
                if(size==0)
                    bw.write("0.000000\n");
                else
                {
                    double ans = q.remove();
                    bw.write(ans+"\n");
                }
            }
        }
        bw.flush();
    }
}

class pair{
    int x,y;
    pair(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}