An elevation profile is an array of n non-negative integer heights. You pour V units of water, one drop at a time, all above index K. Each drop settles using this rule (heights already include any water that has settled):
- First try to flow left: starting at
K, walk left across cells whose surface level does not rise (each next cell to the left has level<=the current cell). Among the cells reachable this way, if some cell is strictly lower than the level atK, the drop settles on the lowest such cell; if several tie for lowest, it settles on the one closest toK. - Otherwise try to flow right by the mirror-image rule.
- Otherwise the drop settles exactly at
K.
Settling a drop raises that cell's level by 1. After all V drops, report the final levels.
Input format
Line 1: three integers n, V, K.
Line 2: n space-separated integers, the initial heights.
Output format
A single line: n space-separated integers, the final levels.
Constraints
- 1 <= n <= 100000
- 0 <= V <= 100000
- 0 <= K <= n-1
- 0 <= each height <= 1000000