You are given a tube which is reflective inside represented as two non-coinciding, but parallel to $Ox$ lines. Each line has some special integer points — positions of sensors on sides of the tube.

You are going to emit a laser ray in the tube. To do so, you have to choose two integer points $A$ and $B$ on the first and the second line respectively (coordinates can be negative): the point $A$ is responsible for the position of the laser, and the point $B$ — for the direction of the laser ray. The laser ray is a ray starting at $A$ and directed at $B$ which will reflect from the sides of the tube (it doesn't matter if there are any sensors at a reflection point or not). A sensor will only register the ray if the ray hits exactly at the position of the sensor. [Image] Examples of laser rays. Note that image contains two examples. The $3$ sensors (denoted by black bold points on the tube sides) will register the blue ray but only $2$ will register the red. 

Calculate the maximum number of sensors which can register your ray if you choose points $A$ and $B$ on the first and the second lines respectively.


-----Input-----

The first line contains two integers $n$ and $y_1$ ($1 \le n \le 10^5$, $0 \le y_1 \le 10^9$) — number of sensors on the first line and its $y$ coordinate.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — $x$ coordinates of the sensors on the first line in the ascending order.

The third line contains two integers $m$ and $y_2$ ($1 \le m \le 10^5$, $y_1 < y_2 \le 10^9$) — number of sensors on the second line and its $y$ coordinate. 

The fourth line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \le b_i \le 10^9$) — $x$ coordinates of the sensors on the second line in the ascending order.


-----Output-----

Print the only integer — the maximum number of sensors which can register the ray.


-----Example-----
Input
3 1
1 5 6
1 3
3

Output
3



-----Note-----

One of the solutions illustrated on the image by pair $A_2$ and $B_2$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Data structures

Mathematics

Divide and conquer


Solutions:
(n, y1) = map(int, input().split())
a = list(map(int, input().split()))
(m, y2) = map(int, input().split())
b = list(map(int, input().split()))
ans = 2
for i in range(30):
	step = 2 << i
	half = step >> 1
	counts = dict()
	for x in a:
		rem = x % step
		count = counts.get(rem, 0)
		counts[rem] = count + 1
	for x in b:
		rem = (x + half) % step
		count = counts.get(rem, 0)
		counts[rem] = count + 1
	res = max(counts.values())
	ans = max(ans, res)
print(ans)


(n, y1) = map(int, input().split())
a = list(map(int, input().split()))
(m, y2) = map(int, input().split())
b = list(map(int, input().split()))
(a_st, b_st) = (dict(), dict())
osn = 2 ** 30
(k_a, k_b) = (set(), set())
for el in a:
	try:
		a_st[el % osn] += 1
	except KeyError:
		a_st[el % osn] = 1
	finally:
		k_a.add(el % osn)
for el in b:
	try:
		b_st[el % osn] += 1
	except KeyError:
		b_st[el % osn] = 1
	finally:
		k_b.add(el % osn)
ans = 2
for i in range(1, 31)[::-1]:
	temp = 0
	for el in k_a:
		try:
			temp = max(temp, a_st[el] + b_st[(el + osn // 2) % osn])
		except KeyError:
			temp = max(temp, a_st[el])
	for el in k_b:
		try:
			temp = max(temp, b_st[el] + a_st[(el + osn // 2) % osn])
		except KeyError:
			temp = max(temp, b_st[el])
	ans = max(ans, temp)
	osn //= 2
	k_ = set()
	k_add = set()
	for el in k_a:
		if el >= osn:
			try:
				a_st[el - osn] += a_st[el]
			except KeyError:
				a_st[el - osn] = a_st[el]
			finally:
				del a_st[el]
				k_add.add(el - osn)
				k_.add(el)
	for el in k_:
		k_a.remove(el)
	for el in k_add:
		k_a.add(el)
	k_ = set()
	k_add = set()
	for el in k_b:
		if el >= osn:
			try:
				b_st[el - osn] += b_st[el]
			except KeyError:
				b_st[el - osn] = b_st[el]
			finally:
				del b_st[el]
				k_add.add(el - osn)
				k_.add(el)
	for el in k_:
		k_b.remove(el)
	for el in k_add:
		k_b.add(el)
print(ans)


(n, _) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
(m, _) = map(int, input().strip().split())
b = list(map(int, input().strip().split()))

def solve(T):
	nonlocal a, b
	d = dict()
	for i in b:
		pos = i % T
		if pos in d:
			d[pos] += 1
		else:
			d[pos] = 1
	for i in a:
		pos = (i + T / 2) % T
		if pos in d:
			d[pos] += 1
		else:
			d[pos] = 1
	return max(d.values())
T = 2
ans = 0
while True:
	ans = max(ans, solve(T))
	T *= 2
	if T > 1000000000.0:
		break
if len(set(a) and set(b)) > 0:
	ans = max(ans, 2)
print(ans)


(n, w56) = map(int, input().split())
if n == 1:
	x = [int(input())]
else:
	x = [int(i) for i in input().split()]
(k, w90) = map(int, input().split())
if k == 1:
	y = [int(input())]
else:
	y = [int(i) for i in input().split()]
t = 0
import collections
for i in range(1, 35):
	m = collections.Counter()
	for j in range(n):
		m[(x[j] - 2 ** (i - 1)) % 2 ** i] += 1
	for j in range(k):
		m[y[j] % 2 ** i] += 1
	t = max(t, max([m[o] for o in m.keys()]))
if t >= 2:
	print(t)
else:
	p = 0
	for i in range(len(x)):
		for j in range(len(y)):
			if x[i] == y[j]:
				print(2)
				p = 1
				break
		if p == 1:
			break
	if p == 0:
		print(1)


(x, y) = map(int, input().split())
a = list(map(int, input().split()))
(o, p) = map(int, input().split())
b = list(map(int, input().split()))
ans = 0
from collections import defaultdict
for i in range(34):
	fac = 2 ** i
	fac2 = fac * 2
	if i == 33:
		fac = fac2
	map = defaultdict(int)
	for j in a:
		map[j % fac2] += 1
	for j in b:
		map[(j + fac) % fac2] += 1
	for v in map.values():
		ans = max(ans, v)
print(ans)