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 .