Задача №111552. Распродажа
В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость ci, время его завоза в магазин ai и время его вывоза из магазина bi.
У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине mj, время sj, которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег kj, которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно kj, при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.
Помогите Иннокентию определить, какие из его планов можно выполнить.
В первой строке входных данных содержится число N — общее количество товаров в магазине (1 ≤ N ≤ 500). Далее содержатся описания товаров, каждый товар описывается тремя целыми числами ci, ai, bi, обозначающими стоимость товара, время его завоза и время его вывоза из магазина (1 ≤ ci ≤ 1 000, 1 ≤ ai ≤ bi ≤ 109).
Далее содержится число M — количество планов Иннокентия (1 ≤ M ≤ 500 000). Каждый план описывается тремя целыми числами mj, kj, sj, обозначающими время прихода Иннокентия в магазин, сумму денег, которую он готов потратить в этом плане и длительность его пребывания в магазине (1 ≤ mj ≤ 109, 1 ≤ kj ≤ 100 000, 0 ≤ sj ≤ 109).
Помните, что это только планы, т. е. ситуация в магазине не меняется вне зависимости от того, может ли Иннокентий осуществить план или нет.
Для каждого плана в отдельной строке выведите «YES», если Иннокентий может его осуществить, и «NO» в противном случае.
Тесты к этой задаче состоят из четырех групп.
- Тест 1. Тест из условия, оценивается в ноль баллов.
- Тесты 2-7. В тестах этой группы M ≤ 10, ai, bi, mj, sj ≤ 20 000, kj ≤ 1 000. Эта группа оценивается в 30 баллов.
- Тесты 8-11. В тестах этой группы N ≤ 200, M ≤ 200, kj ≤ 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