D. Steepness
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ poles placed on a line, evenly spaced, with height $$$a_1,a_2,..,a_n$$$. Culver defines the steepness from pole $$$i$$$ to pole $$$j$$$ ($$$i\ne j$$$) being $$$$$$\left|\frac{a_i-a_j}{i-j}\right|$$$$$$ He wants to know the maximum and minimum possible steepness among all valid choices of pole $$$i$$$ and pole $$$j$$$.

Additionally, since Culver will occasionally replace a pole with another one possibly with a different length, he would like to know the new maximum and minimum steepness after each replacement. As Culver does not want to do the calculations himself, please help him.

Input

The first line contains an integer $$$t$$$ ($$$1\le t\le 10^4$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2\le n\le 10^5$$$), the number of poles.

The next line of each test case contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1\le a_i\le 10^9$$$), the height of each pole.

The next line of each test case contains an integer $$$m$$$ ($$$1\le m\le 10^5$$$), the number of replacements.

The $$$k$$$-th line of the next $$$m$$$ lines contains two integers $$$x_k,y_k$$$ ($$$1\le x_k\le n$$$, $$$1\le y_k\le 10^9$$$), meaning that in the $$$k$$$-th replacement, Culver changes the height of pole $$$x_k$$$ to $$$y_k$$$ i.e. the value of $$$a_{x_k}$$$ becomes $$$y_k$$$.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$10^5$$$.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$n = 2$$$.

Tests $$$2-3$$$ satisfy $$$n \le 10$$$.

Test $$$4$$$ satisfies $$$m \le 10$$$.

Tests $$$5-20$$$ satisfy no additional constraints.

Output

For each test, output $$$m+1$$$ lines.

The first line should contain two real numbers $$$max_0,min_0$$$, the maximum and minimum steepness at first.

Each line on the next $$$m$$$ lines contain two real numbers $$$max_k,min_k$$$, the maximum and minimum steepness after the $$$k$$$-th replacement.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Example
Input
4
5
1 3 4 5 2
3
2 1
2 3
5 6
6
1 1 1 1 1 1
6
1 1
2 2
3 3
4 4
5 5
6 6
4
6 9 4 2
4
4 6
2 10
1 1
3 5
2
1 1
3
1 1
2 2
1 5
Output
3.000000 0.250000
3.000000 0.000000
3.000000 0.250000
2.000000 1.000000
0.000000 0.000000
0.000000 0.000000
1.000000 0.000000
2.000000 0.000000
3.000000 0.000000
4.000000 0.000000
1.000000 1.000000
5.000000 1.000000
5.000000 0.000000
6.000000 0.000000
9.000000 1.500000
9.000000 1.000000
0.000000 0.000000
0.000000 0.000000
1.000000 1.000000
3.000000 3.000000
Note

In the first test case:

Initially, the heights of the poles are $$$1,3,4,5,2$$$ respectively. Then we can get the maximum steepness by choosing pole $$$4$$$ and pole $$$5$$$ which gives a steepness of $$$\left|\frac{5-2}{4-5}\right|=3$$$. We can get the minimum steepness by choosing pole $$$1$$$ and pole $$$5$$$ which gives a steepness of $$$\left|\frac{1-2}{1-5}\right|=0.25$$$.

After the first replacement, the height of the poles become $$$1,1,4,5,2$$$ respectively. Then we can get the maximum steepness by choosing pole $$$4$$$ and pole $$$5$$$ which gives a steepness of $$$\left|\frac{5-2}{4-5}\right|=3$$$. We can get the minimum steepness by choosing pole $$$1$$$ and pole $$$2$$$ which gives a steepness of $$$\left|\frac{1-1}{1-2}\right|=0$$$.

After the second replacement, the height of the poles become $$$1,3,4,5,2$$$ respectively. which is the same as the initial configuration of poles, so the maximum and minimum steepness are $$$3$$$ and $$$0.25$$$ respectively.

After the third replacement, the height of the poles become $$$1,3,4,5,6$$$ respectively. Then we can get the maximum steepness by choosing pole $$$1$$$ and pole $$$2$$$ which gives a steepness of $$$\left|\frac{1-3}{1-2}\right|=2$$$. We can get the minimum steepness by choosing pole $$$2$$$ and pole $$$3$$$ which gives a steepness of $$$\left|\frac{3-4}{2-3}\right|=1$$$.