Segment

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

BrotherK has a white wood stick of length $N$ which consists of $N$ linked sticks of length 1. We number these $N$ sticks from number 1 to $N$, from left to right.

Today, BrotherK is bored, so he wants to cut his wood stick.

First, he chooses two arrays $A,~B$: each one has $M$ elements : $A_1$ ~ $A_M$, $B_1$ ~ $B_M$. Next he chooses a permution of 1 ~ $M$ randomly(All possible permutations have equal probability). Assume the permutaion is $P_1$ ~ $P_M$. If there exists an $I$ in $[1,~M]$ such that $A_I~\gt~B_{P_I}$, BrotherK will choose another permutation randomly, until there is not any $I$ such that $A_I~\gt~B_{P_I}$.

For each $I$ in $[1,~M]$, he will paint black on sticks between the interval $[A_I,~B_{P_I}]$.

Finally, BrotherK cuts all black sticks. There may remain some white sticks.

Now, BrotherK wants to know the expected length of the longest white stick.(If after painting, all sticks are black, then we consider the length as 0).

Input

The first line contains a single integer $T$, indicating the number of test cases.

Each test case begins with two integers $N,~M$, indicating the length of the original stick, and the number of the elements in array $A,~B$.

The second line contains $M$ numbers, from $A_1$ to $A_M$.

The third line contains $M$ numbers, from $B_1$ to $B_M$.

$T$ is about 20.

$1~\le~N~\le~1000000$.

$1~\le~M~\le~50$.

$1~\le~A_i, B_i~\le~N.$

Output

For each test, print one lines.

If BrotherK can't find a valid permutation, print "Stupid BrotherK!" (without quotation marks).

Otherwise, print the expected length. (correct to six decimal places)

Sample Input

2 5 2 1 3 2 4 5 1 1 5

Sample Output

1.000000 0.000000
Hint
In the first case, BrotherK will stop with permutation {1, 2}.

Hint

hujie

Source

赛码"BestCoder"杯中国大学生程序设计冠军赛

提交代码