Database Query for Class Exam Scores

Yellow_sword needs a simple database to maintain the average evaluation values of class exams. Each student's midterm exam has been transformed into an evaluation score, an integer in the range \( [1, 100] \), which assesses the overall ability of that student.

For each of \( n \) classes, you are given two numbers: the class average evaluation value and the number of students in that class. Because both Yellow_sword and his assistant are lazy, they assume every student in a class has exactly the class average evaluation value.

You need to process \( q \) queries. Each query specifies a contiguous range of classes \( [l, r] \) and asks you to compute the following:

1. The overall average evaluation value of all students in classes \( l \) through \( r \). This is computed as \( \frac{\sum_{i=l}^{r} (a_i \times c_i)}{\sum_{i=l}^{r} c_i} \), where \( a_i \) is the average evaluation of class \( i \) and \( c_i \) is its student count.
2. The mode of the evaluation values over these classes (i.e. the evaluation value that occurs most frequently among all students). In case of a tie, choose the smallest value.
3. The range of evaluation values, defined as the difference between the maximum and minimum evaluation values among the classes in the range.

Output the results for each query on a separate line. The average should be printed as a floating-point number with 6 decimal places, followed by the mode and the range, separated by spaces.

inputFormat

The input begins with two integers \( n \) and \( q \) (the number of classes and the number of queries, respectively).

The next \( n \) lines each contain two integers \( a_i \) and \( c_i \), where \( a_i \) is the class average evaluation value and \( c_i \) is the number of students in the class.

Each of the following \( q \) lines contains two integers \( l \) and \( r \) (1-indexed), representing a query over the continuous range of classes from \( l \) to \( r \).

outputFormat

For each query, output three values separated by spaces:

1. The overall average evaluation value of the students in the queried classes, printed as a floating-point number with 6 decimal places.
2. The mode of the evaluation values among these students (if there are several with the same frequency, output the smallest one).
3. The range of evaluation values (i.e. the difference between the maximum and the minimum evaluation value).

Each query's result should be printed on a new line.

sample

5 3
60 10
70 10
80 5
70 5
90 10
1 3
2 5
1 5

68.000000 60 20
78.333333 70 20
73.750000 70 30