Years after the Ishval Civil War, the Ishvalan refugees have now found a safe place for themselves which is a rectangular piece of land, surrounded by fences.

The land can be thought of as a 2d grid which extends $N$ units vertically and $M$ units horizontally. It is divided into $N$ horizontal rows, which are numbered from $1$ to $N$, as you move from top to bottom and into $M$ vertical columns numbered from $1$ to $M$, from left to right.

There are $X$ rivers flowing in a horizontal direction, each flowing in a different row and covering the entire row. Similarly, there are $Y$ rivers flowing in a vertical direction, each flowing in a different column and covering the entire column.

The people want to build houses of dimensions $S \times S$ on the remaining land.
  
What is the maximum number of houses of the given dimensions that could be built on the remaining land, such that no part of any house is in a river and no two houses overlap?
     
------  Input: ------
The first line contains $T$, the number of test cases. Then the test cases follow. 
- For each test case, the first line contains $N$ and $M$.
- Then the second line contains $X$ , $Y$ and $S$ denoting the number of rivers flowing horizontally, number of rivers flowing vertically and the dimension of the house.
- The next line contains $X$ integers $x_{i}$ denoting the indices of rows in which river flows horizontally.
- The next line contains $Y$ integers $y_{i}$ denoting the indices of columns in which the river flows vertically.

Note: 
$x_{i}$ and $y_{i}$ are given in increasing order.
When $X$ or $Y$ are zero, the line containing $x_{i}$ and $y_{i}$ is skipped respectively in the input (instead of a blank line).

------  Output: ------
For each test case, print a single line containing the maximum number of houses that can be built.

------  Constraints  ------
$1≤ T≤ 100$  
$1 ≤ N,M ≤ 10^{4}$  
$0 ≤ X  ≤ N$  
$0 ≤ Y ≤ M$  
$1 ≤ S ≤ min(N,M)$  
$1 ≤ x_{i} ≤ N$  
$1 ≤ y_{j} ≤ M$  
$x_{i} > x_{i-1}$ for all $2 ≤ i ≤ X$
$y_{i} > y_{i-1}$ for all $2 ≤ i ≤ Y$

----- Sample Input 1 ------ 
2
7 8
1 2 2
5
4 8
6 5
2 0 1
1 4
----- Sample Output 1 ------ 
6
20
----- explanation 1 ------ 
The given figure corresponds to the first test case.

7 8
1 2 2
5
4 8
  
As shown in the figure, the maximum number of houses of dimension $2\times2$ that could be built on the remaining land is $6$.

