Concentric Circles

Time limit2sMemory limit1024 MB

Summary

Two families of concentric circles have distinct centers; count the bounded regions that all the circles form together.

Level: Medium7 of 10
Topics: Math, Geometry, Binary search
Solved: No attempts yet

Statement

Space invaders once again sent an expedition to Earth. To intimidate the local population, they decided to draw circles in the fields.

The invaders picked a point $(x_1, y_1)$ on the field and drew $n$ circles centered at this point with radii $a_1, a_2, \dots, a_n$ . Then they drew $m$ circles centered at another point $(x_2, y_2)$ with radii $b_1, b_2, \dots, b_m$ .

The people of Earth are not especially wary of visitors from space, but just in case, they want to know how many regions bounded by the circle lines drawn by the invaders appeared on the field.

Input

The first line contains two integers $x_1$ and $y_1$ ( $-10^9 \le x_1, y_1 \le 10^9$ ).

The second line contains an integer $n$ ( $1 \le n \le 100\,000$ ). It is followed by $n$ integers $a_1, a_2, \dots, a_n$ in strictly increasing order ( $1 \le a_i \le 2 \cdot 10^9$ ).

The third line contains two integers $x_2$ and $y_2$ ( $-10^9 \le x_2, y_2 \le 10^9$ ). It is guaranteed that the points $(x_1, y_1)$ and $(x_2, y_2)$ are distinct.

The fourth line contains an integer $m$ ( $1 \le m \le 100\,000$ ). It is followed by $m$ integers $b_1, b_2, \dots, b_m$ in strictly increasing order ( $1 \le b_i \le 2 \cdot 10^9$ ).

Output

Print one number: the number of regions formed by the circles, not counting the outer region.

Hint

In the first example, the regions look as follows:

Examples3

Example 1
Input
```
3 8
2 5 6
9 13
2 3 4
```
Expected output
```
9
```
Example 2
Input
```
1 1
1 1
5 4
2 4 6
```
Expected output
```
3
```
Example 3
Input
```
-1000 2345
1 1
934 -1344
4 4 5 6 10
```
Expected output
```
5
```