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):

1. 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 at K, the drop settles on the lowest such cell; if several tie for lowest, it settles on the one closest to K.
2. Otherwise try to flow right by the mirror-image rule.
3. 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

7 4 3
2 1 1 2 1 2 2

2 2 2 3 2 2 2

3 2 1
1 2 1

2 2 2