Выставка кошек

Чтобы найти самую красивую кошку на выставке, их всех сравнивают между собой по одному из параметров. Но сам параметр меняется каждый год, это может быть масса кошки, длина ее хвоста и т.д. Для параметра задается набор отрезков, за попадание в каждый из них присваивается определенное количество баллов. Например, если сравнивается масса кошек, то за массу от 0 до 2 кг можно получить 2 балла, от 3 до 5 кг - 5 баллов, а от 6 до 100 кг - 10 баллов.

Помогите организаторам выставки составить рейтинг кошек по сравниваемому параметру.

Входные данные

В первой строке входного файла INPUT.TXT записано целое число N - количество кошек (1 ≤ N ≤ 1000). В каждой из следующих N строк содержится описание кошки: кличка (из строчных латинских символов длиной не более 20 символов) и значение сравниваемого параметра P - целое число (1 ≤ P ≤ 100).

В следующей строке записано целое число K - количество отрезков (1 ≤ K ≤ 100). Каждая из следующих K строк содержит три целых числа: нижняя граница отрезка L, верхняя граница отрезка U и балл S, начисляемый за попадание параметра кошки в этот отрезок (1 ≤ L, U, S ≤ 100, L ≤ U).

Объединение отрезков охватывает все возможные значения данного параметра. Отрезки не пересекаются.

Выходные данные

В выходной файл OUTPUT.TXT выведите список кошек в порядке убывания набранных баллов. Для каждый кошки в отдельной строке необходимо вывести кличку и баллы через пробел. Если количество баллов у некоторых кошек совпадает, то следует их выводить в алфавитном порядке кличек.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!