Alex has two arrays defined as $A=[a_0,a_1,...,a_{n-1}]$ and $B=[b_0,b_1,\ldots,b_{m-1}]$. He created an $n\times m$ matrix, $\mbox{M}$, where $M_{i,j}=gcd(a_i,b_j)$ for each $i,j$ in $\mbox{M}$. Recall that ${gcd}(a,b)$ is the greatest common divisor of $a$ and $\boldsymbol{b}$. 

For example, if $A=[2,3]$ and $B=[5,6]$, he builds $M=[[1,2],[1,3]]$ like so:
  $\begin{array}{|l|c|c|}
(i, j) & 0 & 1 \\
 0 & gcd(2,5)=1 &gcd(2,6)=2 \\
 1 & gcd(3,5)=1 &gcd(3,6)=3 
\end{array}$

Alex's friend Kiara loves matrices, so he gives her $\textit{q}$ questions about matrix $\mbox{M}$ where each question is in the form of some submatrix of $\mbox{M}$ with its upper-left corner at $M_{r_1,c_1}$ and its bottom-right corner at $M_{r_2,c_2}$. For each question, find and print the number of distinct integers in the given submatrix on a new line.

Input Format

The first line contains three space-separated integers describing the respective values of $n$ (the size of array $\mbox{A}$), $m$ (the size of array $\mbox{B}$), and $\textit{q}$ (Alex's number of questions). 

The second line contains $n$ space-separated integers describing $a_0,a_1,\ldots,a_{n-1}$. 

The third line contains $m$ space-separated integers describing $b_0,b_1,\ldots,b_{m-1}$. 

Each line $\boldsymbol{i}$ of the $\textit{q}$ subsequent lines contains four space-separated integers describing the respective values of $r_1$, $\mathbf{c}_{1}$, $r_2$, and $c_2$ for the $i^{\mbox{th}}$ question (i.e., defining a submatrix with upper-left corner $(r_1,c_1)$ and bottom-right corner $(r_2,c_2)$).

Constraints

$1\leq n,m\leq10^5$  
$1\leq a_i,b_i\leq10^5$  
$1\leq q\leq10$  
$0\leq r_{1},r_{2}<n$  
$0\leq c_1,c_2\lt m$  

Scoring  

$1\leq n,m\leq1000$ for $25\%$ of score.  
$1\leq n,m\leq10^5$ for $\textbf{100\%}$ of score.  

Output Format

For each of Alex's questions, print the number of distinct integers in the given submatrix on a new line.

Sample Input 0
3 3 3
1 2 3
2 4 6
0 0 1 1
0 0 2 2
1 1 2 2

Sample Output 0
2
3
3

Explanation 0

Given $A=[1,2,3]$ and $B=[2,4,6]$, we build the following $\mbox{M}$:

  $\begin{array}{|l|c|c|c|}
(i, j) & 0 & 1 & 2 \\
 0 & gcd(1,2)=1 &gcd(1,4)=1 &gcd(1,6)=1 \\
 1 & gcd(2,2)=2 &gcd(2,4)=2 &gcd(2,6)=2 \\
 2 & gcd(3,2)=1 &gcd(3,4)=1 &gcd(3,6)=3 
\end{array}$

The diagram below depicts the submatrices for each of the $q=3$ questions in green:

For the submatrix between $M_{0,0}$ and $M_{1,1}$, the set of integers is $\{1,2\}$. The number of distinct integers is $2$.
For the submatrix between $M_{0,0}$ and $M_{2,2}$, the set of integers is $\{1,2,3\}$. The number of distinct integers is $3$.
For the submatrix between $M_{1,1}$ and $M_{2,2}$, the set of integers is $\{1,2,3\}$. The number of distinct integers is $3$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
import math
import os
import random
import re
import sys
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))

def ff(x):
	sd = [i for i in range(1, 1 + math.floor(math.sqrt(x))) if x % i == 0]
	return set(sd + [int(x / d) for d in sd])
md = {}
for x in set(a).union(set(b)):
	md[x] = ff(x)
ar = {}
for (i, v) in enumerate(a):
	for d in md[v]:
		if d in ar:
			ar[d].add(i)
		else:
			ar[d] = set()
			ar[d].add(i)
