Ray in the tube
Contest: Codeforces Round 509 (Div. 2)
Difficulty rating: 2500
Tags: data structures, divide and conquer, dp, math

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.

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 format:
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 format:
Print the only integer — the maximum number of sensors which can register the ray.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
3 1
1 5 6
1 3
3

Example output:
3

Editorial:
At first, $$$y$$$ coordinates don't matter. Let $$$dx$$$ be signed difference between $$$x$$$ coordinates of $$$B$$$ and $$$A$$$, then on the first line all points with coordinates $$$x_A + dx \cdot (2k)$$$ will be chosen, and on the second line all points with coordinates $$$x_A + dx \cdot (2k + 1)$$$ will be chosen.
Let's prove that it is always optimal to take $$$dx = 2^l$$$ where $$$l \ge 0$$$. Let $$$dx$$$ is not a power of two, then $$$dx = m \cdot 2^l$$$, where $$$m$$$ is odd. Note that $$$dx / m$$$ hits all points which is hitted by $$$dx$$$ that why answer will not decrease.
So, we need to check only $$$dx = 2^l$$$, number of such $$$dx$$$ is equal to $$$O(\log(10^9))$$$.
For the fixed $$$dx$$$ note that ray hits both points on the same line iff $$$x_1 \equiv x_2 \mod{(2 \cdot dx)}$$$. Analogically, the ray hits both points on the different lines iff $$$x_1 + dx \equiv x_2 \mod{(2 \cdot dx)}$$$.
That's why we can split all point on the equivalent classes modulo $$$2 \cdot dx$$$ and take the size of the biggest class. We can do it by sort and two pointers or by $$$map$$$.
Result complexity is $$$O(n \log{(10^9)} \log n)$$$ time and $$$O(n)$$$ memory.