F. Frosted Highway (Hard)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The difference between this and the easier problem is the constraint being queried on.

As the southern US prepares for the weekend's ice freeze, and the City of Austin has hired a surveyor to help you ensure all the highway markers are set up properly for drivers. Unfortunately the surveyor is nowhere near Austin, so the best way they can help is a virtual Zoom conference to ensure all the highway markers are set up properly.

The highway has $$$n$$$ markers indexed from $$$1$$$ to $$$n$$$, each with a height $$$h_i$$$. The surveyor has realized that different parts of the highway have a lot of differences, from the weather conditions of nearby cities to the materials used. In each of $$$q$$$ queries, he will provide you with the numbers $$$l$$$, $$$r$$$, and $$$k$$$, and needs to know how many markers in the interval $$$[l,r]$$$ satisfy $$$k \mid \gcd(h_i, i)^\dagger$$$. Help him out (again) ASAP, before the roads collapse!

$$$^\dagger$$$The notation $$$a\mid b$$$ denotes that $$$a$$$ divides $$$b$$$ (or $$$b$$$ is divisible by $$$a$$$), meaning there exists an integer $$$k$$$ such that $$$ka = b$$$. For instance, $$$3 \mid 6$$$, but $$$4 \nmid 7$$$.

Input

The first line contains two numbers, $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 10^4$$$), the number of markers on the highway and the number of queries respectively. The second line contains the array $$$h$$$ of $$$n$$$ integers, where $$$h_i$$$ denotes the height of the $$$i$$$th marker ($$$1 \le h_i \le 10^6$$$). The next $$$q$$$ lines each contain three numbers, $$$l$$$ $$$r$$$ and $$$k$$$ ($$$1 \le l \lt r \le n$$$, $$$1 \le k \le 10^3$$$), denoting the query as described in the problem statement.

Output

Print $$$q$$$ integers, where the $$$j$$$th integer represents the answer to query $$$j$$$.

Example
Input
5 5
8 6 5 4 10
3 4 1
2 3 2
1 5 1
1 5 2
1 5 5
Output
2
1
5
2
1