Муниципальная олимпиада 2016 Камчатский край

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

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

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

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

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

В первой строке содержатся натуральное число N – общее количество продовольственных товаров на рынке (1 ≤ N ≤ 500). В следующих N строках содержатся описания товаров, каждый товар описывается тремя натуральными числами c_i – стоимость товара, a_i – время завоза, b_i – время вывоза (1 ≤ c_i ≤ 1000, 1 ≤ a_i < b_i ≤ 10⁹). В следующей строке содержится число M – количество планов Ани и Васи (1 ≤ M ≤ 500000). В следующих M строках описаны планы. Каждый план описывается тремя числами m_j – время прихода Ани и Васи, k_j – сумма денег, s_j – время пребывания (1 ≤ m_j ≤ 10⁹, 1 ≤ k_j ≤ 100000, 0 ≤ s_j ≤ 10⁹).

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

Для каждого плана в отдельной строке вывести «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`