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).

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).

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.$

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.$

提交代码