#CW21. 传球(ball)

传球(ball)

题目描述

有 nn 个人在玩游戏。

第 ii 个人持有 aia_i 个球,他每轮游戏中会传球给第 sis_i 个人(可能出现 si=is_i=i)。

具体地,进行了 kk 轮游戏,每轮游戏中,所有人同时将自己手上的球传给自己要传的人(即第 sis_i 个人),并接住所有传给自己的球。

回答两个问题:

  • kk 轮后,持有球数量最多的人持有多少个球?
  • kk 轮后,谁持有的球数量最多?

对于第二问,若有多个答案,从小到大依次输出之。

一部分测试点只要求你回答第一问。

输入格式

第一行,三个正整数 n,k,typen,k,type。type∈[0,1]type \in [0,1] 表示你需要回答的问题,具体见输出格式。

第二行,nn 个正整数 aia_i。

第三行,nn 个正整数 sis_i。

输出格式

当 type=0type=0 时,只需要输出一行一个正整数:持有球数量最多的人持有的球数。

当 type=1type=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≤1051 \le n \le 10^5,1≤k≤1091 \le k \le 10^9,1≤ai≤1031 \le a_i \le 10^3,1≤si≤n1 \le s_i \le n,type∈[0,1]type \in [0,1]。

测试点 n≤n \le k≤k \le type=type= 特殊性质
1∼61 \sim 6 10001000 11 无
7∼97 \sim 9 10510^5 10910^9 00 sis_i 是一个 [1,n][1,n] 的排列
10∼1210 \sim 12 11
13∼1613 \sim 16 00 无
17∼2017 \sim 20 11