Online Vector Dot Product Query

You are given an initially empty collection of 2D vectors. You need to support the following operations online:

• A x y (with \(|x|,|y| \le 10^8\)): Add the vector \((x,y)\) to the collection.
• Q x y l r (with \(|x|,|y| \le 10^8\) and \(1 \le l \le r \le t\), where \(t\) is the current number of added vectors): Query the maximum dot product between the given vector \((x,y)\) and any vector among the \(l\)-th to \(r\)-th inserted vectors.

Note: The vectors are 1-indexed in the order they are added.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the total number of operations.

Each of the next \(n\) lines contains an operation in one of the following formats:

• A x y
• Q x y l r

It is guaranteed that for every query operation, \(1 \le l \le r \le t\) holds, where \(t\) is the number of add operations performed so far.

outputFormat

For each query operation, output a single line containing the maximum dot product between the query vector and one of the vectors in the specified range.

sample

6
A 1 2
A 2 3
Q 1 1 1 2
A -1 4
Q 3 -2 2 3
Q 0 2 1 3

5
-4
8