小 S 想要举办一场擂台游戏,如果共有
- 第一轮编号为
的选手进行一次对局,编号为 的选手进行一次对局,以此类推,编号为 的选手进行一次对局。 - 第二轮在只保留第一轮的胜者的前提下,相邻的两位依次进行一场对局。
- 以此类推,第
轮在只保留第 轮的 位胜者的前提下,前两位、后两位分别进行对局,也就是所谓的半决赛。 - 第
轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后,小 S 将比赛的规则设置为了擂台赛。具体而言,每位选手都有一个能力值
现在,小 S 先后陆续收到了
形式化地,设
当然小 S 觉得这个问题还是太简单了,所以他给了你
输入格式
本题的测试点包含有多组测试数据。 但不同测试数据只是通过修改
输入的第一行包含两个正整数
输入的第二行包含
输入的第三行包含
设
注意,由于询问只是将人数凑齐到
接下来一行包含一个正整数
接下来共
输出格式
共输出
样例 #1
样例输入 #1
5 5 0 0 0 0 0 5 4 1 2 3 1001 10 1 4 2 1 0 0 1 2 1 0 0 2 3 1 2 2 0 1
样例输出 #1
5 19 7 1
提示
【样例 1 解释】
共有
- 对于长度为
的前缀,由于只有 号一个人,因此答案为 。 - 对于长度为
的前缀,由于 个人已经是 的幂次,因此不需要进行扩充。根据抽签 可知 号为擂主,由于 ,因此 号获胜,答案为 。 - 对于长度为
的前缀,首先 号、 号比赛是 号获胜(因为 ,故 号为擂主, ),然后虽然 号能力值还不知道,但 号、 号比赛一定是 号获胜(因为 ,故 号为擂主, ),而决赛 号、 号谁获胜都有可能(因为 ,故 号为擂主,如果 则 号获胜, 则 号获胜)。综上所述,答案为 。 - 对于长度为
的前缀,我们根据上一条的分析得知,由于 ,所以决赛获胜的是 号。 - 对于长度为
的前缀,可以证明,可能获胜的选手包括 号、 号、 号,答案为 。
因此,该组测试数据的答案为
【样例 2】
见选手目录下的 arena/arena2.in 与 arena/arena2.ans。
这组样例满足特殊性质 A。
【样例 3】
见选手目录下的 arena/arena3.in 与 arena/arena3.ans。
这组样例满足特殊性质 B。
【样例 4】
见选手目录下的 arena/arena4.in 与 arena/arena4.ans。
【样例 5】
见选手目录下的 arena/arena5.in 与 arena/arena5.ans。
【数据范围】
对于所有测试数据,保证:
测试点 | 特殊性质 A | 特殊性质 B | ||
---|---|---|---|---|
否 | 否 | |||
是 | 否 | |||
否 | 是 | |||
否 | 否 | |||
是 | 否 | |||
否 | 是 | |||
否 | 否 | |||
否 | 否 | |||
否 | 否 | |||
否 | 否 | |||
否 | 否 |
特殊性质 A:保证询问的
特殊性质 B:保证所有的
时间限制:
空间限制: