← 返回题目列表

Codeforces · 69/C

C. 游戏

中文机器翻译题面 查看原题

在 Vasya 所在的一所学校里,有一名学生 Kostya。 Kostya不喜欢物理,他喜欢不同的网络游戏。每天回到家,克斯特亚都会把他的包扔到最远的角落,然后坐在他心爱的电脑前。克斯特亚甚至一边吃着比赛一边吃东西。几天前,Kostya 购买了一款新的 RPG 游戏“HaresButtle”,该游戏不同于该类型的所有其他游戏。它拥有大量的文物。众所周知,工件分为基本工件和复合工件。仅出售基本文物。更强大的复合工件是从一些基本工件中收集的。

合成合成神器后,所有组件消失。

克斯特亚是联盟的首脑,所以他要记住,什么神器不仅有他自己,还有他的盟友。您必须根据克斯特亚和他的盟友购买的文物的顺序来确定他们每个人收集了多少文物以及哪些文物。据信最初没有人拥有任何文物。

输入

第一行有 4 个自然数:k (1 ≤ k ≤ 100) — Kostya 盟友的数量,n (1 ≤ n ≤ 50) — 基本神器的数量,m (0 ≤ m ≤ 50) — 复合神器的数量,q (1 ≤ q ≤ 500) — 他朋友购买的数量。以下 n 行包含基本工件的名称。在它们之后的 m 行包含以下格式的复合工件的描述:

<艺术。名称>:<艺术。 §1> <艺术。 No.1 号>,<艺术。 §2> <艺术。 №2 编号>,... <艺术。 §X> <艺术。 No.Х 编号>

所有数字均为不超过 100 的自然数 (1 ≤ X ≤ n)。

所有神器的名称都不同,均由小写拉丁字母组成,每个名称的长度为 1 到 100 个字符(含)。复合工件描述格式中的所有单词均由一个空格分隔。保证新工件的所有组件都是不同的,并且已经在输入数据中满足作为基本工件的名称。

接下来,下面的每行q行的特征是数字ai、购买神器的朋友的编号(1≤ai≤k)以及购买的基础神器的名称。假设英雄的背包无限大,以后购买的任何神器都可以装进去。

保证第i次购买后不会出现超过一次收集复合神器的机会。如果有这样的机会,英雄就必须抓住它。

输出

输出文件应由 k 个块组成。第一行应包含数字 bi — 第 i 个盟友拥有的不同文物的数量。然后该块应包含带有这些工件的名称和这些工件的数量的双行。此时,应按照文物名称的字典顺序打印线条。在每个块中,所有工件必须不同,并且除 bi 之外的所有数字都应该为正。

示例

输入 #1

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

1
vanguard 1
2
desolator 1
maelstorm 1