Today is the planned day tor Thik and Ayvak's wedding. Kark is infatuated with Ayvak. He offers to play a game with Thik. Whosoever wins, will get to marry Ayvak. Ayvak, who values games of chance over all the other things in life, agrees to this.

Kark sets up an N by M grid (N rows, M columns), labelled from left to right and top to bottom consecutively with numbers from 1 to M*N, with 1 at the top left corner and M*N at the bottom right corner. For example, a labelled 3 by 6 grid looks as follows:

Kark has already painted K unit squares of the grid with a heart each. Next, Thik randomly picks a rectangle with sides on the grid lines, and having a positive area, with each valid rectangle having an equal probability of being chosen. Three distinct possibilities for Thik's rectangle in the 3 by 6 grid are shown below: 

The nine different rectangles in a 2 by 2 grid are shown below:


If Thik's rectangle contains at least half of the hearts, Thik gets to marry Ayvak. Otherwise, Kark will marry Ayvak. Kark wants to know whether or not he has an advantage here, so he wants to know the expected value of the number of hearts a randomly chosen rectangle will cover. I'm sure that you have a good heart, so please, cover this job for him. 

-----Input-----
The first line of input contains one integer T, the number of test cases.
For each test case, the first line contains 3 space-separated integers N, M, K, as described in the problem statement. The next line contains K space-separated integers, each a single number from 1 to M*N, representing a square that is painted with a heart. It is guaranteed that all K integers are distinct.

-----Output-----
Output T lines, each containing a single real number, containing the expected number of hearts that a randomly chosen rectangle will contain. The answer will be considered correct if its relative or absolute error does not exceed 10-6.

-----Constraints-----
- 1 ≤ T ≤ 5  
- 1 ≤ N, M ≤ 107  
- 1 ≤ K ≤ 105 
- Each of the K integers representing a heart are between 1 and N*M, inclusive. All K integers are distinct. 

-----Subtasks-----Subtask 1 (15 points) : 

- 1 ≤ N, M ≤ 10
- 1 ≤ K ≤ N * M  
Subtask 2 (85 points) : no additional constraints 


-----Example-----
Input:
1
2 2 2
1 2

Output:
0.8888888888888888

-----Explanation-----
There are a total of 9 possible rectangles Thik could draw, shown in the figure above, and grid squares 1 and 2 are painted with a heart. The top row of possible selections (shown in the figure) contain 1, 0, 1, 2, and 2 hearts (from left to right), and the bottom row of possible selections (in the figure) contain 1, 0, 1, and 0 hearts. Therefore, 3/9 of the time 0 hearts are contained in the rectangle, 4/9 of the times 1 heart is contained in the rectangle, and 2/9 of the time 2 hearts are contained in the rectangle. The expected value is then 0 * 3/9 + 1 * 4/9 + 2 * 2/9 = 8/9.

Difficulty: HARD
Tags: Mathematics

Probability

Starter code:

Solutions:
t = int(input())
while t is not 0:
	(n, m, k) = map(int, input().split())
	prob = 0.0
	p = list(map(int, input().split()))
	kp = n * (n + 1) * m * (m + 1) / 4.0
	for i in range(0, k):
		if p[i] % m != 0:
			c = p[i] % m
			r = p[i] // m + 1
		if p[i] % m == 0:
			c = m
			r = p[i] // m
		prob = prob + c * r * (n - r + 1) * (m - c + 1)
	prob = prob / kp
	print(prob)
	t = t - 1


def get(x, y):
	if x <= 0 or y <= 0:
		return 0
	return x * (x + 1) * y * (y + 1) // 4
t = int(input())
while t > 0:
	t -= 1
	(n, m, k) = map(int, input().split())
	ans = 0
	L = list(map(int, input().split()))
	for v in L:
		v -= 1
		x = v // m + 1
		y = v % m + 1
		tmp = get(x - 1, m) + get(n - x, m) + get(n, y - 1) + get(n, m - y)
		tmp -= get(x - 1, y - 1) + get(x - 1, m - y) + get(n - x, y - 1) + get(n - x, m - y)
		ans += (get(n, m) - tmp) * 1.0 / get(n, m)
	print('%.13f' % ans)


