Description

Maintain a set of vectors and support the following operations online:

• A x y ($|x|, |y| \le 10^8$): insert the vector $(x, y)$.
• Q x y l r ($|x|, |y| \le 10^8$, $1 \le l \le r \le t$, where $t$ is the number of vectors already inserted): query the maximum dot product between the vector $(x, y)$ and each of the vectors from the $l$-th to the $r$-th inserted.

Initially, the set is empty.

Input Format

The first line contains an integer $N (1 \le N \le 4 \times 10^5)$ and a character $s$, representing the number of operations and the data category, respectively.

Then follow $N$ lines, each containing one operation in the format described above.

Note that when $s$ is not E, all integers in the input are encrypted. You can use the following program to obtain the original input:

inline int decode(int x, long long lastans) {    
    return x ^ (lastans & 0x7fffffff);
}

Here, $x$ is the number read by your program, and lastans is the answer to the most recent previous query. Before the first query, lastans is $0$. Note: the dot product of vectors $(x, y)$ and $(z, w)$ is defined as $xz + yw$.

Output Format

For each Q operation, output an integer representing the answer.

6 A
A 3 2
Q 1 5 1 1
A 15 14
A 12 9
Q 12 8 12 15
Q 21 18 19 18

13
17
17

Hint

Sample explanation: after decryption, the input is

    6 E
    A 3 2
    Q 1 5 1 1
    A 2 3
    A 1 4
    Q 1 5 1 2
    Q 4 3 2 3

Translated by ChatGPT 5