Ron's permutation is exposed to m examinations of the accompanying sort: (ri, pi). This means that components in range [1,ri] (as such, the prefix of length ri) have to be arranged in ascending request with the probability of pi. All examinations are acted in the same request wherein they are determined in the input data. As an example, how about we take a gander at a
Correct answer will be upvoted else Multiple Downvoted. Computer science.
Ron's permutation is exposed to m examinations of the accompanying sort: (ri, pi). This means that components in range [1,ri] (as such, the prefix of length ri) have to be arranged in ascending request with the probability of pi. All examinations are acted in the same request wherein they are determined in the input data.
As an example, how about we take a gander at a permutation [4,2,1,5,3] and an investigation (3,0.6). After such a test with the probability of 60% the permutation will assume the structure [1,2,4,5,3] and with a 40% probability it will remain unchanged.
You have to decide the probability of the permutation turning out to be totally arranged in ascending request after m trials.
Input
Each test contains at least one experiments. The main line contains the number of experiments t (1≤t≤100).
The primary line of each experiment contains two integers n and m (1≤n,m≤105) — the length of the permutation and the number of trials, individually.
The second line of each experiment contains n integers a1,a2,… ,an (1≤
The accompanying m lines of each experiment each contain an integer ri and a real number pi (1≤ri≤n,0≤pi≤1) — the length of the prefix and its probability being arranged. All probabilities are given with at most 6 decimal places.
It is guaranteed that the amount of n and the amount of m doesn't surpass 105 (∑n,∑m≤105).
Output
For each experiment, print a solitary number — the probability that after all investigations the permutation becomes arranged in ascending request. Your answer will be considered right if its absolute or relative mistake doesn't surpass 10−6.
Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and provided that |a−b|max(1,|b|)≤10−6.
Step by step
Solved in 4 steps with 1 images
