Một tuyến đường thẳng có các vị trí được biểu diễn bằng tọa độ. Ban đầu, trên đường có ~n~ xe cứu hộ. Xe thứ ~i~ đỗ tại tọa độ ~x_i~ và có vận tốc ~v_i~. Mỗi xe có thể chạy theo cả hai hướng với vận tốc của nó.

Khi nhận được tin có xe hỏng tại tọa độ ~y~, trung tâm điều phối muốn biết mất ít nhất bao lâu để một xe cứu hộ đến đó. Nếu xe cứu hộ đang đỗ tại ~x_i~, thời gian di chuyển của nó là ~\dfrac{|y-x_i|}{v_i}~.

Trung tâm xử lý ~q~ truy vấn theo thứ tự xuất hiện.

• + x v — Bổ sung một xe cứu hộ đỗ tại tọa độ ~x~ với vận tốc ~v~. Xe này có thể được chọn trong mọi truy vấn tiếp theo.
• ? y — Có xe hỏng tại tọa độ ~y~. Hãy tính thời gian ngắn nhất để một trong các xe cứu hộ hiện có đến vị trí đó.

Trong mỗi truy vấn ?, tất cả xe cứu hộ đều xuất phát từ vị trí đỗ đã khai báo. Việc trả lời truy vấn chỉ tính thời gian và không làm thay đổi vị trí đỗ của xe. Nhiều xe có thể đỗ cùng một tọa độ.

Input

• Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 10^4)~, là số bộ test.
• Dòng đầu tiên của mỗi test chứa số nguyên ~n~ ~(1 \le n \le 10^5)~, là số xe cứu hộ ban đầu.
• Mỗi dòng trong ~n~ dòng tiếp theo chứa hai số nguyên ~x_i~ và ~v_i~ ~(-10^{14} \le x_i \le 10^{14},\ 1 \le v_i \le 10^9)~, là tọa độ đỗ và vận tốc của xe thứ ~i~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 3 \cdot 10^5)~, là số truy vấn.
• Mỗi dòng trong ~q~ dòng tiếp theo chứa một truy vấn + x v hoặc ? y. Các tọa độ ~x~ và ~y~ là số nguyên trong đoạn ~[-10^{14},10^{14}]~. Vận tốc ~v~ là số nguyên thỏa mãn ~1 \le v \le 10^9~.

Tổng ~n~ qua tất cả các test không vượt quá ~10^5~. Tổng ~q~ qua tất cả các test không vượt quá ~3 \cdot 10^5~.

Output

Với mỗi truy vấn ?, in ra một dòng chứa một số thực là thời gian ngắn nhất để xe cứu hộ đến vị trí được hỏi. In các đáp án theo thứ tự truy vấn.

Gọi ~a~ là kết quả chương trình in ra và ~b~ là đáp án đúng. Kết quả được chấp nhận nếu ~\dfrac{|a-b|}{\max(1,b)} \le 10^{-6}~.

Subtask

Bạn nhận toàn bộ số điểm của một subtask nếu chương trình vượt qua tất cả các test thuộc subtask đó.

Sample Input 1

2
2
0 2
10 10
7
? 2
? 2
+ 2 1
? 2
? -2
+ -4 4
? -2
1
-5 3
4
? -4
? -5
+ 3 2
? 2

Sample Output 1

0.8000000000
0.8000000000
0.0000000000
1.0000000000
0.5000000000
0.3333333333
0.0000000000
0.5000000000

Giải thích

• Test thứ nhất. Trong hai truy vấn đầu, xe đỗ tại ~10~ đến vị trí ~2~ sau ~8/10 = 0.8~, nhanh hơn xe đỗ tại ~0~ cần ~2/2 = 1~. Sau khi bổ sung xe ngay tại ~2~, thời gian đến vị trí này bằng ~0~. Với vị trí ~-2~, thời gian tốt nhất ban đầu là ~2/2 = 1~. Khi bổ sung xe tại ~-4~ với vận tốc ~4~, thời gian giảm còn ~2/4 = 0.5~.
• Test thứ hai. Xe đỗ tại ~-5~ đến vị trí ~-4~ sau ~1/3~ đơn vị thời gian. Truy vấn tại ~-5~ có đáp án ~0~. Sau khi bổ sung xe tại ~3~ với vận tốc ~2~, xe này đến vị trí ~2~ sau ~1/2~ đơn vị thời gian.