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}`) (

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 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`).

提交代码