문제

구름이가 사는 마을에는 번 집부터 번 집까지 총 개의 집이 순서대로 세워져 있다. 마을의 땅 높이는 제각각이어서, 번째 집의 땅 높이는 이다. 땅 높이의 기준은 해수면이기 때문에, 해수면보다 낮은 위치에 집이 있다면 높이가 음수일 수도 있다.

장마가 시작되면 일 동안 멈추지 않고 비가 온다. 장마가 시작된 지 일이 되는 날에는 번 집이 있는 위치부터 번 집이 있는 위치까지 비가 내린다. 어떤 집에 비가 내리면 그 집에 쌓인 물의 높이가 만큼 증가한다. 한 번 쌓인 물은 배수 시스템이 작동하기 전까지는 빠지지 않는다.

배수 시스템은 장마가 시작된 지 의 배수가 되는 날마다, 비가 내리고 난 뒤 작동한다. 배수 시스템은 작동 날짜를 기준으로 일 이내에 비가 내린 위치에서만 작동한다. 예를 들어, 장마가 시작되고 일째에 작동하는 배수 시스템은 일 째에 비가 내린 위치에서만 작동한다. 배수 시스템이 작동하면 그 집에 쌓인 물의 높이가 만큼 감소한다.

장마가 지나간 뒤, 마을의 모든 땅 높이는 그 땅에 쌓였던 물의 높이만큼 증가한다. 구름이는 번 집부터 번 집까지의 땅 높이를 다시 조사하려고 한다. 구름이를 도와 변한 땅 높이를 구해보자.

입력

첫째 줄에 집의 개수 과 장마 기간 이 공백을 두고 주어진다.
둘째 줄에 마을의 땅 높이 이 공백을 두고 주어진다.
다음 개의 줄에는 가 공백을 두고 주어진다. 장마가 시작된 지 일이 되는 날에는 번 집이 있는 위치부터 번 집이 있는 위치까지 비가 내렸다는 의미이다.

• 
• 
  
• 
• 
  
• 입력에서 주어지는 모든 수는 정수이다.

출력

장마가 끝난 뒤, 번 집부터 번 집까지의 땅 높이를 한 줄에 하나씩 출력한다.