Deposits

Time limit3sMemory limit256 MB

Summary

Count pairs of deposits and requests where the deposit amount is divisible by the request length, using frequency counts and divisor enumeration up to 10^6.

Level: Medium4 of 10
Topics: Math, Number theory, Hash map
Solved: No attempts yet

Problem

During a financial crisis, many central banks deposit large amounts of cash into investment and savings banks to provide liquidity and support credit markets.

The central bank of Flatland plans to place $n$ deposits on the market. Each deposit is described by its amount $a_i$ .

Banks send requests for deposits to the market. There are currently $m$ requests. Each request is described by its length $b_i$ , measured in days.

Market regulations require every deposit to be refinanced by an equal integer amount each day. Therefore a deposit with amount $a$ and a request with length $b$ match each other if and only if $a$ is divisible by $b$ .

Given the deposits and the requests, find the number of deposit-request pairs that match.

Input

The first line contains $n$ , the number of deposits ( $1 \le n \le 100\,000$ ).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ).

The third line contains $m$ , the number of requests ( $1 \le m \le 100\,000$ ).

The fourth line contains $m$ integers $b_1, b_2, \dots, b_m$ ( $1 \le b_i \le 10^6$ ).

Output

Print a single integer — the number of matching pairs.

Note

Every request is counted individually, so a deposit can match the same length more than once when that length is requested several times.

For the deposits $3, 4, 5, 6$ and the request lengths $1, 1, 2, 3$ , the matching (deposit, length) pairs are $(3,1)$ twice, $(3,3)$ , $(4,1)$ twice, $(4,2)$ , $(5,1)$ twice, $(6,1)$ twice, $(6,2)$ , and $(6,3)$ — $12$ pairs in total.

Examples4

Example 1
Input
```
4
3 4 5 6
4
1 1 2 3
```
Expected output
```
12
```
Example 2
Input
```
1
1
1
1
```
Expected output
```
1
```
Example 3
Input
```
2
2 4
2
3 5
```
Expected output
```
0
```
Example 4
Input
```
3
7 10 3
4
1 1 1 1
```
Expected output
```
12
```