CF#509 Div2 F. Ray in the tube

You are given a tube which is reflective inside represented as two non-coinciding, but parallel to $O x$ 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.

$\text{[math]}$ 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 \leq n \leq 10^{5}$ , $0 \leq y_{1} \leq 10^{9}$ ) — number of sensors on the first line and its $y$ coordinate.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $0 \leq a_{i} \leq 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 \leq m \leq 10^{5}$ , $y_{1} < y_{2} \leq 10^{9}$ ) — number of sensors on the second line and its $y$ coordinate.

The fourth line contains $m$ integers $b_{1}, b_{2}, \dots, b_{m}$ ( $0 \leq b_{i} \leq 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

Copy

output

Copy

Note

One of the solutions illustrated on the image by pair $A_{2}$ and $B_{2}$ .

考试的时候智障没想出来，下来去剪头的时候突然知道怎么做。

首先考虑如果没有整点限制我们直接把斜率接近inf就可以完成经过所有点这个操作。

那么我们可不可以贪心呢？可不可以选最小的单位1作为距离呢？

我们发现1不能凑出2，具体来说是这样：

其中黑色的是1，红色的是2，绿色的是4 。因为有两边的原因，所以和奇偶性有关。

那么我们只要枚举2^n然后把所有点在模意义下枚举扔进map就行了。

代码呢？有点懒没写

Rockdu's Blog