Divide and Rule 2.0

Time limit1sMemory limit1024 MB

Summary

Given an array of distinct values, count the positions in each query range [l, r] whose value divides d or is a multiple of d.

Level: Hard8 of 10
Topics: Number theory, Prefix sum, Array
Solved: No attempts yet

Problem

Sasha loves the division operation so much that he invented a problem for the autumn informatics tournament that uses only division. The problem gives him a favorite array of $N$ positive integers $a_1, a_2, \ldots, a_N$ and $Q$ queries. The $i$ -th query is given by three positive integers $l_i$ , $r_i$ , and $d_i$ . For each query, count the numbers at positions $l_i$ through $r_i$ in the array that are divisors of $d_i$ or multiples of $d_i$ . Time is running out, and you want first place, so write a program divide.cpp that answers the queries.

Input

The first line contains the integers $N$ and $Q$ . The second line contains $N$ integers $a_1, a_2, \ldots, a_N$ . Each of the following $Q$ lines contains $l_i$ , $r_i$ , and $d_i$ .

Output

Print one line with $Q$ integers. The $i$ -th integer is the answer to the $i$ -th query.

Constraints

$1 ≤ N, Q ≤ 100000$ , $1 ≤ a_i, d_i ≤ 200000$ , $1 ≤ l_i ≤ r_i ≤ N$ . For all $1 ≤ i < j ≤ N$ , $a_i e a_j$ .

Examples1

Example 1

Input

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

Expected output

6 1 3 1 2