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.io.*;
    import java.util.*;
    import java.text.*; 
    import java.lang.*;
    import java.math.*;
public class Main{
/*********************************************Constants***********************************/
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));        
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static long mod=(long)1e9+7;
    static long mod1=998244353;
    static ArrayList<Integer> graph[];
    static int pptr=0,pptrmax=0;
    static String st[];
/*****************************************Solution Begins*********************************/
    static int n,k;
    static int A[];
    static double B[];
    static ArrayList<Double> ls;
    static double dp[][];
    static int len=0;
    static double dfs(int i,int f){
        if(i==len){
            return (double)f;
        }
        if(dp[i][f]>=0)
            return dp[i][f];
        
        double ans=dfs(i+1,f)*(1-ls.get(i));
        ans+=dfs(i+1,1)*ls.get(i);

        return dp[i][f]=ans;
    }
    public static void main(String args[]) throws Exception{
        int tt=pi();
        while(tt-->0){
            n=pi();
            int m=pi();
            int input[]=new int[n+1];
            for(int i=1;i<=n;i++){
                input[i]=pi();
            }
            ls=new ArrayList<>();
            int idx = 0;
            for(int i=n;i>=1;i--){
                if(input[i]!=i){
                    idx = i;
                    break;
                }
            }
            len=0;
            double ans=0;

                for(int i=0;i<m;i++){
                    int a = pi();
                    double x = pd();
                    if(a>=idx){
                        ls.add(x);
                    }
                }
                len = ls.size();

            if(idx == 0){
                ans=1;
                printPrecision(ans);
            }
            else{
                dp=new double[len][2];
                for(double aa[]:dp)
                    Arrays.fill(aa,-2);
                if(ls.size()>0)
                ans=dfs(0,0);
                printPrecision(ans);
            }
        }
/****************************************Solution Ends*************************************/
        clr();
    }
    static void clr(){
        out.flush();
        out.close();
    }
    static void nl() throws Exception{
        pptr=0;
        st=br.readLine().split(" ");
        pptrmax=st.length;
    }
    static void nls() throws Exception{
        pptr=0;
        st=br.readLine().split("");
        pptrmax=st.length;
    }
    static int pi() throws Exception{
        if(pptr==pptrmax)
            nl();
        return Integer.parseInt(st[pptr++]);
    }
    static long pl() throws Exception{
        if(pptr==pptrmax)
            nl();
        return Long.parseLong(st[pptr++]);
    }
    static double pd() throws Exception{
        if(pptr==pptrmax)
            nl();
        return Double.parseDouble(st[pptr++]);
    }
    static String ps() throws Exception{
        if(pptr==pptrmax)
            nl();
        return st[pptr++];
    }
/***************************************Precision Printing*********************************/
    static void printPrecision(double d){
        DecimalFormat ft = new DecimalFormat("0.00000000000"); 
        out.println(ft.format(d));
    }
/**************************************Bit Count*******************************************/
    static int countBit(long mask){
        int ans=0;
        while(mask!=0){
            mask&=(mask-1);
            ans++;
        }
        return ans;
    }
/******************************************Graph******************************************/
    static void Makegraph(int n){
        graph=new ArrayList[n];
        for(int i=0;i<n;i++)
            graph[i]=new ArrayList<>();
    }
    static void addEdge(int a,int b){
        graph[a].add(b);
    }
    // static void addEdge(int a,int b,int c){
    //     graph[a].add(new Pair(b,c));
    // }    
/******************************************Ceil*******************************************/
    static long ceil(long a,long b){
        return (a+b-1)/b;
    }
/*****************************************Debug********************************************/
    public static void debug(Object... o){
        System.err.println(Arrays.deepToString(o));
    }
/************************************Modular Exponentiation********************************/
    static long modulo(long a,long b,long c){
        long x=1,y=a%c;
        while(b > 0){
            if(b%2 == 1)
                x=(x*y)%c;
            y = (y*y)%c;
            b = b>>1;
        }
        return  x%c;
    }
/********************************************GCD*******************************************/
    static long gcd(long x, long y){
        if(x==0)
            return y;
        if(y==0)
            return x;
        long a = (x > y) ? x : y; 
        long b = (x < y) ? x : y;
        long r = b;
        while(a % b != 0){
            r = a % b;
            a = b;
            b = r;
        }
        return r;
    }
}