Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3800
Calculation

Time Limit: 5 Seconds      Memory Limit: 262144 KB

You are given a sequence {A0, A1, ..., AN-1} and an integer set called GS. Defined a function called G(L, R) on A, where G(L, R) = GCD(Ai) (Li < R) that is the greatest common divisor of all the integers in the subsequence {AL, AL+1, ..., AR-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 Ll < rR.

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, A0, A1, ..., AN-1 (1≤ Ai≤ 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< RN, gGS).

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