C. Мир Вещей
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Каждый предмет в игре имеет уровень. Чем выше уровень — тем более высокие базовые параметры имеет вещь. Мы будем рассматривать только следующие базовые параметры: атака (atk), защита (def) и сопротивления к различным воздействиям (res).

Каждая вещь принадлежит одному из классов. В данной задаче мы будем рассматривать только три таких класса: оружие (weapon), броня (armor), защитные сферы (orb).

Кроме того, внутри каждого предмета скрыт целый мир. С помощью путешествий в мир данного предмета можно повышать его уровень. Также в Мире Вещей можно захватывать так называемых резидентов.

Резиденты — это существа, которые живут внутри предметов. Каждый резидент дает некоторый бонус предмету, в котором он на данный момент находится. Мы будем рассматривать только резидентов типов: гладиатор (gladiator, увеличивает параметр atk предмета), часовой (sentry, увеличивает def) и целитель (physician, увеличивает res).

Каждый предмет имеет параметр вместимости. Он означает максимальное количество резидентов, которые могут жить внутри предмета. Резидентов можно перемещать между предметами. За один момент времени можно взять любого резидента в любом предмете, и переместить его в какой-либо другой предмет, если там есть место для нового жителя. При этом вынимать резидентов из предметов наружу не разрешается — каждый резидент обязательно должен быть в каком-либо предмете в любой момент времени.

У Лахарла есть некоторое количество предметов. Он хочет перераспределить резидентов между предметами таким образом, чтобы затем выбрать себе оружие, броню и защитную сферу для экипировки. При этом параметр оружия atk должен получиться максимально возможным. Из всех экипировок с максимальным параметром оружия atk параметр брони def должен быть максимальным. Из всех таких экипировок следует выбрать ту, в которой параметр защитной сферы res максимален. Значения параметров def и res у оружия, atk и res у брони и atk и def у защитной сферы Лахарлу безразличны.

Найдите оптимальную экипировку, которую Лахарл может получить.

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

В первой строке находится число n (3 ≤ n ≤ 100) — количество предметов у Лахарла.

Далее идут n строк, в каждой из которых описывается один предмет. Описание предмета имеет вид: «name class atk def res size» — имя предмета, его класс, базовые параметры атаки, защиты, сопротивления и вместимость соответственно.

  • name и class — строки, а atk, def, res и size — целые числа.
  • name состоит из малых латинских букв и имеет длину от 1 до 10.
  • class может быть "weapon", "armor" или "orb".
  • 0 ≤ atk, def, res ≤ 1000.
  • 1 ≤ size ≤ 10.

Гарантируется, что среди всех предметов имеется хотя бы один предмет каждого из трех классов.

В следующей строке находится целое число k (1 ≤ k ≤ 1000) — количество резидентов.

Далее идут k строк, в каждой из которых описывается один резидент. Описание резидента имеет вид: «name type bonus home» — имя резидента, его тип, количество очков, на которые увеличивает данный резидент соответствующий типу резидента параметр предмета и имя предмета, в котором резидент сейчас находится.

  • name, type и home — строки, а bonus — целое число.
  • name состоит из малых латинских букв и имеет длину от 1 до 10.
  • type может быть "gladiator", "sentry" или "physician".
  • 1 ≤ bonus ≤ 100.

Гарантируется, что количество резидентов в каждом предмете не превосходит вместимости предмета.

Имена всех предметов и резидентов попарно различны.

Все слова и числа во входных данных разделены одиночными пробелами.

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

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

Во второй и третьей строке в аналогичном формате выведите имена брони и защитной сферы, а так же имена резидентов, находящихся в них.

В качестве разделителей используйте одиночные пробелы.

Если возможных решений несколько — выведите любое.

Примеры
Входные данные
4
sword weapon 10 2 3 2
pagstarmor armor 0 15 3 1
iceorb orb 3 2 13 2
longbow weapon 9 1 2 1
5
mike gladiator 5 longbow
bobby sentry 6 pagstarmor
petr gladiator 7 iceorb
teddy physician 6 sword
blackjack sentry 8 sword
Выходные данные
sword 2 petr mike 
pagstarmor 1 blackjack 
iceorb 2 teddy bobby
Входные данные
4
sword weapon 10 2 3 2
pagstarmor armor 0 15 3 1
iceorb orb 3 2 13 2
longbow weapon 9 1 2 1
6
mike gladiator 5 longbow
bobby sentry 6 pagstarmor
petr gladiator 7 iceorb
teddy physician 6 sword
blackjack sentry 8 sword
joe physician 6 iceorb
Выходные данные
longbow 1 mike 
pagstarmor 1 bobby 
iceorb 2 petr joe
Примечание

Во втором примере свободного места в предметах нет, поэтому перемещать резидентов нельзя.