Background

As an old saying goes: “With spring breeze and success, the horse’s hooves are swift; in one day one can see all the flowers of Chang’an.”

Of course, in an exam it is impossible for everyone to be so lucky and successful, especially when encountering some “toxic” problem setters.

It is time for the monthly exam again, and the problems are set by Teacher xf again.

The last time Teacher xf’s problems were too “toxic”, and the average score was only a bit more than $40$. The students were very unhappy, since the average scores of other subjects were all above $80$.

Problem Description

This time, in order to avoid being sent razor blades by the students, xf came up with an idea: only publish the average of the average scores of all exam rooms. In this way, he can adjust the way students are assigned to exam rooms to make the average look higher. (Each exam room can hold an unlimited number of students.)

Also, not every student participates in every exam. Only students whose student IDs are in the interval $[l,r]$ will attend.

He wants to know, for each exam, after adjusting the exam rooms, the maximum possible value of the average of the average scores of all exam rooms.

Of course, students’ scores may also change because they study hard or slack off all day.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers. The $i$-th number $v_i$ represents the initial score of the $i$-th student.

The third line contains an integer $q$, meaning there are $q$ operations. The next $q$ lines each describe an operation, where the first number indicates the operation type.

If the operation is 1 p x, it means the score of the student with ID $p$ becomes $x$.

If the operation is 2 l r k, it means to split the students with IDs in $[l,r]$ into $k$ exam rooms, and you need to find the maximum possible value of the average of the average scores of these $k$ exam rooms.

Output Format

For each type $2$ operation, output one line. Round to exactly $3$ digits after the decimal point.

5
5 3 4 2 1
5
2 1 4 3
1 4 8
2 3 5 3
1 2 2
2 1 3 2

3.833
4.333
4.000

Hint

Sample Explanation

The first operation asks for the maximum possible value of the average of the average scores when splitting students with IDs in $[1, 4]$ into $3$ exam rooms. The optimal strategy is: $\{1\}$, $\{2, 4\}$, $\{3\}$. The average is $(5/1 +(3+2)/2 + 4/1)/3$.

The second operation changes the score of the student with ID $4$ to $8$.

The third operation asks for the maximum possible value of the average of the average scores when splitting students with IDs in $[3, 5]$ into $3$ exam rooms. The optimal strategy is: $\{3\}$, $\{4\}$, $\{5\}$.

The fourth operation changes the score of the student with ID $2$ to $2$.

The fifth operation asks for the maximum possible value of the average of the average scores when splitting students with IDs in $[1, 3]$ into $2$ exam rooms. The optimal strategy is: $\{1\}$, $\{2,3\}$.

Evaluation Case Scale and Assumptions

For all evaluation cases, $1\le n, q \le 200000$. At any time, each student’s score satisfies $v_i \le 10^9$, and $k \le r- l + 1$.

During evaluation, $20$ evaluation cases will be used to test your program. The limits for each evaluation case are as follows:

Lanqiao Cup 2019 National Contest A Group, Problem I.

Translated by ChatGPT 5