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

В одной школе с Васей учится мальчик Костя. Костя не любит физику, он любит разные онлайн игры. Каждый день, приходя домой, Костя бросает свою сумку в самый дальний угол и садится за свой любимый компьютер. Костя даже ест не отрываясь от игры. На днях Костик купил новую RPG игру «ЗайцButtle», которая отличается от всех своих конкурентов в этом жанре огромным количеством артефактов. Как известно, артефакты делятся на базовые и составные. В продаже доступны только базовые артефакты. Более мощные составные артефакты собираются из некоторого количества базовых артефактов.

После сборки составного артефакта, все его компоненты изчезают.

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

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

В первой строке находится 4 натуральных числа: k (1 ≤ k ≤ 100) — количество союзников Кости, n (1 ≤ n ≤ 50) — количество базовых артефактов, m (0 ≤ m ≤ 50) — количество составных артефактов, q (1 ≤ q ≤ 500) — количество покупок его друзей. Следующие n строк содержат названия базовых артефактов. После них в m строках содержатся описания составных артефактов в следующем формате:

<Название арт.>: <Арт. №1> <Количество aрт. №1>, <Арт. №2> <Количество aрт. №2>, ... <Арт. №X> <Количество aрт. №Х>

Все количества — натуральные числа, не большие 100 (1 ≤ X ≤ n).

Названия всех артефактов различны, состоят из строчных букв латинского алфавита, длина каждого названия — от 1 до 100 символов включительно. Все слова в формате описания составного артефакта разделены ровно одним пробелом. Гарантируется, что все составляющие нового артефакта различны и уже встречались во входных данных в качестве названий базовых артефактов.

Дальше каждая из последующих q строчек характеризуется числом ai, номером друга, купившего артефакт (1 ≤ ai ≤ k), и наименованием купленного базового артефакта. Будем считать, что рюкзаки у героев бездонные и любой последующий купленный артефакт влезает.

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

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

Выходной файл должен состоять из k блоков. В первой строке должно находиться число bi — количество различных артефактов у i-ого союзника. Далее в блоке должно располагаться bi строк с наименованиями этих артефактов и количеством этих артефактов, причем строки должны быть выведены в соответствии с лексикографическим порядком названий артефактов. В каждом блоке все артефакты должны быть различны, а все числа кроме bi положительны.

Примеры
Входные данные
2 3 2 5
desolator
refresher
perseverance
vanguard: desolator 1, refresher 1
maelstorm: perseverance 2
1 desolator
2 perseverance
1 refresher
2 desolator
2 perseverance
Выходные данные
1
vanguard 1
2
desolator 1
maelstorm 1