- Prepare
- Algorithms
- Dynamic Programming
- GCD Matrix

# GCD Matrix

# GCD Matrix

Alex has two arrays defined as and . He created an matrix, , where for each in . Recall that is the greatest common divisor of and .

For example, if and , he builds like so:

Alex's friend Kiara loves matrices, so he gives her questions about matrix where each question is in the form of some submatrix of with its upper-left corner at and its bottom-right corner at . For each question, find and print the number of *distinct* integers in the given submatrix on a new line.

**Input Format**

The first line contains three space-separated integers describing the respective values of (the size of array ), (the size of array ), and (Alex's number of questions).

The second line contains space-separated integers describing .

The third line contains space-separated integers describing .

Each line of the subsequent lines contains four space-separated integers describing the respective values of , , , and for the question (i.e., defining a submatrix with upper-left corner and bottom-right corner ).

**Constraints**

**Scoring**

- for of score.
- for of score.

**Output Format**

For each of Alex's questions, print the number of *distinct* integers in the given submatrix on a new line.

**Sample Input 0**

```
3 3 3
1 2 3
2 4 6
0 0 1 1
0 0 2 2
1 1 2 2
```

**Sample Output 0**

```
2
3
3
```

**Explanation 0**

Given and , we build the following :

The diagram below depicts the submatrices for each of the questions in *green*:

- For the submatrix between and , the set of integers is . The number of distinct integers is .
- For the submatrix between and , the set of integers is . The number of distinct integers is .
- For the submatrix between and , the set of integers is . The number of distinct integers is .