Implement Softmax

Problem: Implement Softmax

Do not rely on any third-party libraries.

For an array x containing n real numbers, compute its softmax values according to:

softmax(x_i) = exp(x_i) / sum(exp(x_j)), j = 0..n-1

Use the following mathematically equivalent form to prevent overflow:

softmax(x_i) = exp(x_i - max(x)) / sum(exp(x_j - max(x)))

Display each resulting value rounded to 6 digits after the decimal point.

Input Format

n
x_0 x_1... x_{n-1}

Output Format

Output a single line with n decimal values.

Constraints

• 1 <= n <= 1000
• -1000 <= x_i <= 1000

Example

Input:

3
1 2 3

Output:

0.090031 0.244728 0.665241

The three output values are the softmax results for the corresponding input values, rounded to six decimal places.