今年秋天,两支俄罗斯球队进入了世界上最负盛名的足球俱乐部赛事——欧洲冠军联赛的小组赛阶段。现在,这些球队已经开始小组赛的比赛,正在为晋级季后赛而奋斗。在这个问题中,我们感兴趣的是抽签阶段,即将球队分组的过程。
抽奖过程如下(本问题中描述的规则与现实生活相比有所简化)。假设n支球队将参加小组赛(n可被4整除)。团队应分为四人一组。我们将组数表示为 m ($$m = \frac{n}{4}$$)。每个团队都有一个评级——一个描述团队之前成就的整数。球队按评分递减排序(没有两支球队具有相同的评分)。
之后形成四个“篮子”,每个“篮子”将包含 m 支球队:评分最高的前 m 支球队进入第一个篮子,随后的 m 支球队进入第二个篮子,依此类推。
然后以下过程重复 m - 1 次。从每个篮子中随机抽取一支球队,首先从第一个篮子中,然后从第二个篮子中,然后从第三个篮子中,最后从第四个篮子中。被淘汰的球队组成另一个小组。之后,将它们从篮子中取出。
执行(m - 1)次这样的程序后留在篮筐中的四支球队组成最后一组。
在真正的抽签中,从篮子里随机选择球队是由人们执行的——通常是过去的知名球员。由于我们没有,我们将使用随机数生成器,其构造如下。它的参数是四个正整数x、a、b、c。每次调用随机数生成器时,它都会产生以下操作:
- 计算 $$y = ( x \cdot a + b ) \mod c$$;
- 用值 y 替换参数 x (分配 $$\dot{x}:=y$$);
- 返回 x 作为另一个随机数。
运算$$\bmod$$表示除法后取余数:$$10 \mod 7 = 3$$,$$26 \mod 2 = 0$$。
抽签中将使用随机数生成器,如下所示:每次我们需要从篮子中随机选择一支球队时,它将生成一个随机数 k。仍然留在篮子里的球队被认为是用从 0 到 s - 1 的连续整数进行编号,按照评级递减的顺序,其中 s 是篮子的当前大小。然后从篮子中取出球队号码$$k \mod s$$。
给定球队列表和随机数生成器的参数,确定抽签结果。
输入
第一输入行包含整数 n(4 ≤ n ≤ 64,n 可被 4 整除)——参与排序的团队数量。第二行包含四个空格分隔的整数 x, a, b, c (1 ≤ x, a, b, c ≤ 1000) — 随机数生成器的参数。以下 n 行中的每一行描述一个团队。描述由团队名称及其评级组成,以单个空格分隔。队伍名称由大小写英文字母组成,长度为1~20个字符。球队的评分是 0 到 1000 之间的整数。所有球队的名称都是不同的。所有球队的评分也各不相同。
输出
打印团队必须分组的方式。按排序时形成的顺序打印组。从字母“A”开始,用连续的大写英文字母对组进行编号。在每组内每行打印一个团队名称,按照团队评级递减的顺序。请参阅示例以更好地了解输出格式。
示例
输入 #1
8 1 3 1 7 Barcelona 158 Milan 90 Spartak 46 Anderlecht 48 Celtic 32 Benfica 87 Zenit 79 Malaga 16
输出 #1
Group A: Barcelona Benfica Spartak Celtic Group B: Milan Zenit Anderlecht Malaga
注意
在给定的样本中,随机数生成器将执行四次:
- $$(1 \cdot 3 + 1) \mod 7 = 4$$,
- $$( 4 \cdot 3 + 1 ) \mod 7 = 6$$,
- $$(6 \cdot 3 + 1) \mod 7 = 5$$,
- $$( 5 \cdot 3 + 1 ) \mod 7 = 2$$。