G. Derby
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It is the day of the Grand Derby at the Stade Hammadi Agrebi in Radès. The stadium is packed to capacity, and the atmosphere is electric.

As the lead audio engineer for the broadcast, you are monitoring a row of $$$n$$$ passionate fans in the "Virage" stand. Each fan at position $$$i$$$ has a specific vocal intensity level, represented by an integer $$$a_i$$$.

When a continuous segment of fans chants together, their voices create a "Resonance Wave". The Total Resonance of the segment from index $$$l$$$ to index $$$r$$$ is defined as the product of their individual intensities: $$$$$$ \text{Resonance}(l, r) = a_l \times a_{l+1} \times \dots \times a_r $$$$$$

The stadium's modern "Smart Audio System" filters noise based on power tiers. For a chant to be successfully broadcast clearly on the high-definition channel of Tier $$$k$$$, its Total Resonance must be divisible by $$$10^k$$$.

You must process $$$q$$$ queries from the control room. For each query $$$(l, r, k)$$$, determine if the chant from the fans between $$$l$$$ and $$$r$$$ (inclusive) qualifies for the Tier $$$k$$$ broadcast (i.e., is divisible by $$$10^k$$$).

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the number of fans in the row and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the vocal intensity of each fan.

Each of the next $$$q$$$ lines contains three integers $$$l$$$, $$$r$$$, and $$$k$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 10^9$$$) — the range of the fans and the required audio tier.

Output

For each query, output a single line:

  • YES — if the Total Resonance of the range is divisible by $$$10^k$$$.
  • NO — otherwise.
Example
Input
5 4
48 250 4 75 128
1 2 4
2 4 3
4 5 1
1 5 6
Output
NO
YES
YES
NO
Note

Note:

Query 1 $$$(l=1, r=2, k=4)$$$: The segment is $$$[48, 250]$$$, The Resonance is $$$48 \times 250 = 12000$$$. We check if $$$12000$$$ is divisible by $$$10^4$$$. Since $$$12,000$$$ is not divisible by $$$10000$$$, the answer is NO.

Query 2 $$$(l=2, r=4, k=3)$$$: The segment is $$$[250, 4, 75]$$$. The Resonance is $$$250 \times 4 \times 75 = 75000$$$. Since $$$75000$$$ is divisible by $$$10^3$$$, the answer is YES.