Задача 5. Рынок ≡

Входной файл:in   Ограничение времени:3 сек
Выходной файл:out   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

На центральном рынке часто происходит распродажа различных продовольственных товаров. Каждый товар привозят на рынок в определенное время, и через некоторое время увозят, то есть каждый товар имеет стоимость ci, время завоза ai и время вывоза bi.

Молодожены Аня и Вася запланировали несколько походов на рынок на следующий месяц. План похода выглядит следующим образом: Аня и Вася выбирают время mj, когда они появятся на рынке, сумму денег kj, которую они планируют потратить и время sj, которое они проведут на рынке. Аня и Вася хотят узнать, смогут ли они осуществить свои планы, то есть верно ли, что они смогут во время своего пребывания на рынке накупить товаров суммарной стоимостью ровно kj, при этом все выбранные товары должны быть на рынке на протяжении всего пребывания Ани и Васи.

Формат входного файла

В первой строке содержатся натуральное число N – общее количество продовольственных товаров на рынке (1 ≤ N ≤ 500). В следующих N строках содержатся описания товаров, каждый товар описывается тремя натуральными числами ci – стоимость товара, ai – время завоза, bi – время вывоза (1 ≤ ci ≤ 1000, 1 ≤ ai < bi ≤ 109). В следующей строке содержится число M – количество планов Ани и Васи (1 ≤ M ≤ 500000). В следующих M строках описаны планы. Каждый план описывается тремя числами mj – время прихода Ани и Васи, kj – сумма денег, sj – время пребывания (1 ≤ mj ≤ 109, 1 ≤ kj ≤ 100000, 0 ≤ sj ≤ 109).

Формат выходного файла

Для каждого плана в отдельной строке вывести «YES», если Анна и Вася смогут его осуществить, и «NO» в обратном случае.

Примеры тестов

№ Входной файл (in) Выходной файл (out)
1 
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
0.191s 0.095s 15