题目描述
有 n 个人在玩游戏。
第 i 个人持有 ai 个球,他每轮游戏中会传球给第 si 个人(可能出现 si=i)。
具体地,进行了 k 轮游戏,每轮游戏中,所有人同时将自己手上的球传给自己要传的人(即第 si 个人),并接住所有传给自己的球。
回答两个问题:
- k 轮后,持有球数量最多的人持有多少个球?
- k 轮后,谁持有的球数量最多?
对于第二问,若有多个答案,从小到大依次输出之。
一部分测试点只要求你回答第一问。
输入格式
第一行,三个正整数 n,k,type。type∈[0,1] 表示你需要回答的问题,具体见输出格式。
第二行,n 个正整数 ai。
第三行,n 个正整数 si。
输出格式
当 type=0 时,只需要输出一行一个正整数:持有球数量最多的人持有的球数。
当 type=1 时,需要再输出一行若干个正整数,表示持有球数量最多的人,按照编号从小到大排序。
样例 1 输入
2 1 1
5 6
2 1
样例 1 输出
6
1
样例 2 输入
4 10000000 1
1 2 3 4
2 1 4 3
样例 2 输出
4
4
数据范围
对于所有测试数据,保证:1≤n≤105,1≤k≤109,1≤ai≤103,1≤si≤n,type∈[0,1]。
| 测试点 |
n≤ |
k≤ |
type= |
特殊性质 |
| 1∼6 |
1000 |
1 |
无 |
| 7∼9 |
105 |
109 |
0 |
si 是一个 [1,n] 的排列 |
| 10∼12 |
1 |
| 13∼16 |
0 |
无 |
| 17∼20 |
1 |