Omkar and Landslide

Omkar is standing at the foot of Celeste mountain. The summit is n meters away from him, and he can see all of the mountains up to the summit, so for all 1 ≤ j ≤ n he knows that the height of the mountain at the point j meters away from himself is h_j meters. It turns out that for all j satisfying 1 ≤ j ≤ n - 1, h_j < h_{j + 1} (meaning that heights are strictly increasing).

Suddenly, a landslide occurs! While the landslide is occurring, the following occurs: every minute, if h_j + 2 ≤ h_{j + 1}, then one square meter of dirt will slide from position j + 1 to position j, so that h_{j + 1} is decreased by 1 and h_j is increased by 1. These changes occur simultaneously, so for example, if h_j + 2 ≤ h_{j + 1} and h_{j + 1} + 2 ≤ h_{j + 2} for some j, then h_j will be increased by 1, h_{j + 2} will be decreased by 1, and h_{j + 1} will be both increased and decreased by 1, meaning that in effect h_{j + 1} is unchanged during that minute.

The landslide ends when there is no j such that h_j + 2 ≤ h_{j + 1}. Help Omkar figure out what the values of h_1, ..., h_n will be after the landslide ends. It can be proven that under the given constraints, the landslide will always end in finitely many minutes.

Note that because of the large amount of input, it is recommended that your code uses fast IO.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^6).

The second line contains n integers h_1, h_2, ..., h_n satisfying 0 ≤ h_1 < h_2 < ... < h_n ≤ 10^{12} — the heights.

Output

Output n integers, where the j-th integer is the value of h_j after the landslide has stopped.

Example

Input

4 2 6 7 8

Output

5 5 6 7

Note

Initially, the mountain has heights 2, 6, 7, 8.

In the first minute, we have 2 + 2 ≤ 6, so 2 increases to 3 and 6 decreases to 5, leaving 3, 5, 7, 8.

In the second minute, we have 3 + 2 ≤ 5 and 5 + 2 ≤ 7, so 3 increases to 4, 5 is unchanged, and 7 decreases to 6, leaving 4, 5, 6, 8.

In the third minute, we have 6 + 2 ≤ 8, so 6 increases to 7 and 8 decreases to 7, leaving 4, 5, 7, 7.

In the fourth minute, we have 5 + 2 ≤ 7, so 5 increases to 6 and 7 decreases to 6, leaving 4, 6, 6, 7.

In the fifth minute, we have 4 + 2 ≤ 6, so 4 increases to 5 and 6 decreases to 5, leaving 5, 5, 6, 7.

In the sixth minute, nothing else can change so the landslide stops and our answer is 5, 5, 6, 7.

inputFormat

input, it is recommended that your code uses fast IO.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^6).

The second line contains n integers h_1, h_2, ..., h_n satisfying 0 ≤ h_1 < h_2 < ... < h_n ≤ 10^{12} — the heights.

outputFormat

Output

Output n integers, where the j-th integer is the value of h_j after the landslide has stopped.

Example

Input

4 2 6 7 8

Output

5 5 6 7

Note

Initially, the mountain has heights 2, 6, 7, 8.

In the first minute, we have 2 + 2 ≤ 6, so 2 increases to 3 and 6 decreases to 5, leaving 3, 5, 7, 8.

In the second minute, we have 3 + 2 ≤ 5 and 5 + 2 ≤ 7, so 3 increases to 4, 5 is unchanged, and 7 decreases to 6, leaving 4, 5, 6, 8.

In the third minute, we have 6 + 2 ≤ 8, so 6 increases to 7 and 8 decreases to 7, leaving 4, 5, 7, 7.

In the fourth minute, we have 5 + 2 ≤ 7, so 5 increases to 6 and 7 decreases to 6, leaving 4, 6, 6, 7.

In the fifth minute, we have 4 + 2 ≤ 6, so 4 increases to 5 and 6 decreases to 5, leaving 5, 5, 6, 7.

In the sixth minute, nothing else can change so the landslide stops and our answer is 5, 5, 6, 7.

样例

4
2 6 7 8

5 5 6 7