Statistics from a 256-Bucket Frequency Array

Problem: Compute Statistics from a 256-Bucket Frequency Array

You are given a frequency array count of length 256, where count[i] represents how many times value i appears in the original data. The possible values are fixed to 0..255.

Compute the following statistics of the original data:

1. minimum
2. maximum
3. mean
4. median
5. mode
6. population standard deviation

If there are multiple modes, return the smallest value.

The standard deviation is defined as:

[ std = \sqrt{\frac{\sum count[i] \times (i - mean)^2}{N}} ]

where N = sum(count).

Input Format

For testing purposes, stdin uses a sparse representation:

• The first line contains an integer m, the number of non-zero buckets.
• The next m lines each contain two integers value count, meaning value appears count times.

This is equivalent to a frequency array of length 256, with all omitted buckets having frequency 0.

Output Format

Print one line:

minimum maximum mean median mode stddev

where:

• minimum, maximum, and mode are integers;
• mean, median, and stddev are printed with exactly 5 digits after the decimal point.

Constraints

• 0 <= value <= 255
• count > 0
• 1 <= m <= 256
• There is at least one data point: sum(count) > 0
• The total frequency can be large, so do not expand the original data array.

Example

Input

3
0 2
1 5
2 8

Output

0 2 1.40000 2.00000 2 0.71181