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.*;

public class C {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    static FastReader s = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    private static int[] rai(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
        }
        return arr;
    }

    private static int[][] rai(int n, int m) {
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.nextInt();
            }
        }
        return arr;
    }

    private static long[] ral(int n) {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextLong();
        }
        return arr;
    }

    private static long[][] ral(int n, int m) {
        long[][] arr = new long[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.nextLong();
            }
        }
        return arr;
    }

    private static int ri() {
        return s.nextInt();
    }

    private static long rl() {
        return s.nextLong();
    }

    private static String rs() {
        return s.next();
    }

    static int gcd(int a,int b)
    {
        if(b==0)
        {
            return a;
        }
        return gcd(b,a%b);
    }

    static boolean isPrime(int n) {
        //check if n is a multiple of 2
        if (n % 2 == 0) return false;
        //if not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
    static int MOD=1000000007;

    static long mpow(long base,long pow)
    {
        long res=1;
        while(pow>0)
        {
            if(pow%2==1)
            {
                res=(res*base)%MOD;
            }
            pow>>=1;
            base=(base*base)%MOD;
        }
        return res;
    }


    public static HashSet<Long> primeFactors(long n)
    {
        // Print the number of 2s that divide n
        HashMap<Long,Integer> map=new HashMap<>();

        while (n % 2 == 0) {
            map.put(2L,map.getOrDefault(2L,0)+1);
            n /= 2;
        }

        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (long i = 3; i <= Math.sqrt(n); i += 2) {
            // While i divides n, print i and divide n
            while (n % i == 0) {
                map.put(i,map.getOrDefault(i,0)+1);
                n /= i;
            }
        }

        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            map.put(n,map.getOrDefault(n,0)+1);

        HashSet<Long> set=new HashSet<>(map.keySet());
        return set;
    }


    static int calcCost(char[] arr,int rem,int x,int y,int n,int p,int k)
    {
        int cost=rem*y;
        boolean flag=false;
        int ind=rem;
        ind+=p;
        while(ind<=n)
        {
            if(arr[ind]!='1')
            {
                cost+=x;
            }
            ind+=k;
        }
        return cost;
    }

    static String create()
    {
        StringBuilder str=new StringBuilder();
        Random r=new Random();
        for(int i=0;i<2000;i++)
        {

            int val=r.nextInt(10);
            str.append(val);
        }
        return str.toString();
    }



    public static void main(String[] args) {
        StringBuilder ans = new StringBuilder();

        int t = ri();
//        int t = 1;
        while (t-- > 0)
        {
            int n=ri();
            int m=ri();
            int[] arr=rai(n);
            List<Pair> list=new ArrayList<>();
            for(int i=0;i<m;i++)
            {
                list.add(new Pair(ri(),s.nextDouble()));
            }
            list.sort(new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.ind-o2.ind;
                }
            });
            int ind=-1;
            for(int i=n-1;i>=0;i--)
            {
                if(i==arr[i]-1)
                {
                    continue;
                }
                ind=i+1;
                break;
            }
            if(ind==-1)
            {
                ans.append("1\n");
                continue;
            }
            double prod=1D;
            if(list.get(list.size()-1).ind<ind)
            {
                ans.append("0\n");
                continue;
            }

            double res=0;
            for(int i=list.size()-1;i>=0;i--)
            {
                int index=list.get(i).ind;
                double val=list.get(i).val;
                if(index<ind)
                {
                    break;
                }

                res+=prod*val;
                prod*=(1D-val);
            }
            ans.append(res).append("\n");




        }
        out.print(ans.toString());
        out.flush();

    }
    static class Pair
    {
        int ind;
        double val;

        public Pair(int ind, double val) {
            this.ind = ind;
            this.val = val;
        }
    }



}