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 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 #0-1 (25 points): n,m ≤ 10  
Test #2 (25 points): n,m ≤ 1000  
Test #3-4 (50 points): n,m ≤ 100000

Source: codechef | Difficulty: VERY_HARD
Tags: Probability

Range queries

Segment trees revisited

Mathematics

Data structures


Solutions:
lim = 10 ** 5

def update(bit, index, val):
	index += 1
	while index < len(bit):
		bit[index] += val
		index += index & -index

def get(bit, index):
	index += 1
	s = 0
	while index:
		s += bit[index]
		index -= index & -index
	return s
z = int(input())
from decimal import getcontext, Decimal
getcontext().prec = 30
while z:
	z -= 1
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	bit1 = [0] * (lim + 2)
	x = xy = y = 0
	bit2 = [0] * (lim + 2)
	for i in a[::-1]:
		x += get(bit1, i - 1)
		update(bit1, i, 1)
	for (i, j) in enumerate(b):
		y += i - get(bit2, j) + get(bit2, j - 1)
		update(bit2, j, 1)
	for (i, j) in enumerate(a):
		xy += (i + 1) * (m - get(bit2, j))
		xy += (n - i) * get(bit2, j - 1)
	ans = Decimal(x) + Decimal(y) / Decimal(2) + Decimal(xy) / Decimal(n + 1)
	print(ans)