B. Boulevard of Broken Cars
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The government of Ajobdesh launched an ambitious project to build a national highway, spanning the entire country, costing billions of dollars. But the construction company decided that high-quality bitumen was optional and spent most of the budget on million dollar pillows. As a result, the highway is riddled with potholes and cars break down all the time. As stranded vehicles become a common sight along the highway, the tow truck business is booming.

There are $$$n$$$ tow truck companies operating on the highway. The $$$i^{th}$$$ company operates a truck which is positioned at $$$x_i$$$ and moves at speed $$$v_i$$$. If a car breaks down at position $$$y$$$, the time required to reach it for the $$$i^{th}$$$ truck is $$$\dfrac{|y-x_i|}{v_i}$$$. You want to know the minimum response time for a tow truck if a car breaks down.

You must answer $$$q$$$ queries. Each query will be one of the following two types.

  • + x v — A new company opens with a truck at position $$$x$$$ with speed $$$v$$$.
  • ? y — A car breaks down at position $$$y$$$. You have to find the minimum time taken by any tow truck to reach the car.

Note that the queries of the second type are independent, you can assume that all tow trucks are at their initial positions before each query.

Input

The first line contains $$$T\ (1 \leq T\leq 10^4)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n\ (1 \leq n \leq 10^5)$$$ — the number of tow truck companies. Each of the following $$$n$$$ lines contain two integers $$$x_i\ (-10^{14} \leq x_i \leq 10^{14})$$$ and $$$v_i\ (1 \leq v_i\leq 10^9)$$$.

The next line contains $$$q\ (1 \leq q \leq 3 \cdot 10^5)$$$ — the number of queries. Each of the following $$$q$$$ lines contain the description of the queries in the format described above $$$(-10^{14} \leq x, y \leq 10^{14}\ and\ 1 \leq v\leq 10^9)$$$.

It is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$10^5$$$ and the sum of $$$q$$$ over all cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each query of the second type, output a single real number in a line — the minimum response time. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then your answer is accepted, if and only if $$$\dfrac{|a-b|}{max(1, b)} \leq 10^{-6}$$$.

Example
Input
2
1
0 1
3
? 1
+ 2 2
? 1
2
0 2
2 2
8
? 1
? -1
+ 3 5
? 1
? -1
+ 1 9
? 1
? -1
Output
1.000000000000000
0.500000000000000
0.500000000000000
0.500000000000000
0.400000000000000
0.500000000000000
0.000000000000000
0.222222222222222
Note

In the first case, there is initially only one truck at $$$x=0$$$ with speed $$$v = 1$$$.

  • Query 1: A car breaks down at $$$y = 1$$$. It takes $$$1$$$ second for the only truck to reach it.
  • Query 2: A new truck appears at $$$x = 2$$$ with speed $$$v = 2$$$.
  • Query 3: A car breaks down at $$$y = 1$$$. The initial truck at $$$x=0$$$ can reach it in $$$1$$$ second, but the new truck at $$$x=2$$$ can reach it in $$$0.5$$$ seconds.