让我们考虑一下名为 Boom(又名 Hat)的著名游戏,它的规则很简单。
有 n 支球队参加比赛。每队有两名球员。游戏的目的是向队友解释单词,而不使用任何包含相同词根或发音相似的单词。
来自 i 队 (1 ≤ i ≤ n, 1 ≤ j ≤ 2) 的球员 j 有两个数字:aij 和 bij。这些数字相应地代表了该特定玩家所具有的解释能力和理解能力。
此外,游戏使用m张卡。每张卡片上都写有一个词。卡号 k (1 ≤ k ≤ m) 由数字 ck 来表征 - 它包含的单词的复杂性。
游戏开始前,将牌放入一副牌中并洗牌。然后各队依次进行比赛:第 1 队的第 1 名选手、第 2 队的第 1 名选手、...、第 n 队的第 1 名选手、第 1 队的第 2 名选手、...、第 n 队的第 2 名选手、第 1 队的第 1 名选手,依此类推。
每回合持续 t 秒。它是这样的:最初每轮的时间是 t。当玩家剩下的时间大于 0 时,玩家从牌堆顶部取出一张牌,并开始向队友解释牌上的单词。第 i 队的第 j 名玩家向其队友(第 i 队的第 q 名玩家)解释卡片 k 中的单词所需的时间等于 max(1, ck - (aij + biq) - dik)(如果 j = 1,则 q = 2,否则 q = 1)。 dik 值是第 i 个团队在前几轮中已经花费在解释单词 k 上的秒数。最初,所有 dik 都等于 0。如果一方在回合结束前成功猜出单词,则从回合持续时间中减去上面给出的时间,包含猜出单词的卡片离开游戏,该小组赢得一分,游戏继续。如果团队未能猜出该单词,则该卡将被放在牌堆的底部,dik 会增加回合中用于解释该单词的时间。因此,当这个团队得到同一个词时,他们不是从头开始解释,而是从他们停下来的地方开始解释。当所有 m 张卡片上的单词都被猜对时,游戏结束。
你有n支球队和一副m张牌。您应该确定每个团队在游戏结束时将获得多少分以及该团队将猜出哪些单词。
输入
第一行包含两个整数n, t (1 ≤ n, t ≤ 100),分别表示队伍数量和回合持续时间。
输入文件的接下来 n 行每行包含四个整数:ai1, bi1, ai2, bi2 (1 ≤ aij, bij ≤ 100) — 第 i 队的第一名和第二名球员的技能。球队按照比赛顺序给出。
输入文件的下一行包含整数 m (1 ≤ m ≤ 100) 的卡片数量。
接下来的 2m 行包含卡片的描述。每张卡有两行描述。描述的第一行包含不超过 20 个字符的单词。这些单词仅包含小拉丁字母。描述的第二行包含一个整数 ck (1 ≤ ck ≤ 100) — 第 k 张卡片上所写单词的复杂度。这些牌按照牌中从上到下的顺序列出。所有卡片上的字都不同。
输出
打印 n 行。在第 i 行,首先打印数字 si,即第 i 队获胜的分数。然后打印 si 个空格分隔的单词——i 组按照猜出的顺序猜出的卡片上的单词。
示例
输入 #1
2 2 1 1 1 1 1 1 1 1 3 home 1 car 1 brother 1
输出 #1
2 home car 1 brother
输入 #2
2 4 1 2 2 1 2 3 2 2 4 armchair 3 quetzalcoatl 10 pilotage 5 defibrillator 7
输出 #2
2 armchair quetzalcoatl 2 pilotage defibrillator