Calculation

Time Limit: 5 Seconds
Memory Limit: 262144 KB

You are given a sequence {`A`_{0}, `A`_{1}, ..., `A`_{N-1}} and an integer set called `GS`. Defined a function called `G`(`L`, `R`) on `A`, where `G`(`L`, `R`) = GCD(`A`_{i}) (`L` ≤ `i` < `R`) that is the greatest common divisor of all the integers in the subsequence {`A`_{L}, `A`_{L+1}, ..., `A`_{R-1}}.

Now There're several questions for you. Give you three integers `L`, `R` and `g`, where `g` is an integer in `GS`. You need to calculate how many integer pairs (`l`, `r`) satisfy the condition that `G`(`l`, `r`) = `g` and `L`` ≤ ``l` < `r` ≤ `R`.

#### Input

Input will consist of multiple test cases.
The first line of each case contains three integers `N`, `M`, `Q` (1≤ `N`, `Q`≤ 100000, 1 ≤ `M` ≤ 50), separated by spaces.
The second line contains `N` integers, `A`_{0}, `A`_{1}, ..., `A`_{N-1} (1≤ `A`_{i}≤ 100000).
The third line contains `M` integers, indicating the set `GS`. Every integer in `GS` is positive and less than 2000.
For the next `Q` line, each line contains three integers, `L`, `R`, `g` (0≤ `L`< `R`≤ `N`, `g`∈ `GS`).

#### Output

For each case, output `Q` lines. Each line contains an integer, indicating the answer for the query.

#### Sample Input

4 4 4
1 2 3 4
1 2 3 4
0 4 1
0 4 2
0 4 3
0 4 4

#### Sample Output

7
1
1
1

Author:

**LIN, Xi**
Source:

**ZOJ Monthly, August 2014**
Submit
Status