Счастливые телефоны
В стране Эдем все телефонные разговоры наполнены счастьем. Люди, которые жалуются по телефону, немедленно отправляются в тюрьму. Чтобы обеспечить соблюдение этого закона, полиция прослушивает все телефонные разговоры.
Полиция хочет нанять необходимое количество операторов для прослушивания всех разговоров в заданный период времени. К сожалению, каждый оператор может прослушать только один разговор, прежде чем ему потребуется длительный отдых от напряженной работы.
Как подрядчик полицейского департамента, вас попросили создать программу, которая определит необходимое количество операторов. Если программа не будет работать правильно, вас также посадят в тюрьму вместе со всеми несчастными жалобщиками. Вы действительно хотите оказаться там?
Входные данные
Каждый тестовый случай начинается с двух целых чисел, обозначающих количество телефонных звонков N (1 ≤ N < 10 000) и количество интервалов M (1 ≤ M < 100). Далее следуют N строк, описывающих телефонные звонки, каждая из которых состоит из четырех целых чисел Source, Destination, Start и Duration. Source и Destination идентифицируют пару телефонных номеров, устанавливающих соединение (0 ≤ Source, Destination ≤ 10 000 000). Start и Duration — это время начала и продолжительность звонка в секундах (1 ≤ Duration ≤ 10 000 и Start ≥ 0). Вы можете быть уверены, что сумма Start и Duration помещается в 32-битное целое число со знаком.
Далее следуют M строк, содержащих временные интервалы, которые интересуют полицию, каждый из которых описывается двумя целыми числами Start и Duration, в том же формате и с теми же ограничениями, что и в телефонных звонках. Последний тестовый случай представлен N = M = 0 и не должен обрабатываться.
Выходные данные
Для каждого из M интервалов каждого тестового случая выведите количество звонков, которые активны в течение хотя бы одной секунды интервала.