Sereja and Two Arrays

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja and Arrays
Sereja have an array that consist of n integers a[1], a[2], ..., a[n]. Also Sereja have an array that consist of m integers b[1], b[2], ..., b[m]. Sereja make next operations:
 random_shuffle(b) — shuffle elements of b
 random_merge(a, b) — merge array a and b to array a. From all possible merges Sereja chooses a random one. For better understanding you can imagine, that merged array is sequence q of n+m elements, each element if either zero or one. It contains exactly n zeroes and m ones. Then zeroes are replaced with elements of a, and ones are replaced with elements of b (without changing their relative order inside initial sequences).
Now Sereja want to know expected number of inversions in array a after described operations. Inversion is a pair (i, j) (1 ≤ i < j ≤ n + m) such that a[i] > a[j].
Input
First line contain number T — number of testcases. T tests follow. First line of each testcase contain two integers n and m. Next line contain n integers a[1], a[2], ..., a[n]. Next line contain m integers b[1], b[2], ..., b[m].
Output
For each testcase print expected number of inversions.
Constraints
 1 ≤ T ≤ 7
 1 ≤ n,m ≤ 10^5
 1 ≤ a[i], b[i] ≤ 10^5
Example
Input: 2 5 3 1 5 4 3 2 2 6 3 10 9 10 3 6 4 8 4 1 9 7 2 9 8 3 3 10 8 2 9 2 Output: 13.833333333 87.818181818
Note
Test #01 (25 points): n,m ≤ 10
Test #2 (25 points): n,m ≤ 1000
Test #34 (50 points): n,m ≤ 100000
Author:  sereja 
Editorial  http://discuss.codechef.com/problems/LFEB14A 
Tags  fenwick, inversions, ltime09, maths, medium, sereja 
Date Added:  9022014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 