ADATAXES - Ada and Taxes

As you might already know, Ada the Ladybug is a farmer. She grows vegetables in a long furrow. All of the vegetables have some height. Local politicians tax small vegetables, but as the furrow is very long, they always tax just a part of it.

The taxes always have some limit on height. They are calculated very simply: Tax collectors multiply the heights of all vegetables, which are lesser or equal to limit and are on desired segment.

The taxes might be very high so tax collectors just round their income and take only 1000000007 (109+7) banknotes. They are very kind, so they always leave the rest to Ada. She is interested in how much they will leave her.

NOTE: If none of the vegetable is lesser/equal to given limit, Ada is left with symbolical 1 "money".

Input

The first line contains an integer 1 ≤ N, Q ≤ 3*105, the number of vegetables Ada grows and the number of times the tax collectors come.

The second line contains N integers 1 ≤ Ai ≤ 3*105, the heights of vegetables.

The next Q lines contains three integers 0 ≤ L ≤ R < N, the left and right vegetables of segment and 1≤ H ≤ 3*105, the limit.

Output

Print a single line for each query with the number of money Ada will be left with after each tax collecting.

Example Input

10 6
1 2 3 4 5 10 9 8 7 6
5 5 5
0 2 3
0 9 9
4 8 8
2 4 11
2 2 3

Example Output

1
6
362880
280
60
3

Added by:Morass
Date:2017-06-29
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2021-09-23 09:12:53
persistent segment tree
2020-12-10 02:07:49
NlogN + Q (logN)^2 with fast IO
2020-12-09 08:20:52
How was it related to binary search btw?
2020-07-26 16:21:26
What was number theory in this?
It was purely segment tree.
2020-02-26 07:11:29
cin,cout costed me extra two WA finally solved
segment tree +binarySearch
2018-08-23 19:07:54 DOT
Woah! Getting TLE with O(NlogN + QlogQ + Q√A) approach. Should try with segment tree, I guess.
Edit: Got AC by gambling on the block size. :) But still should attempt segment tree as I'm sure it'll be drastically faster.

Last edit: 2018-08-23 19:25:53
2017-06-29 14:38:03
@[Rampage] Blue.Mary: Sorry, seems I deleted part of input instead of harsh warning :'( is it better now? :O
2017-06-29 12:20:14 [Rampage] Blue.Mary
The input specification doesn't match the sample input.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.