Задача 2. Фильтр товаров

Автор:Д. Глушкова, В. Глушков   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Варфоломей устроился программистом-стажёром в одну известную компанию. Вместе со своим наставником Иннокентием они разрабатывали приложение для подбора товаров по пожеланиям клиентов. За продуктивную рабочую неделю они реализовали методы выбора товаров нужной категории, и тут Иннокентий заболел и вышел на больничный, но на носу дедлайн! Варфоломей обращается к дружному коллективу олимпиадников за помощью: помогите ему закончить приложение!

Для реализации главной задачи, а именно выбора узкой категории товаров, Варфоломей предоставил вам следующие данные: N - количество подобранных товаров соответствующей категории, для каждого из которых присутствуют 3 характеристики, а именно: цвет (R, G, B), размер (S, M, L) и цена (целое число).

К дедлайну необходимо сделать возможным обработку K запросов от клиентов следующего вида: 1 символ означает цвет, 2 — означает размер, а 3 символ, равный A либо D, означает в последовательности возрастания или убывания необходимо вывести список найденных товаров. Во время составления запросов клиенту может быть неважен цвет товара, его размер или последовательность вывода, тогда вместо символа нужной категории он ставит символ "_". Если клиенту не важна последовательность вывода или товары имеют одинаковую стоимость, то необходимо сохранить исходный порядок Варфоломей и его наставник надеются на вашу помощь!

Формат входных данных

Первая строка входных данных содержит целое число N. Далее идут N строк, содержащих 3 характеристики товара (цвет, размер и цену). Строка номер N + 1 содержит целое число K, далее идут K строк клиентских запросов.

Формат выходных данных

Выходные данные должны содержать K строк с перечислением товаров, удовлетворяющих запросу. Если для запроса не найдется хотя бы один товар, нужно вывести  − 1. Если клиенту не важна последовательность вывода или товары имеют одинаковую стоимость, то необходимо сохранить исходный порядок.

Ограничения

0 ≤ N, K ≤ 102

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача Баллы Дополнительные ограничения
Сортировка по цене
150Сортировка товаров по цене не требуется
150Сортировка товаров по цене требуется

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

Стандартный вход Стандартный выход
1
4
R S 5
G L 8
G S 7
B M 9
5
R _ A
B L D
G _ _
G L _
G _ A
R S 5
-1
G L 8 G S 7
G L 8
G S 7 G L 8

0.202s 0.093s 13