br = {}
for (j, v) in enumerate(b):
	for d in md[v]:
		if d in br:
			br[d].add(j)
		else:
			br[d] = set()
			br[d].add(j)
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	aps = set()
	for i in range(r1, r2 + 1):
		aps.update(md[a[i]])
	bps = set()
	for j in range(c1, c2 + 1):
		bps.update(md[b[j]])
	ps = aps.intersection(bps)

	def rowFindGCD(i, x):
		for j in br[x]:
			if c1 <= j and j <= c2:
				if math.gcd(a[i], b[j]) == x:
					return j
		return None

	def findGCD(x):
		for i in ar[x]:
			if r1 <= i and i <= r2:
				j = rowFindGCD(i, x)
				if not j is None:
					return (i, j)
		return None
	ret = 0
	for x in ps:
		ret += 1 if findGCD(x) else 0
	print(ret)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
q = int(first_multiple_input[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	second_multiple_input = input().rstrip().split()
	r1 = int(second_multiple_input[0])
	c1 = int(second_multiple_input[1])
	r2 = int(second_multiple_input[2])
	c2 = int(second_multiple_input[3])

	def f(k):
		if gf[k] >= 0:
			return gf[k]
		res = ga[k] * gb[k]
		if res == 0:
			gf[k] = 0
			return 0
		for i in range(k + k, m + 1, k):
			res -= f(i)
		gf[k] = res
		return res
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
q = int(first_multiple_input[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	second_multiple_input = input().rstrip().split()
	r1 = int(second_multiple_input[0])
	c1 = int(second_multiple_input[1])
	r2 = int(second_multiple_input[2])
	c2 = int(second_multiple_input[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
q = int(first_multiple_input[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	second_multiple_input = input().rstrip().split()
	r1 = int(second_multiple_input[0])
	c1 = int(second_multiple_input[1])
	r2 = int(second_multiple_input[2])
	c2 = int(second_multiple_input[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))

def ff(x):
	sd = [i for i in range(1, 1 + math.floor(math.sqrt(x))) if x % i == 0]
	return set(sd + [int(x / d) for d in sd])
md = {}
for x in set(a).union(set(b)):
	md[x] = ff(x)
ar = {}
for (i, v) in enumerate(a):
	for d in md[v]:
		if d in ar:
			ar[d].add(i)
		else:
			ar[d] = set()
			ar[d].add(i)
br = {}
for (j, v) in enumerate(b):
	for d in md[v]:
		if d in br:
			br[d].add(j)
		else:
			br[d] = set()
			br[d].add(j)
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	aps = set()
	for i in range(r1, r2 + 1):
		aps.update(md[a[i]])
	bps = set()
	for j in range(c1, c2 + 1):
		bps.update(md[b[j]])
	ps = aps.intersection(bps)

	def rowFindGCD(i, x):
		for j in br[x]:
			if c1 <= j and j <= c2:
				if math.gcd(a[i], b[j]) == x:
					return j
		return None

	def findGCD(x):
		for i in ar[x]:
			if r1 <= i and i <= r2:
				j = rowFindGCD(i, x)
				if not j is None:
					return (i, j)
		return None
	ret = 0
	for x in ps:
		ret += 1 if findGCD(x) else 0
	print(ret)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
first_multiple_input = input().rstrip().split()
n = int(first_multiple_input[0])
m = int(first_multiple_input[1])
q = int(first_multiple_input[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	second_multiple_input = input().rstrip().split()
	r1 = int(second_multiple_input[0])
	c1 = int(second_multiple_input[1])
	r2 = int(second_multiple_input[2])
	c2 = int(second_multiple_input[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	nm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, nm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)


import math
import os
import random
import re
import sys

def f(k):
	if gf[k] >= 0:
		return gf[k]
	res = ga[k] * gb[k]
	if res == 0:
		gf[k] = 0
		return 0
	for i in range(k + k, m + 1, k):
		res -= f(i)
	gf[k] = res
	return res
nmq = input().split()
n = int(nmq[0])
m = int(nmq[1])
q = int(nmq[2])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
for q_itr in range(q):
	r1C1R2C2 = input().split()
	r1 = int(r1C1R2C2[0])
	c1 = int(r1C1R2C2[1])
	r2 = int(r1C1R2C2[2])
	c2 = int(r1C1R2C2[3])
	sa = set(a[r1:r2 + 1])
	sb = set(b[c1:c2 + 1])
	na = len(a)
	nb = len(b)
	mxa = max(sa)
	mxb = max(sb)
	m = min(mxa, mxb)
	mm = max(mxa, mxb)
	ga = [0] * (m + 1)
	gb = [0] * (m + 1)
	ga[1] = na
	gb[1] = nb
	for i in range(2, m + 1):
		for j in range(i, mm + 1, i):
			if j in sa:
				ga[i] += 1
			if j in sb:
				gb[i] += 1
	gf = [-1] * (m + 1)
	f(1)
	r = sum([x > 0 for x in gf])
	print(r)