|
Темы:
Sparse tables
Recently, a new Counter-Strike 2 game has been released. There is N in 5th grade and they all want to play this game. At the physical education lesson, all the students were lined up. Physical education instructor Oleg Evgenievich is in a mixed mood today: he decided to allow students to play CS2 instead of physical activities, but they will only play according to certain rules.
Oleg Evgenievich will allow all students to play, whose line number lies in the segment \([L;R]\). Oleg Evgenievich found out that the parents of children are only allowed to play on the computer for ti minutes. But the students are very fond of computer games, so everyone will play exactly ti minutes, while no one refuses to play.
The game is played as follows: a match time is chosen such that each student must play a strictly integer number of matches, while the number of matches played by each student may vary and the match time should be as long as possible.
For example, 2 players are playing. If player has 1 time \(t_1 = 12\) and player 2 has \(t_2 = 8\) , then the maximum possible match time is 4 minutes. 1 player will be able to play 3 matches of 4 minutes, and 2 – 2 matches of 4 minutes.
Oleg Evgenievich has been hard at work lately, so he decided M times to calculate the maximum time Q for players from L to R. You should check Oleg Evgenievich. To do this, print YES if it is correct, otherwise – NO.
Input
The first line contains the number N (\(1 <= N <= 10000\)) – the number of guys. The second line contains N numbers – ti (\(1 <= t_i <= 1000\)), time, given by the parents i-th child to play. The third line contains the number M (\(1 <= M <= 10^8\)), the number of queries. Further, in M lines there are 3 numbers L, R, Q (time calculated by Oleg Evgenievich).
Imprint
Output for each request YES if Oleg Evgenievich calculated correctly, otherwise – NO.
Examples
| # |
Input |
Output |
| 1 |
3
8 5 6
4
1 2 2
1 3 1
2 3 1
1 3 2
| NO
YES
YES
NO |
|