N Slovakistan farmers own neighbouring fields alongside a river, forming a straight line. Each field is infested with (possibly zero) pests.

Thanks to ingenious Slovakistan science, each species of pest can be assigned a prime number. Each field can then be assigned a positive number, representative of the pests that are infesting it - the prime factorization of this number indicates which pests are present, with the powers of each prime number representing how strongly the field is infested with that pest. The resulting number indicates how much damage is done to the crops on that field.

To help the farmers, the government is planning to spray pesticide on some contiguous segment of fields. Due to environmental concerns, the pesticide can only be effective against a single species of pest. However, what segment of fields to spray and with what pesticide has given rise to a huge debate in the parliament - there simply isn't enough data to decide. Given Q proposals L R p, meaning that pesticide against the pest assigned prime number p could be sprayed on fields L through R, find out how much damage to crops it would prevent.

Input

The first line of input contains two integers N and Q (1 ≤ N,Q ≤ 500,000): the number of fields and the number of proposals.

The second line contains N numbers f₁, ... , f_N - the numbers assigned to the fields. They will be positive and not greater than 10⁶.

Q lines follow, each containing three numbers L R p (1  ≤ L ≤ R ≤ N, 1 ≤ p ≤ 10⁶, p is a prime number), meaning that the government proposes to spray pesticide against pest p on fields [L,R]

Output

For each proposal L R p, output how much crop damage is mitigated; that is, output  (f_L + ... + f_R - f'_L - ... - f'_R ), where f'_i is f_i after all factors of p have been removed from it.

Example

Input:
5 5
10 20 30 40 50
1 1 2
1 5 5
1 5 47
2 4 3
2 4 2

Output:
5
128
0
20
65

In the fourth proposal, the result is (20 + 30 + 40 - 20 - 10 - 40) = 20.