|
Темы:
Разреженные таблицы (sparse table)
Недавно вышла новая игра Counter-Strike 2. В 5-м классе учится N человек, и все они хотят поиграть в эту игру. На уроке физкультуры всех учеников построили в шеренгу. У физрука Олега Евгеньевича сегодня смешанное настроение: он решил разрешить ученикам поиграть в CS2 вместо физических занятий, но играть они будут только по определенным правилам.
Олег Евгеньевич будет разрешать играть всем ученикам, номер в шеренге которых лежит в отрезке \([L;R]\). Олег Евгеньевич узнал, что родители детей разрешают играть им в компьютер только ti минут. Но ученики очень любят компьютерные игры, поэтому каждый будет играть ровно ti минут, при этом играть никто не отказывается.
Игра происходит следующим образом: выбирается время матча такое, что каждый ученик должен сыграть строго целое число матчей, при этом количество сыгранных матчей у каждого ученика может различаться и время матча должно быть максимально возможным.
Например, играют 2 игрока. Если у играющего 1 время \(t_1 = 12\), а у играющего 2 время \(t_2 = 8\), то максимально возможное время матча 4 минуты. 1 играющий сможет сыграть 3 матча по 4 минуты, а 2 – 2 матча по 4 минуты.
Олег Евгеньевич в последнее время усердно занимается математикой, поэтому он решил M раз посчитать максимальное время Q для играющих от L до R. Вам следует проверить Олега Евгеньевича. Для этого следует вывести YES, если он прав, иначе – NO.
Входные данные
Первая строка содержит число N (\(1 <= N <= 10000\)) – количество ребят. Во второй строке записаны N чисел – ti (\(1 <= t_i <= 1000\)), время, которое дают родители i-ому ребенку на игру. В третьей строке записано число M (\(1 <= M <= 10^8\)), количество запросов. Далее, в M строках идут 3 числа L, R, Q (время, которое посчитал Олег Евгеньевич).
Выходные данные
Выведите для каждого запроса YES, если Олег Евгеньевич правильно посчитал, иначе – NO.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
8 5 6
4
1 2 2
1 3 1
2 3 1
1 3 2 |
NO
YES
YES
NO |
|