Harshit, the Proxy Master!

All submissions for this problem are available.
Harshit and Navdeep are bestfriends and roommates too! As we know that harshit is extremely famous for his proxy skills. One fine day, Navdeep decided to bunk his Android Development lecture and asked Harshit to mark his proxy if he will attend the lecture! Harshit told him that he will mark his proxy if and only if he will help him solve this problem.
You are given an array of size N and Q queries to be handled. In each query you will be provided with the value of L, R and K, find the value of f(L , R , K).
f(L , R , K){
ans = 0
for i : L to R
{
if sum of distinct prime factors of A[i] > K :
ans = ans + i * sum of distinct prime factors of A[i]
}
return ans
}
As you know, Navdeep is extremely lazy person, can you please solve this problem for him so that he will have his proxy marked by Harshit?
Input
The first line of the input contains two space separated positive integers N and Q denoting the number of elements in an array and number of queries to be handled. The next line contains N space separated positive integers A[1] , A[2] .... A[N] denoting the elements of array. Each of the next Q lines contains three space separated positive integers L , R and K.
Output
For each query, output the required answer in a separate line.
Constraints
1 <= N <= 10^6
1 <= Q <= 10^5
1 <= A[i] <= 10^7
1 <= L <= R <= N
1 <= K <= 10^7
Example
Input: 5 5 1 2 3 4 15 1 5 1 1 5 2 2 4 1 3 5 3 1 5 10 Output: 61 49 21 40 0
Explanation
Query1 :
L = 1 , R = 5 , K = 1
i G(A[i]) => Sum of Distinct Prime Factors of A[i]
1 0()
2 2(2)
3 3(3)
4 2(2)
5 8(3 + 5)
Since, G(A[2]) , G(A[3]) , G(A[4]) , G(A[5]) > K :
ans = 2 * G(A[2]) + 3 * G(A[3]) + 4 * G(A[4]) + 5 * G(A[5])
=> 2 * 2 + 3 * 3 + 4 * 2 + 5 * 8 => 61
Author:  code_hard123 
Tags  code_hard123 
Date Added:  25012017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYPY 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions