순환선의 안내 열차

문제

어느 지하철 순환선에는 N개의 역이 있다. 역에는 운행 방향을 따라 1번부터 N번까지 번호가 붙어 있다. 열차는 1번 역 다음에 2번 역을 방문하고, 같은 방식으로 번호가 증가하는 방향으로 이동한다. N번 역 다음에 방문하는 역은 다시 1번 역이다. 반대 방향으로 이동하는 경우는 없다. 각 역에는 안내 열차를 기다리는 승객이 있다. 안내 열차는 일반 열차가 운행하기 전에 대기 승객을 모두 태워 이동시키는 특별 열차다. 이번 운행에서는 S번 역을 첫 번째 방문 역으로 정하고, 그 역부터 운행 방향을 따라 정확히 K개의 역을 방문한다. S번 역에 도착하는 것도 한 번의 방문으로 센다. 따라서 K가 1이면 S번 역만 방문하고, K가 0이면 어느 역도 방문하지 않는다. 열차가 어떤 역을 방문하면 그 역에서 기다리던 승객이 모두 탑승하며, 그 역의 대기 승객 수는 0이 된다. 열차의 수용 인원에는 제한이 없다. 이번 운행 중에는 새로운 승객이 역에 도착하지 않고, 열차에 탄 승객이 역으로 돌아오는 일도 없다. 방문하지 않은 역의 대기 승객 수는 처음 주어진 값과 같다. K는 N 이하이므로 이번 운행에서 같은 역을 두 번 방문하지 않는다. 특히 K가 N이면 출발 위치에 관계없이 모든 역을 정확히 한 번씩 방문한다. N이 1인 경우에도 같은 규칙을 적용한다. 승객이 처음부터 없었던 역을 방문해도 방문 횟수에는 포함한다. 운행 기록을 작성하기 위해 이번에 열차에 탑승한 승객의 총수를 구하려 한다. 또한 운행이 끝난 직후 각 역에 남은 대기 승객 수를 1번 역부터 N번 역까지 번호순으로 기록하려 한다. 출력할 역의 순서는 열차가 방문한 순서와 관계없이 항상 역 번호순이다.

입력

첫째 줄에 정수 N, S, K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 100,000, 1 ≤ S ≤ N, 0 ≤ K ≤ N이다.
둘째 줄에 1번 역부터 N번 역까지의 초기 대기 승객 수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다. 모든 Aᵢ는 0 이상 9 이하의 정수이다.

출력

첫째 줄에 이번 운행에서 탑승한 승객의 총수를 정수로 출력한다. 방문한 역이 없거나 탑승한 승객이 없으면 0을 출력한다. 둘째 줄에 운행 종료 후 각 역의 대기 승객 수를 1번 역부터 N번 역까지 공백으로 구분하여 출력한다.

7 6 4
3 0 4 1 2 5 6

14
0 0 4 1 2 0 0

1 1 1
0

0
0

4 3 0
2 7 1 0

0
2 7 1 0

출처: Devin.KR 자체 제작