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:
//package div3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class board
{
    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;
        }
    }



    /*
            BABB
            BAABBB

            AAAAABBB

    *  AABBBABBBB
    *
    * AABABB
    *
    * */
    static void helper(String s,int[] a,int n,String match,int inc){
        int i=0;
        while(i<n){
            int j = i;
            if(j+inc-1<=n-1 && s.substring(j,j+inc).equals(match)){
                a[j] = 1;
                i = j+inc-1;
            }
            else{
                i++;
            }
        }

    }
    static final int MAXN = 100000;
    static final int level = 18;



    //static LinkedList<Integer>[] adj;


    static int[] diameter;
    static int bfs(int init, int n)
    {
        // Initializing queue
        Queue<Integer> q = new LinkedList<>();
        q.add(init);

        int visited[] = new int[n + 1];
        for (int i = 0; i <= n; i++)
        {
            visited[i] = 0;
            diameter[i] = 0;
        }

        // Pushing each node in queue
        q.add(init);

        // Mark the traversed node visited
        visited[init] = 1;
        while (q.size() > 0)
        {
            int u = q.peek();
            q.remove();
            for (int nei : adj[u])
            {
                if (visited[nei] == 0)
                {
                    visited[nei] = 1;

                    // Considering weight of edges equal to 1
                    diameter[nei] += diameter[u] + 1;
                    q.add(nei);
                }
            }
        }
        int in = 0;
        for(int i = 0; i <= n; i++)
        {
            if(diameter[i] > diameter[in])
                in = i;
        }

        // return index of max value in diameter
        return in;
    }
    private static int dfs(int node,LinkedList<Integer>[] adj,int parent,int[] sub){

        int size = 1;
        for(int nei : adj[node]){
            if(nei != parent){
                size += dfs(nei,adj,node,sub);
            }
        }
        sub[node] = size;
        return size;
    }
    private static int dfs2(int node,LinkedList<Integer>[] adj,int parent,int[] sub){
        int res = sub[node];
        int maxScore = 0;
        for(int nei : adj[node]){
            if(nei != parent) {
                maxScore = Math.max(maxScore,dfs2(nei,adj,node,sub));
            }
        }
        return res + maxScore;
    }
    public static void primeFactors(long n)
    {
        // Print the number of 2s that divide n
        while (n%2==0)
        {
            primesMap.put((long)2,primesMap.getOrDefault((long)2,0)+1);
            n /= 2;
        }

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

        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            primesMap.put(n,primesMap.getOrDefault(n,0)+1);
    }
    static TreeMap<Long,Integer> primesMap;
    /*
    *
    *  2 2 2 1 3 4 5
    *  1 2 2 2 3 3 2 1 2 2 2
    * */
    static LinkedList<Integer>[] adj;
    static int[] color;
    static int[] parent;
    static int cycle_end;
    static int cycle_start;
    static int n;
    static HashSet<Integer> cycle;
    static boolean dfs(int v, int par) { // passing vertex and its parent vertex
        color[v] = 1;
        for (int u : adj[v]) {
            if(u == par) continue; // skipping edge to parent vertex
            if (color[u] == 0) {
                parent[u] = v;
                if (dfs(u, parent[u]))
                    return true;
            } else if (color[u] == 1) {
                cycle_end = v;
                cycle_start = u;
                return true;
            }
        }
        color[v] = 2;
        return false;
    }
    static void find_cycle() {
        Arrays.fill(color,0);
        Arrays.fill(parent,-1);
        cycle_start = -1;

        for (int v = 0; v <= n; v++) {
            if (color[v] == 0 && dfs(v, parent[v]))
                break;
        }



        cycle.add(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.add(v);
        cycle.add(cycle_start);
        //System.out.println(cycle);

    }
    static int dfs2(int node,int par){
        int s = 1;
        for(int nei: adj[node]){
            if(!cycle.contains(nei) && nei != par){
                s += dfs2(nei,node);
            }
        }
        return s;
    }
    static long nC2(int n){
        return ((long)(n)*(long)(n-1))/2;
    }
    static int[][] d = new int[][]{{0,0},{1,0},{0,1},{1,1}};
    static Long[][] dp;
    static long go(int start,int i,long[] f,long[] cost,long fuel,int started){
        int s = start,ss = started;
        //System.out.println(fuel);
        if(start != -1 && fuel<0) return Integer.MAX_VALUE;
        if(i >= f.length){
            //System.out.println(start+" "+fuel);
            if(start == -1 ) return Integer.MAX_VALUE;
            if(fuel+1 >= (f.length-(i-1-start))) return 0;
            else return Integer.MAX_VALUE;
        }
        if(start != -1 && dp[i][start] != null) return dp[i][start];
        long totCost = Long.MAX_VALUE;
        if(start == -1) {
            //fuel = 0;
            start = i;
            started = 1;
        }
        fuel += f[i];
        //System.out.println(fuel);
        totCost = Math.min(totCost,cost[i]*f[i] + go(start,i+1,f,cost,fuel-1,started));
        fuel -= f[i];

        totCost = Math.min(totCost,go(s,i+1,f,cost,(s == -1)?0:fuel-1,ss));


        if(s == -1)return totCost;
        return dp[i][s] = totCost;

    }
//    static int go(int index,int x,int k){
//        if(index-k > x || index+)
//        if(index == x) return 0;
//        int op1 = 1+go(index+k,x,k+1);
//        int op2 = 1+go(index-1,x,k+1);
//        return Math.min(op1,op2);
//    }

    public static  int quadraticEquationRoot1(double a, double b, double c){
        double root1, root2; //This is now a double, too.
        root1 = (-b + Math.sqrt(Math.pow(b, 2) - 4*a*c)) / (2*a);
        root2 = (-b - Math.sqrt(Math.pow(b, 2) - 4*a*c)) / (2*a);
        int min = Integer.MAX_VALUE;
        if(root1 >= 0 && root1<min && Math.ceil(root1) == root1)min = (int)root1;
        if(root2 >= 0 && (int)root2<min && Math.ceil(root2) == root2)min = (int)root2;
        if(min == Integer.MAX_VALUE) return -1;
        return min;
}
    static void print(int[] days){
        for(int i:days)out.print(i+" ");
        out.println();
    }
    static void print(int[][] a){
        for(int[] f:a){
            out.println();
            for(int i:f){
                out.print(i+" ");
            }
        }
        out.println();
    }
    static PrintWriter out;
    static int[] pre;

    static int XOR(int l,int r){
        if(l == 0){
            return pre[r];
        }
        else{
            return pre[r]^pre[l-1];
        }
    }
    static int m = (int)(1e9+7);
    static long prod(long a,long b){
        return (a%m * b%m)%m;
    }
    static List<Long> dfs(int node,LinkedList<Integer>[] adj,int[] a){
        List<Long> ret = new ArrayList<>();
        for(int nei:adj[node]){
            List<Long> get = dfs(nei,adj,a);
            for(long e:get) ret.add(e);
        }
        if(ret.isEmpty()){
            ret.add((long)a[node]);
            return ret;
        }
        Collections.sort(ret);
        long max = ret.get(ret.size()-1);
        int needed = a[node];
        for(int i=0;i<ret.size();i++){
            long diff = max-ret.get(i);
            if(needed > diff){
                ret.set(i,ret.get(i)+diff);
                needed -= diff;
            }
            else{
                ret.set(i,ret.get(i)+needed);
                needed = 0;
                break;
            }
        }
        if(needed > 0){
            for(int i=0;i<ret.size();i++){
                ret.set(i,ret.get(i)+needed/ret.size());
            }
            if(needed%ret.size() != 0){
                ret.set(0,ret.get(0)+needed%ret.size());
            }

        }
        return ret;

    }
    static int manhattan(int[] a,int[] b){
        return Math.abs(a[0]-b[0])+Math.abs(a[1]-b[1]);
    }
    static boolean satisfy(int[] head,int r,int c,int[][] pre,int[][] suf){
        int diff = r-head[1];
        int want = (1+(diff)*(2))/2 + 1;
        if(pre[r][c] >= want && suf[r][c] >= want) return false;
        return true;
    }
    public static void main(String[] args)
    {
        FastReader sc=new FastReader();
        out = new PrintWriter(System.out);
        int t = sc.nextInt();

        while(t-->0) {

            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = sc.nextInt();
            double[][] exp = new double[m][2];
            for(int i=0;i<m;i++){
                exp[i][0] = sc.nextDouble();
                exp[i][1] = sc.nextDouble();
            }
            double[][] dp = new double[m][2];
            int displacement = 0;
            for(int i=0;i<n;i++){
                if(a[i] != i+1)
                    displacement = Math.max(displacement,i+1);
                //displacement = Math.max(displacement,Math.abs(i+1-a[i]));
            }
            //out.println("displacement"+" "+displacement);
            if(displacement == 0){
                out.println(1.0); continue;

            }
            if(exp[m-1][0] >= displacement){
                dp[m-1][0] = exp[m-1][1];
            }

            for(int i=m-2;i>=0;i--){
                double r = exp[i][0];
                double p = exp[i][1];
                if(r >= displacement){
                    dp[i][0] = p;
                    dp[i][1] = (1.0-p)*(dp[i+1][0]+dp[i+1][1]);
                }
                else{
                    dp[i][0] = p*(dp[i+1][0]+dp[i+1][1]);
                    dp[i][1] = (1.0-p)*(dp[i+1][0]+dp[i+1][1]);
                }
            }
            out.println(dp[0][0]+dp[0][1]);

        }




        out.close();
    }


}