Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3800

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


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


Author: LIN, Xi
Source: ZOJ Monthly, August 2014
Submit    Status