\(n\) học sinh đứng thành vòng tròn. Học sinh \(i\) đang có \(a_i\) quả bóng và chọn một người mình thích \(s_i\) (có thể là chính mình). Trò chơi có \(k\) lượt; trong mỗi lượt, mọi người đồng thời ném toàn bộ bóng cho người mình thích và luôn bắt được toàn bộ bóng gửi đến.

Sau \(k\) lượt, hãy xác định số bóng lớn nhất mà một học sinh có và tất cả chỉ số học sinh đạt số bóng đó, theo thứ tự tăng dần.

Dữ liệu vào

Dòng đầu chứa \(n,k\) (\(1\le n\le10^5\), \(1\le k\le10^9\)). Dòng hai chứa \(n\) số \(a_i\) (\(1\le a_i\le1000\)). Dòng ba chứa \(n\) số \(s_i\) (\(1\le s_i\le n\)).

Dữ liệu ra

Dòng đầu in số bóng lớn nhất. Dòng hai in các chỉ số học sinh đạt giá trị đó theo thứ tự tăng dần.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(14\) điểm: \(n,k\le1000\).
2. \(26\) điểm: dãy \(s\) là hoán vị.
3. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

2 1
5 6
2 1

6
1

4 2
5 5 5 5
1 2 1 1

15
1

4 10000000
1 2 3 4
2 1 4 3

4
4

Nguồn

COCI 2025/2026 - Vòng 1, bài Krugomet.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.