Задача №113467. Распродажа
В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c i , время его завоза в магазин a i и время его вывоза из магазина b i .
У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m j , время s j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.
Помогите Иннокентию определить, какие из его планов можно выполнить.
В первой строке входных данных содержится число N — общее количество товаров в магазине ( 1 ≤ N ≤ 500 ). Далее содержатся описания товаров, каждый товар описывается тремя целыми числами c i , a i , b i , обозначающими стоимость товара, время его завоза и время его вывоза из магазина ( 1 ≤ c i ≤ 1 000 , 1 ≤ a i < b i ≤ 10 9 ).
Далее содержится число M — количество планов Иннокентия ( 1 ≤ M ≤ 500 000 ). Каждый план описывается тремя целыми числами m j , k j , s j , обозначающими время прихода Иннокентия в магазин, сумму денег, которую он готов потратить в этом плане и длительность его пребывания в магазине ( 1 ≤ m j ≤ 10 9 , 1 ≤ k j ≤ 100 000 , 0 ≤ s j ≤ 10 9 ).
Помните, что это только планы, т. е. ситуация в магазине не меняется вне зависимости от того, может ли Иннокентий осуществить план или нет.
Для каждого плана в отдельной строке выведите « YES », если Иннокентий может его осуществить, и « NO » в противном случае.
Тесты к этой задаче состоят из четырех групп.
- Тест 1. Тест из условия, оценивается в ноль баллов.
- Тесты 2–7. В тестах этой группы M ≤ 10 , a i , b i , m j , s j ≤ 20 000 , k j ≤ 1 000 . Эта группа оценивается в 30 баллов.
- Тесты 8–11. В тестах этой группы N ≤ 200 , M ≤ 200 , k j ≤ 5 000 . Эта группа оценивается в 30 баллов.
- Тесты 12–23. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
5 6 2 7 5 4 9 1 2 4 2 5 8 1 3 9 5 2 7 1 2 7 2 3 2 0 5 7 2 4 1 5
YES NO YES YES NO