t = int(input())
while t:
	num = input().split()
	n = int(num[0])
	m = int(num[1])
	k = int(num[2])
	inp = input().split()
	ans = 0
	i = 0
	while k:
		z = int(inp[i])
		z = z - 1
		qwe = z // m
		qwe = qwe + 1
		asd = z % m
		asd = asd + 1
		ans += 4.0 * (qwe * (n - qwe + 1)) * (asd * (m - asd + 1)) / (n * (n + 1) * (m * (m + 1)))
		k = k - 1
		i = i + 1
	print('{0:.25f}'.format(ans))
	t = t - 1


for i in range(int(input())):
	(n, m, k) = [int(i) for i in input().split()]
	ans = 0
	l = [int(i) for i in input().split()]
	for i in l:
		r = i // m + 1
		c = i % m
		if c == 0:
			c = m
			r -= 1
		ans += r * (n + 1 - r) * c * (m + 1 - c)
	ans /= (n + 1) * (m + 1) * n * m // 4
	print(ans)


import math
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	total = 0
	for v in a:
		if v % m == 0:
			y = m
		else:
			y = v % m
		x = math.ceil(v / m)
		total += x * (n + 1 - x) * y * (m + 1 - y)
	ans = total / (n * (n + 1) * m * (m + 1) // 4)
	print('%.11f' % ans)


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	arr_k = list(map(int, input().split()))[:k]
	total_p = n * m * (n + 1) * (m + 1) // 4
	total = 0
	for i in range(k):
		a = arr_k[i]
		x = (a - 1) // m + 1
		y = (a - 1) % m + 1
		total += x * y * (n - x + 1) * (m - y + 1)
	res = total / total_p
	print(f'{res:.10f}')


tc = int(input())
while tc > 0:
	(n, m, k) = map(int, input().split())
	hearts = map(int, input().split())
	res = 0
	for i in hearts:
		y = 1 + (i - 1) % m
		x = 1 + (i - 1) // m
		res += x * y * (n - x + 1) * (m - y + 1)
	res *= 4.0
	res /= m * n * (m + 1) * (n + 1)
	print(res)
	tc -= 1


t = int(input())
while t > 0:
	(n, m, k) = map(int, input().split())
	tot = 0
	l = list(map(int, input().split()))
	for i in range(0, k):
		a = l[i]
		x = (a - 1) // m + 1
		y = (a - 1) % m + 1
		tot = tot + x * y * (n - x + 1) * (m - y + 1)
	print('{0:.10f}'.format(tot / (m * (m + 1) * n * (n + 1) // 4)))
	t = t - 1


import math
from decimal import *
t = int(input())
while t:
	k = 0
	t = t - 1
	(n, m, l) = map(int, input().split())
	b = list(map(float, input().split()))
	for i in range(0, l):
		r = b[i] % m
		if b[i] % m == 0:
			s = b[i] / m
			r = m
		else:
			s = int(b[i] / m) + 1
		k = k + r * (m - r + 1) * (s * (n - s + 1))
	print(format(Decimal(k) / Decimal(m * (m + 1) / 2 * (n * (n + 1) / 2)), '.6f'))


t = int(input())
while t > 0:
	t -= 1
	inp = [int(x) for x in input().split()]
	n = inp[0]
	m = inp[1]
	k = inp[2]
	num = 0
	inp = [int(x) for x in input().split()]
	for h in inp:
		h -= 1
		i = h // m
		j = h % m
		num += (i + 1) * (j + 1) * (n - i) * (m - j)
	den = n * m * (n + 1) * (m + 1) // 4
	print(num / den)


t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	su = 0
	sol = 0
	c = map(int, input().split())
	for a in c:
		p = int((a - 1) / m + 1)
		q = (a - 1) % m + 1
		sol = 4 * (p * (n + 1 - p) / (m * (m + 1))) * (q * (m + 1 - q) / (n * (n + 1)))
		su += sol
	print('%.8f' % su)


T = int(input())
for _ in range(T):
	(N, M, K) = [int(s) for s in input().split()]
	s = 0
	eff = N * (N + 1) * M * (M + 1) / 4
	hh = [int(s) for s in input().split()]
	for h in hh:
		h -= 1
		(i, j) = (h // M, h % M)
		s += (M - j) * (N - i) * (i + 1) * (j + 1)
	print(s / eff)


import random
import sys
import os
t = int(input())
while t > 0:
	read = lambda : map(int, input().split())
	(n, m, k) = read()
	ind = list(map(int, input().split()))
	ans = 0
	for d in range(0, k):
		ind[d] = ind[d] - 1
		i = ind[d] // m
		j = ind[d] % m
		ans = ans + (n - i) * (m - j) * (i + 1) * (j + 1)
	print('%.10f' % (4 * ans / (n * m * (n + 1) * (m + 1))))
	t = t - 1


def rect(x, y):
	return x * (x + 1) * y * (y + 1) // 4
T = int(input())
while T != 0:
	T -= 1
	(N, M, K) = (int(n) for n in input().split(' '))
	a = [int(n) - 1 for n in input().split(' ')]
	r = 0
	for n in a:
		i = n // M + 1
		j = n % M + 1
		r += rect(N, M) - rect(i - 1, M) - rect(N, M - j) - rect(N - i, M) - rect(N, j - 1) + rect(i - 1, j - 1) + rect(i - 1, M - j) + rect(N - i, M - j) + rect(N - i, j - 1)
	print('%.8f' % (r / rect(N, M)))


t = int(input())
for z in range(t):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	total = n * (n + 1) / 2 * m * (m + 1) / 2
	for x in l:
		x -= 1
		row = x // m
		col = x % m
		ans += (n - row) * (m - col) * (row + 1) * (col + 1) / total
	print(ans)


z = input()
z = int(z)
for i in range(z):
	ipt = input()
	(n, m, k) = (int(x) for x in ipt.split())
	tot = 0
	add = 0
	ipt = input()
	ark = [int(x) for x in ipt.split()]
	for qr in ark:
		i = (qr - 1) // m + 1
		j = (qr - 1) % m + 1
		add = 4 * (i * (n + 1 - i) / (n * (n + 1))) * (j * (m + 1 - j) / (m * (m + 1)))
		tot += add
	print(tot)


def f(N, M, x, y):
	return (N + 1 - x) * (M + 1 - y) * x * y

def tot(N, M):
	return M * N * (M + 1) * (N + 1) // 4
for T in range(int(input())):
	(N, M, K) = map(int, input().split())
	H = map(int, input().split())
	n = 0
	for h in H:
		(x, y) = (1 + (h - 1) // M, 1 + (h - 1) % M)
		n = n + f(N, M, x, y)
	print(n / tot(N, M))


for t in range(int(input())):
	(n, m, k) = map(int, input().split())
	v = 0
	for x in map(int, input().split()):
		(i, j) = divmod(x - 1, m)
		v += (i + 1) * (j + 1) * (n - i) * (m - j)
	print(4 * v / (n * (n + 1) * m * (m + 1)))


t = int(input())
for i in range(0, t):
	a = input().split()
	N = int(a[0])
	M = int(a[1])
	K = int(a[2])
	total = int(N * (N + 1) * M * (M + 1) / 4)
	A = input().split()
	ans = 0
	for j in range(0, K):
		c = int(A[j]) - 1
		left = c % M + 1
		right = M + 1 - left
		up = int(c / M) + 1
		down = N + 1 - up
		down /= total
		ans += left * right * up * down
	print(ans)


t = int(input())
for curent_test in range(t):
	nmk = input().split(' ')
	n = int(nmk[0])
	m = int(nmk[1])
	k = int(nmk[2])
	all_count = (n * (n - 1) // 2 + n) * (m * (m - 1) // 2 + m)
	sum = 0
	a = input().split(' ')
	for i in range(k):
		val = int(a[i])
		x = (val + m - 1) // m
		y = val % m
		if y == 0:
			y = m
		sum += x * y * ((m - y + 1) * (n - x + 1))
	print(sum / all_count)


def get_xy(k, m):
	x = (k - 1) // m + 1
	y = k % m
	if y == 0:
		y = m
	return (x, y)

def nc2(n):
	return n * (n - 1) // 2
t = int(input())
for test in range(t):
	(n, m, k) = map(int, input().split())
	hearts = list(map(int, input().split()))
	ans = 0
	for i in hearts:
		(x, y) = get_xy(i, m)
		term = x * y * (n - x + 1) * (m - y + 1)
		ans = ans + term
	total_rec = nc2(n + 1) * nc2(m + 1)
	ans = ans / total_rec
	print('%.20f' % ans)


import sys

def readInt():
	return int(input())

def readList():
	return list(map(int, input().strip().split(' ')))

def readStr():
	return input().strip()

def makeMatrix(a, b, value):
	z = [value] * a
	for i in range(a):
		z[i] = [value] * b
	return z
tc = readInt()
while tc:
	tc -= 1
	(y, x, k) = readList()
	total = (x + 1) * x * (y + 1) * y // 4
	s = 0
	a = readList()
	for c in a:
		c -= 1
		xc = c % x
		yc = c // x
		s += (xc + 1) * (yc + 1) * (x - xc) * (y - yc)
	print('%.12f' % (s / total))


T = int(input())
for i in range(0, T):
	(N, M, K) = map(int, input().split())
	Ar = N * (N + 1) / 2
	Ark = M * (M + 1) / 2
	Val = 0
	Sa = Ar * Ark
	aaa = []
	aaa = list(map(int, input().split()))
	for j in range(0, K):
		aa = int(aaa[j])
		X = aa % M
		Y = int(aa / M)
		if aa % M == 0:
			X = 1
		else:
			Y = Y + 1
		X2 = M + 1 - X
		Y2 = N + 1 - Y
		Zita = X2 * X * Y2 * Y
		Val = Val + Zita
	Xa = Val / Sa
	print(Xa)


def count(h, w):
	return h * w * (h + 1) * (w + 1) / 4
t = int(input())
while t > 0:
	t -= 1
	(n, m, k) = map(int, input().split())
	ks = map(int, input().split())
	cnt_all = count(n, m)
	sum = 0
	for a in ks:
		(x, y) = ((a - 1) // m, (a - 1) % m)
		cur = cnt_all
		cur -= count(x, m) + count(n - 1 - x, m) + count(n, y) + count(n, m - 1 - y)
		cur += count(x, y) + count(n - 1 - x, y) + count(x, m - 1 - y) + count(n - 1 - x, m - 1 - y)
		sum += cur
	print(sum / cnt_all)


T = int(input())
while T > 0:
	(N, M, K) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	denom = (N + 1) * N * (M + 1) * M / 4
	sum = 0
	for i in range(K):
		r = (arr[i] - 1) // M + 1
		c = (arr[i] - 1) % M + 1
		b_count = (M + 1) * M * (N - r + 1) * (N - r) / 4
		r_count = (M - c + 1) * (M - c) * (N + 1) * N / 4
		b_right = (M - c + 1) * (M - c) * (N - r + 1) * (N - r) / 4
		t_count = (M + 1) * M * r * (r - 1) / 4
		t_right = (M - c + 1) * (M - c) * r * (r - 1) / 4
		l_count = c * (c - 1) * (N + 1) * N / 4
		t_left = c * (c - 1) * r * (r - 1) / 4
		b_left = c * (c - 1) * (N - r + 1) * (N - r) / 4
		inv = b_count + r_count - b_right + t_count - t_right + l_count - t_left - b_left
		actual = denom - inv
		sum += actual
	print(sum / denom)
	T -= 1


t = int(input())
while t > 0:
	t = t - 1
	(n, m, k) = [int(x) for x in input().split()]
	count = 0
	tot = (n + 1) * n * (m + 1) * m / 4
	i = 0
	a = [int(x) for x in input().split()]
	while i < k:
		if a[i] % m == 0:
			r = int(a[i] / m) - 1
			c = m - 1
		else:
			r = int(a[i] / m)
			c = a[i] % m - 1
		count = count + (r + 1) * (n - r) * (c + 1) * (m - c)
		i = i + 1
	result = float(count) / float(tot)
	print(result)


test = int(input())
for i in range(test):
	testInput = input()
	(n, m, k) = (int(x) for x in testInput.split())
	ans = 0
	val = 0
	div = 0
	row = 0
	col = 0
	xxx = 0
	y = 0
	rohit = 1
	testInput = input()
	array = [int(x) for x in testInput.split()]
	for heart in array:
		row = int((heart - 1) / m + 1)
		col = int((heart - 1) % m + 1)
		val = val + 4 * row * col * (n + 1 - row) * (m + 1 - col)
	div = m * n * (m + 1) * (n + 1)
	ans = val / div
	print(ans)


import math
t = int(input())
while t > 0:
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	k = int(s[2])
	l = [int(x) for x in input().split()]
	sum = 0.0
	a = n * (n + 1) / 2
	b = m * (m + 1) / 2
	ab = a * b
	for x in range(k):
		row = float(math.ceil(float(l[x]) / float(m)))
		col = float(l[x] % m)
		if col == 0:
			col = m
		sum += row * (n - row + 1) * col * (m - col + 1)
	ans = sum / ab
	print(ans)
	t -= 1


t = int(input())

def calc(n, m):
	return int((n * (n - 1) / 2 + n) * (m * (m - 1) / 2 + m))
for r in range(0, t):
	st = input()
	inp = st.split()
	n = int(inp[0])
	m = int(inp[1])
	k = int(inp[2])
	num = 0
	den = calc(n, m)
	st = input()
	inp = st.split()
	for i in range(0, k):
		x = int(inp[i])
		p = int((x - 1) / m)
		p = p + 1
		q = (x - 1) % m
		q = q + 1
		val = p * (n - p + 1) * q * (m - q + 1)
		num = num + val
	print(num / den)


t = int(input())
while t > 0:
	(n, m, k) = [int(x) for x in input().split()]
	total = (n + 1) * n * (m + 1) * m / 4
	ans = 0
	tmp = [int(x) for x in input().split()]
	for i in range(k):
		ni = int(tmp[i] / m)
		mj = int(tmp[i] % m)
		if mj == 0:
			mj = m
		else:
			ni = ni + 1
		ans = ans + ni * (n - ni + 1) * mj * (m - mj + 1)
	print(ans / total)
	t = t - 1


from math import ceil

def convert(x, n, m):
	return (ceil(x / m), x % m if x % m != 0 else m)

def calculate_rectangles(x, y):
	if x <= 0 or y <= 0:
		return 0
	return x * y * (x + 1) * (y + 1) // 4

def count_rectangles(x, y, m, n, total_rectangles):
	return total_rectangles - (calculate_rectangles(x - 1, m) + calculate_rectangles(m - y, n) + calculate_rectangles(m, n - x) + calculate_rectangles(y - 1, n) - calculate_rectangles(x - 1, m - y) - calculate_rectangles(x - 1, y - 1) - calculate_rectangles(n - x, m - y) - calculate_rectangles(n - x, y - 1))
t = int(input())
for _ in range(t):
	(n, m, k) = map(int, input().split())
	temp_arr = list(map(int, input().split()))
	arr = [convert(x, n, m) for x in temp_arr]
	total_rectangles = calculate_rectangles(n, m)
	usable_rectangles = 0
	for i in range(k):
		usable_rectangles += count_rectangles(arr[i][1], arr[i][0], n, m, total_rectangles)
	print(usable_rectangles / total_rectangles)