Difficulty: MEDIUM_HARD
Tags: Geometry

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x > 0:
		xs = list(map(int, input().split()))
		xs = [0] + xs + [n + 1]
	else:
		xs = [0, n + 1]
	if y > 0:
		ys = list(map(int, input().split()))
		ys = [0] + ys + [m + 1]
	else:
		ys = [0, m + 1]
	hors = 0
	verts = 0
	for i in range(1, x + 2):
		space = xs[i] - xs[i - 1]
		if space > 0:
			space -= 1
		verts += space // s
	for j in range(1, y + 2):
		space = ys[j] - ys[j - 1]
		if space > 0:
			space -= 1
		hors += space // s
	print(hors * verts)


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	(X, Y, S) = map(int, input().split())
	XL = list(map(int, input().split())) if X > 0 else []
	YL = list(map(int, input().split())) if Y > 0 else []
	(availX, availY) = (0, 0)
	curr = 0
	for i in XL:
		availX += (i - curr - 1) // S
		curr = i
	availX += (N - curr) // S
	curr = 0
	for i in YL:
		availY += (i - curr - 1) // S
		curr = i
	availY += (M - curr) // S
	print(availX * availY)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x == 0:
		a = [0, n + 1]
	else:
		a = [0] + list(map(int, input().split())) + [n + 1]
	if y == 0:
		b = [0, m + 1]
	else:
		b = [0] + list(map(int, input().split())) + [m + 1]
	a = sum([(a[i + 1] - a[i] - 1) // s for i in range(len(a) - 1)])
	b = sum([(b[i + 1] - b[i] - 1) // s for i in range(len(b) - 1)])
	print(a * b)


T = int(input())
for i in range(T):
	NM = str(input()).split(' ')
	N = int(NM[0])
	M = int(NM[1])
	XYS = str(input()).split(' ')
	X = int(XYS[0])
	Y = int(XYS[1])
	S = int(XYS[2])
	if X:
		A = str(input()).split(' ')
	if Y:
		B = str(input()).split(' ')
	total = 0
	for j in range(X + 1):
		if j == 0:
			y1 = 1
		else:
			y1 = int(A[j - 1]) + 1
		if j == X:
			y2 = N
		else:
			y2 = int(A[j]) - 1
		total = total + (y2 - y1 + 1) // S
	total2 = 0
	if True:
		for k in range(Y + 1):
			if k == 0:
				x1 = 1
			else:
				x1 = int(B[k - 1]) + 1
			if k == Y:
				x2 = M
			else:
				x2 = int(B[k]) - 1
			total2 = total2 + (x2 - x1 + 1) // S
	print(total * total2)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x != 0:
		tempa = list(map(int, input().split()))
	else:
		tempa = []
	if y != 0:
		tempb = list(map(int, input().split()))
	else:
		tempb = []
	tempa = [0] + tempa + [n + 1]
	tempb = [0] + tempb + [m + 1]
	tempa.sort()
	tempb.sort()
	a = 0
	b = 0
	for i in range(1, len(tempa)):
		a += (tempa[i] - tempa[i - 1] - 1) // s
	for i in range(1, len(tempb)):
		b += (tempb[i] - tempb[i - 1] - 1) // s
	ans = a * b
	print(ans)


T = int(input())
for tc in range(T):
	(N, M) = map(int, input().split())
	(H, V, S) = map(int, input().split())
	X = [0]
	Y = [0]
	if H > 0:
		X = X + list(map(int, input().split()))
	if V > 0:
		Y = Y + list(map(int, input().split()))
	X.append(N + 1)
	Y.append(M + 1)
	countx = 0
	county = 0
	for i in range(H + 1):
		a = int((X[i + 1] - X[i] - 1) / S)
		countx += a
	for j in range(V + 1):
		b = int((Y[j + 1] - Y[j] - 1) / S)
		county += b
	print(countx * county)


T = int(input())
for tc in range(T):
	(N, M) = map(int, input().split())
	(X, Y, S) = map(int, input().split())
	x = [0]
	y = [0]
	if X > 0:
		xlist = list(map(int, input().split()))
		for xlist1 in xlist:
			x.append(xlist1)
	x.append(N + 1)
	if Y > 0:
		ylist = list(map(int, input().split()))
		for ylist1 in ylist:
			y.append(ylist1)
	y.append(M + 1)
	counter = 0
	for i in range(len(x) - 1):
		counter += (x[i + 1] - x[i] - 1) // S
	counter1 = 0
	for i in range(len(y) - 1):
		counter1 += (y[i + 1] - y[i] - 1) // S
	print(counter * counter1)


T = int(input())
for tc in range(T):
	(N, M) = map(int, input().split())
	(X, Y, S) = map(int, input().split())
	x = [0]
	y = [0]
	if X > 0:
		xx = list(map(int, input().split()))
		for xx1 in xx:
			x.append(xx1)
	x.append(N + 1)
	if Y > 0:
		yy = list(map(int, input().split()))
		for yy1 in yy:
			y.append(yy1)
	y.append(M + 1)
	x1 = 0
	for i in range(len(x) - 1):
		x1 += (x[i + 1] - x[i] - 1) // S
	y1 = 0
	for i in range(len(y) - 1):
		y1 += (y[i + 1] - y[i] - 1) // S
	print(x1 * y1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x != 0:
		a = list(map(int, input().split()))
	else:
		a = []
	if y != 0:
		b = list(map(int, input().split()))
	else:
		b = []
	a = [0] + a + [n + 1]
	b = [0] + b + [m + 1]
	a.sort()
	b.sort()
	suma = 0
	sumb = 0
	for i in range(1, len(a)):
		suma += (a[i] - a[i - 1] - 1) // s
	for i in range(1, len(b)):
		sumb += (b[i] - b[i - 1] - 1) // s
	ans = suma * sumb
	print(ans)


def func(l, s):
	house = 0
	index = 1
	for i in l:
		house += (i - index) // s
		index = i + 1
	return house
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	xl = []
	yl = []
	if x:
		xl = list(map(int, input().split()))
	if y:
		yl = list(map(int, input().split()))
	xl += [n + 1]
	yl += [m + 1]
	print(func(xl, s) * func(yl, s))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(X, Y, s) = map(int, input().split())
	x = [0]
	y = [0]
	if X > 0:
		x = x + list(map(int, input().split()))
	if Y > 0:
		y = y + list(map(int, input().split()))
	x.append(n + 1)
	y.append(m + 1)
	(l1, l2) = ([], [])
	for j in range(1, X + 2):
		tempx = x[j] - x[j - 1] - 1
		l1.append(tempx // s)
	for j in range(1, Y + 2):
		tempy = y[j] - y[j - 1] - 1
		l2.append(tempy // s)
	print(sum(l1) * sum(l2))


def house(l, s):
	(h, index) = (0, 1)
	for i in l:
		h = h + (i - index) // s
		index = i + 1
	return h
for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	(list1, list2) = ([], [])
	if x:
		list1 = list(map(int, input().split()))
	list1.append(n + 1)
	if y:
		list2 = list(map(int, input().split()))
	list2.append(m + 1)
	print(house(list1, s) * house(list2, s))


t = int(input())
for i in range(t):
	lx = [0]
	ly = [0]
	c = 0
	c1 = 0
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x != 0:
		lx += list(map(int, input().split()))
	lx.append(n + 1)
	if y != 0:
		ly += list(map(int, input().split()))
	ly.append(m + 1)
	for i in range(1, len(lx)):
		if lx[i] - lx[i - 1] - 1 > 0:
			c += (lx[i] - lx[i - 1] - 1) // s
	for i in range(1, len(ly)):
		if ly[i] - ly[i - 1] - 1 > 0:
			c1 += (ly[i] - ly[i - 1] - 1) // s
	print(c * c1)
	lx = []
	ly = []


t = int(input())
for i in range(t):
	h = [0]
	v = [0]
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x != 0:
		h += list(map(int, input().split()))
	h.append(n + 1)
	if y != 0:
		v += list(map(int, input().split()))
	v.append(m + 1)
	p = []
	q = []
	count = 0
	count1 = 0
	for i in range(1, len(h)):
		if h[i] - h[i - 1] - 1 > 0:
			count += (h[i] - h[i - 1] - 1) // s
	for i in range(1, len(v)):
		if v[i] - v[i - 1] - 1 > 0:
			count1 += (v[i] - v[i - 1] - 1) // s
	print(count * count1)
	h = []
	v = []


t = int(input())
for _ in range(t):
	(n, m) = [int(z) for z in input().split()]
	(x, y, s) = [int(z) for z in input().split()]
	ax = [0]
	if x != 0:
		ax += [int(z) for z in input().split()]
	ax.append(n + 1)
	ay = [0]
	if y != 0:
		ay += [int(z) for z in input().split()]
	ay.append(m + 1)
	sx = 0
	sy = 0
	for i in range(x + 1):
		sx += (ax[i + 1] - ax[i] - 1) // s
	for i in range(y + 1):
		sy += (ay[i + 1] - ay[i] - 1) // s
	print(sx * sy)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = list(map(int, input().split()))
	(x, y, s) = list(map(int, input().split()))
	(X, Y) = ([0], [0])
	if x != 0:
		X.extend(map(int, input().split()))
	if y != 0:
		Y.extend(map(int, input().split()))
	X.append(n + 1)
	Y.append(m + 1)
	x_sum = 0
	y_sum = 0
	for i in range(len(X) - 1):
		x_sum += (X[i + 1] - X[i] - 1) // s
	for j in range(len(Y) - 1):
		y_sum += (Y[j + 1] - Y[j] - 1) // s
	print(x_sum * y_sum)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(p, q, r) = map(int, input().split())
	if p != 0:
		h = list(map(int, input().split()))
	else:
		h = []
	if q != 0:
		v = list(map(int, input().split()))
	else:
		v = []
	h.append(a + 1)
	v.append(b + 1)
	a1 = 0
	a2 = 0
	b1 = 1
	c1 = 1
	for i in range(p + 1):
		a1 = a1 + (h[i] - b1) // r
		b1 = h[i] + 1
	for j in range(q + 1):
		a2 = a2 + (v[j] - c1) // r
		c1 = v[j] + 1
	print(a1 * a2)


houseList = []
testCases = int(input())

def compute(river_list, house_size, size):
	space_count = 0
	prev = 0
	for i in river_list:
		space_count += (i - prev - 1) // house_size
		prev = i
	space_count += (size - prev) // house_size
	return space_count
for tests in range(0, testCases):
	houses = 0
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	x1 = [int(x) for x in input().split()] if x > 0 else []
	y1 = [int(x) for x in input().split()] if y > 0 else []
	houseList.append(compute(x1, s, n) * compute(y1, s, m))
for item in houseList:
	print(item)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	xi = []
	yj = []
	if x > 0:
		xi = [int(j) for j in input().split()]
	if y > 0:
		yj = [int(j) for j in input().split()]
	xi.append(n + 1)
	yj.append(m + 1)
	d1 = 0
	d2 = 0
	countx = 0
	county = 0
	for k in xi:
		countx = countx + (k - d1 - 1) // s
		d1 = k
	for k in yj:
		county = county + (k - d2 - 1) // s
		d2 = k
	print(countx * county)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	(X, Y, S) = map(int, input().split(' '))
	hor = list(map(int, input().split(' '))) if X > 0 else []
	ver = list(map(int, input().split(' '))) if Y > 0 else []
	prev_hor = 0
	nbh = 0
	for h in hor:
		diff = h - prev_hor - 1
		nbh += diff // S
		prev_hor = h
	diff = N - prev_hor
	nbh += diff // S
	nbv = 0
	prev_ver = 0
	for v in ver:
		diff = v - prev_ver - 1
		nbv += diff // S
		prev_ver = v
	diff = M - prev_ver
	nbv += diff // S
	print(nbv * nbh)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	riverx = [0]
	rivery = [0]
	if x > 0:
		riverx += list(map(int, input().split()))
	if y > 0:
		rivery += list(map(int, input().split()))
	riverx += [n + 1]
	rivery += [m + 1]
	landx = []
	landy = []
	for i in range(1, x + 2):
		val = riverx[i] - riverx[i - 1] - 1
		if val >= s:
			landx.append(val // s)
	for i in range(1, y + 2):
		val = rivery[i] - rivery[i - 1] - 1
		if val >= s:
			landy.append(val // s)
	print(sum(landx) * sum(landy))


T = int(input())
for k in range(T):
	(N, M) = map(int, input().split())
	(X, Y, s) = map(int, input().split())
	if X > 0:
		X_rivers = list(map(int, input().split()))
	if Y > 0:
		Y_rivers = list(map(int, input().split()))
	X_prev = 0
	B_sum = 0
	for i in range(X):
		B_sum += (X_rivers[i] - X_prev - 1) // s
		X_prev = X_rivers[i]
	B_sum += (N - X_prev) // s
	Y_prev = 0
	A_sum = 0
	for j in range(Y):
		A_sum += (Y_rivers[j] - Y_prev - 1) // s
		Y_prev = Y_rivers[j]
	A_sum += (M - Y_prev) // s
	print(A_sum * B_sum)


def pieces(Max, b, d):
	lista = [0] + b + [Max]
	res = 0
	for i in range(1, len(b) + 2):
		res += (lista[i] - lista[i - 1] - 1) // d
	return res
for _ in range(int(input())):
	(row, col) = map(int, input().split())
	(hor, ver, dim) = map(int, input().split())
	if hor != 0:
		hor_pieces = pieces(row + 1, list(map(int, input().split())), dim)
	else:
		hor_pieces = row // dim
	if ver != 0:
		ver_pieces = pieces(col + 1, list(map(int, input().split())), dim)
	else:
		ver_pieces = col // dim
	print(hor_pieces * ver_pieces)


t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if not x == 0:
		xl = list(map(int, input().split()))
	else:
		xl = []
	if not y == 0:
		yl = list(map(int, input().split()))
	else:
		yl = []
	houses = 0
	X_prev = 0
	w_sum = 0
	for i in range(x):
		w_sum += (xl[i] - X_prev - 1) // s
		X_prev = xl[i]
	w_sum += (n - X_prev) // s
	Y_prev = 0
	h_sum = 0
	for j in range(y):
		h_sum += (yl[j] - Y_prev - 1) // s
		Y_prev = yl[j]
	h_sum += (m - Y_prev) // s
	houses = w_sum * h_sum
	print(houses)


import numpy as np

def create(p, q, t, r):
	q = q.split()
	for k in range(len(q) + 1):
		if k == 0:
			t += [int(q[k]) - 1]
		elif k == len(q):
			t += [p - int(q[k - 1])]
		else:
			t += [int(q[k]) - int(q[k - 1]) - 1]
	t = np.floor_divide(t, r)
	return t
i = int(input(''))
for i in range(i):
	(n, m) = map(int, input('').split())
	(x, y, s) = map(int, input('').split())
	if x != 0:
		xi = input('')
		a = create(n, xi, [], s)
	else:
		a = [n // s]
	if y != 0:
		yi = input('')
		b = create(m, yi, [], s)
	else:
		b = [m // s]
	a = np.array(a)
	b = sum(b)
	a = a * b
	print(sum(a))


MOD = 1000000007
from collections import defaultdict as dd, Counter, deque

def si():
	return input()

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def mi():
	return map(int, input().split())

def out(v):
	print(v)

def spout():
	print(v, end=' ')

def d2b(n):
	return bin(n).replace('0b', '')

def twod(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def vow():
	return ['a', 'e', 'i', 'o', 'u']

def let():
	return [chr(i) for i in range(97, 123)]

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def ispow2(x):
	return x and (not x & x - 1)

def prime_factors(n):
	i = 2
	factors = {}
	max_rep = 0
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors[i] = factors.get(i, 0) + 1
			if max_rep < factors[i]:
				num = i
				max_rep = factors[i]
	if n > 1:
		factors[n] = factors.get(n, 0) + 1
		if max_rep < factors[n]:
			num = n
			max_rep = factors[n]
	return (factors, num, max_rep)
t = ii()
while t:
	t -= 1
	(n, m) = mi()
	(x1, y1, s) = mi()
	h = v = 0
	if x1 > 0:
		x = li()
		h += (x[0] - 1) // s
		for i in range(1, len(x)):
			h += (x[i] - x[i - 1] - 1) // s
		h += (n - x[-1]) // s
	else:
		h += n // s
	if y1 > 0:
		y = li()
		v += (y[0] - 1) // s
		for i in range(1, len(y)):
			v += (y[i] - y[i - 1] - 1) // s
		v += (m - y[-1]) // s
	else:
		v += m // s
	print(h * v)


def land_count(n, m, s, x, y, xI, yI):
	xI.append(n + 1)
	yI.append(m + 1)
	land_X = []
	land_Y = []
	for i in range(1, x + 2):
		val = xI[i] - xI[i - 1] - 1
		if val >= s:
			land_X.append(val // s)
	for i in range(1, y + 2):
		val = yI[i] - yI[i - 1] - 1
		if val >= s:
			land_Y.append(val // s)
	return sum(land_X) * sum(land_Y)
output = []
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	(X, Y, S) = map(int, input().split())
	xi = [0]
	yi = [0]
	if X != 0:
		r = input()
		for i in r.split():
			xi.append(int(i))
	if Y != 0:
		g = input()
		for i in g.split():
			yi.append(int(i))
	output.append(land_count(N, M, S, X, Y, xi, yi))
for i in output:
	print(i)


test_cases = int(input())
for test_case in range(test_cases):
	(N, M) = map(int, input().split())
	(X, Y, S) = map(int, input().split())
	if X != 0:
		Xi = list(map(int, input().split()))
	else:
		Xi = []
	if Y != 0:
		Yi = list(map(int, input().split()))
	else:
		Yi = []
	Xi = [0] + Xi + [N + 1]
	Yi = [0] + Yi + [M + 1]
	n_sum = 0
	m_sum = 0
	for i in range(1, len(Xi)):
		n_sum = n_sum + (Xi[i] - Xi[i - 1] - 1) // S
	for i in range(1, len(Yi)):
		m_sum = m_sum + (Yi[i] - Yi[i - 1] - 1) // S
	print(n_sum * m_sum)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	(X, Y, k) = map(int, input().split())
	if X != 0:
		x = list(map(int, input().split()))
	else:
		x = []
	if Y != 0:
		y = list(map(int, input().split()))
	else:
		y = []
	x.sort()
	y.sort()
	if X == n or Y == m:
		print(0)
		continue
	(x1, y1) = ([], [])
	if len(x) > 0 and x[0] != 1:
		x1.append(x[0] - 1)
	if len(x) > 0 and x[-1] != n:
		x1.append(n - x[-1])
	for j in range(X - 1):
		val = x[j + 1] - x[j] - 1
		if val > 0:
			x1.append(val)
	if len(y) > 0 and y[0] != 1:
		y1.append(y[0] - 1)
	if len(y) > 0 and y[-1] != m:
		y1.append(m - y[-1])
	for j in range(Y - 1):
		val = y[j + 1] - y[j] - 1
		if val > 0:
			y1.append(val)
	c = 0
	if len(x) == 0:
		x1.append(n)
	if len(y) == 0:
		y1.append(m)
	ans1 = 0
	ans2 = 0
	for u in range(len(x1)):
		ans1 += x1[u] // k
	for v in range(len(y1)):
		ans2 += y1[v] // k
	print(ans1 * ans2)


tests = int(input())
for _ in range(tests):
	(n, m) = [int(j) for j in input().split()]
	(x, y, s) = [int(j) for j in input().split()]
	x_rivers = []
	y_rivers = []
	if x != 0:
		x_rivers = [int(j) for j in input().split()]
	if y != 0:
		y_rivers = [int(j) for j in input().split()]
	x_rivers.append(n + 1)
	x_rivers.insert(0, 0)
	y_rivers.append(m + 1)
	y_rivers.insert(0, 0)
	x_lands = [x_rivers[i + 1] - x_rivers[i] - 1 for i in range(x + 1)]
	y_lands = [y_rivers[i + 1] - y_rivers[i] - 1 for i in range(y + 1)]
	x_count = sum([land // s for land in x_lands])
	y_count = sum([land // s for land in y_lands])
	print(x_count * y_count)


t = int(input())
for T in range(t):
	(n, m) = [int(_) for _ in input().split()]
	(x, y, s) = [int(_) for _ in input().split()]
	(lx, ly) = ([], [])
	if x > 0:
		lx = [int(_) for _ in input().split()]
	if y > 0:
		ly = [int(_) for _ in input().split()]
	(dx, dy) = ([], [])
	if m not in ly:
		ly.append(m + 1)
	if n not in lx:
		lx.append(n + 1)
	val = lx[0] - 1
	dx.append(val)
	val = ly[0] - 1
	dy.append(val)
	for i in range(1, len(lx)):
		val = lx[i] - lx[i - 1] - 1
		dx.append(val)
	for i in range(1, len(ly)):
		val = ly[i] - ly[i - 1] - 1
		dy.append(val)
	total_x = []
	total_y = []
	for i in dx:
		total_x.append(i // s)
	for i in dy:
		total_y.append(i // s)
	sum_x = sum(total_x)
	sum_y = sum(total_y)
	print(sum_x * sum_y)


def main_():
	for _ in range(int(input())):
		(Rows, Cols) = map(int, input().split())
		(no_rivers_rows, no_rivers_cols, house_side) = [int(x) for x in input().split()]
		if no_rivers_rows:
			prev = row_gaps_sum = 0
			for x in input().split() + [Rows + 1]:
				x = int(x)
				row_gaps_sum += (x - prev - 1) // house_side
				prev = x
		else:
			row_gaps_sum = Rows // house_side
		if no_rivers_cols:
			prev = col_gaps_sum = 0
			for x in input().split() + [Cols + 1]:
				x = int(x)
				col_gaps_sum += (x - prev - 1) // house_side
				prev = x
		else:
			col_gaps_sum = Cols // house_side
		print(row_gaps_sum * col_gaps_sum)

def main():
	for _ in range(int(input())):
		(Rows, Cols) = map(int, input().split())
		(rivers_in_rows, rivers_in_cols, house_side) = map(int, input().split())
		if rivers_in_rows:
			rivers_rows = [0] + [int(x) for x in input().split()] + [Rows + 1]
			row_gaps = [(rivers_rows[i] - rivers_rows[i - 1] - 1) // house_side for i in range(1, len(rivers_rows)) if rivers_rows[i] - rivers_rows[i - 1] > house_side]
		else:
			row_gaps = [Rows // house_side]
		if rivers_in_cols:
			rivers_cols = [0] + [int(x) for x in input().split()] + [Cols + 1]
			col_gaps = [(rivers_cols[i] - rivers_cols[i - 1] - 1) // house_side for i in range(1, len(rivers_cols)) if rivers_cols[i] - rivers_cols[i - 1] > house_side]
		else:
			col_gaps = [Cols // house_side]
		print(sum(row_gaps) * sum(col_gaps))
main()


t = int(input())
for _ in range(t):
	(m, n) = input().split()
	n = int(n)
	m = int(m)
	(x, y, s) = input().split()
	x = int(x)
	y = int(y)
	s = int(s)
	if x != 0:
		X = list(map(int, input().strip().split()))[:x]
	if y != 0:
		Y = list(map(int, input().strip().split()))[:y]
	x1 = 0
	x2 = 0
	for i in range(x):
		x2 += (X[i] - x1 - 1) // s
		x1 = X[i]
	x2 += (m - x1) // s
	y1 = 0
	y2 = 0
	for i in range(y):
		y2 += (Y[i] - y1 - 1) // s
		y1 = Y[i]
	y2 += (n - y1) // s
	print(x2 * y2)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x:
		xl = list(map(int, input().split()))
	if y:
		yl = list(map(int, input().split()))
	x1 = 0
	x2 = 0
	for i in range(x):
		x2 += (xl[i] - x1 - 1) // s
		x1 = xl[i]
	x2 += (m - x1) // s
	y1 = 0
	y2 = 0
	for i in range(y):
		y2 += (yl[i] - y1 - 1) // s
		y1 = yl[i]
	y2 += (n - y1) // s
	print(x2 * y2)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x:
		hor = list(map(int, input().split()))
	else:
		hor = []
	if y:
		ver = list(map(int, input().split()))
	else:
		ver = []
	hor.append(n + 1)
	ver.append(m + 1)
	a = 0
	b = 0
	h = 1
	v = 1
	for i in range(x + 1):
		a = a + (hor[i] - h) // s
		h = hor[i] + 1
	for j in range(y + 1):
		b = b + (ver[j] - v) // s
		v = ver[j] + 1
	print(a * b)


def func(numlist, size, n):
	h_count = 0
	prev = 0
	for i in numlist:
		h_count += (i - prev - 1) // size
		prev = i
	h_count += (n - prev) // size
	return h_count
for _ in range(int(input())):
	[n, m] = list(map(int, input().split(' ')))
	[h, v, s] = list(map(int, input().split(' ')))
	h_rivers = v_rivers = []
	if h:
		h_rivers = list(map(int, input().split(' ')))
	if v:
		v_rivers = list(map(int, input().split(' ')))
	print(func(h_rivers, s, n) * func(v_rivers, s, m))


t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x:
		x_total = list(map(int, input().split()))
	if y:
		y_total = list(map(int, input().split()))
	x_prev = 0
	x_sum = 0
	for i in range(x):
		x_sum += (x_total[i] - x_prev - 1) // s
		x_prev = x_total[i]
	x_sum += (m - x_prev) // s
	y_prev = 0
	y_sum = 0
	for i in range(y):
		y_sum += (y_total[i] - y_prev - 1) // s
		y_prev = y_total[i]
	y_sum += (n - y_prev) // s
	print(x_sum * y_sum)


for _ in range(int(input())):
	(verticle, horizontal) = map(int, input().split())
	(v_river, h_river, s) = map(int, input().split())
	cx = cy = sx = sy = 0
	if v_river:
		X = [int(i) for i in input().split()] + [verticle + 1]
	else:
		X = [verticle + 1]
	if h_river:
		Y = [int(i) for i in input().split()] + [horizontal + 1]
	else:
		Y = [horizontal + 1]
	for i in range(v_river + 1):
		sx = sx + (X[i] - cx - 1) // s
		cx = X[i]
	for j in range(h_river + 1):
		sy = sy + (Y[j] - cy - 1) // s
		cy = Y[j]
	print(sx * sy)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	(cx, cy, sx, sy) = (0, 0, 0, 0)
	if x:
		X = [int(i) for i in input().split()] + [m + 1]
	else:
		X = [m + 1]
	if y:
		Y = [int(i) for i in input().split()] + [n + 1]
	else:
		Y = [n + 1]
	for i in range(x + 1):
		sx += (X[i] - cx - 1) // s
		cx = X[i]
	for j in range(y + 1):
		sy += (Y[j] - cy - 1) // s
		cy = Y[j]
	print(sx * sy)


try:
	for _ in range(int(input())):
		(rows, colums) = map(int, input().split())
		(x_n, y_n, s) = map(int, input().split())
		if x_n > 0:
			x = list(map(int, input().split()))
		else:
			x = []
		x.append(rows + 1)
		if y_n > 0:
			y = list(map(int, input().split()))
		else:
			y = []
			y.append(0)
		y.append(colums + 1)
		ans = 0
		prev_x = 0
		prev_y = 0
		a = 0
		b = 0
		for i in x:
			if i - prev_x - 1 >= s:
				x_diff = i - prev_x - 1
				a += int(x_diff / s)
			prev_x = i
		for j in y:
			if j - prev_y - 1 >= s:
				y_diff = j - prev_y - 1
				b += int(y_diff / s)
			prev_y = j
		print(a * b)
except:
	pass


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x > 0:
		xRiver = list(map(int, input().split()))
	else:
		xRiver = []
	if y > 0:
		yRiver = list(map(int, input().split()))
	else:
		yRiver = []
	xRiver.append(n + 1)
	yRiver.append(m + 1)
	(r, c, ii, jj) = (0, 0, 1, 1)
	for i in range(len(xRiver)):
		r += (xRiver[i] - ii) // s
		ii = xRiver[i] + 1
	for j in range(len(yRiver)):
		c += (yRiver[j] - jj) // s
		jj = yRiver[j] + 1
	print(r * c)


def take():
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x != 0:
		hor = list(map(int, input().split()))
	else:
		hor = []
	if y != 0:
		vert = list(map(int, input().split()))
	else:
		vert = []
	hor.append(n + 1)
	vert.append(m + 1)
	return (hor, vert, s)
for _ in range(int(input())):
	(hor, vert, s) = take()
	(r, c, ii, jj) = (0, 0, 1, 1)
	for i in range(len(hor)):
		r += (hor[i] - ii) // s
		ii = hor[i] + 1
	for j in range(len(vert)):
		c += (vert[j] - jj) // s
		jj = vert[j] + 1
	print(r * c)


try:
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		(x, y, s) = map(int, input().split())
		(xi, yi) = ([0], [0])
		if x != 0:
			temp_x = [int(x) for x in input().split()][:x]
			xi.extend(temp_x)
		if y != 0:
			temp_y = [int(y) for y in input().split()][:y]
			yi.extend(temp_y)
		ans_x = 0
		ans_y = 0
		for i in range(len(xi) - 1):
			a = xi[i] + 1
			b = xi[i + 1]
			c = abs(b - a)
			temp_x = c // s
			ans_x = ans_x + temp_x
		for j in range(len(yi) - 1):
			a = yi[j] + 1
			b = yi[j + 1]
			c = abs(b - a)
			temp_y = c // s
			ans_y = ans_y + temp_y
		if xi[-1] != n:
			c = n - xi[-1]
			temp_x = c // s
			ans_x = ans_x + temp_x
		if yi[-1] != m:
			c = m - yi[-1]
			temp_y = c // s
			ans_y = ans_y + temp_y
		print(ans_x * ans_y)
except:
	pass


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x != 0:
		x1 = list(map(int, input().split()))
		x1.append(0)
		x1.append(n + 1)
		x1.sort()
	else:
		x1 = [0, n + 1]
	if y != 0:
		y1 = list(map(int, input().split()))
		y1.append(0)
		y1.append(m + 1)
		y1.sort()
	else:
		y1 = [0, m + 1]
	w = 0
	d = 0
	t = 0
	q = 0
	for i in range(1, len(y1)):
		w += (y1[i] - t - 1) // s
		t = y1[i]
	for i in range(1, len(x1)):
		d += (x1[i] - q - 1) // s
		q = x1[i]
	print(w * d)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y, s) = map(int, input().split())
	if x != 0:
		hor = list(map(int, input().split()))
	else:
		hor = []
	if y != 0:
		vert = list(map(int, input().split()))
	else:
		vert = []
	hor.append(n + 1)
	vert.append(m + 1)
	c1 = 0
	c2 = 0
	i1 = 1
	j1 = 1
	for i in range(x + 1):
		c1 += (hor[i] - i1) // s
		i1 = hor[i] + 1
	for j in range(y + 1):
		c2 += (vert[j] - j1) // s
		j1 = vert[j] + 1
	print(c1 * c2)


T = int(input())
from math import floor
for i in range(T):
	(N, M) = map(int, input().split())
	(X, Y, S) = map(int, input().split())
	if X != 0:
		Lx = list(map(int, input().split()))
	else:
		Lx = []
	if Y != 0:
		Ly = list(map(int, input().split()))
	else:
		Ly = []
	Lx.insert(0, 0)
	Lx.append(N + 1)
	Ly.insert(0, 0)
	Ly.append(M + 1)
	(LX, LY) = ([], [])
	for i in range(len(Lx) - 1):
		LX.append(Lx[i + 1] - Lx[i] - 1)
	for i in range(len(Ly) - 1):
		LY.append(Ly[i + 1] - Ly[i] - 1)
	(A, B) = (0, 0)
	for i in LX:
		A += floor(i / S)
	for i in LY:
		B += floor(i / S)
	print(A * B)