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

• "A $x$ $y$ ($|x|, |y| \le 10^8$)": Add 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 added)": Query the maximum dot product$^1$ between the vectors added from the $l$-th to the $r$-th and the vector $(x, y)$.

The set is initially empty.

Input

The first line contains an integer $N$ and a character $s$, representing the number of operations and the data category, respectively.

The next $N$ lines each contain an operation, formatted as described above.

Please note that when $s = \text{'E'}$, all integers in the input are encrypted. You can use the following code to obtain the original input:

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

function decode (x : longint; lastans : int64) : longint;
begin
    decode := x xor (lastans and $7fffffff);
end;

Where $x$ is the number read by the program, and $lastans$ is the answer to the last query. Before the first query, $lastans = 0$.

Output

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

Examples

Input 1

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

Output 1

13
17
17

Note

The decrypted 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

Constraints

$^1$ The dot product of vectors $(x, y)$ and $(z, w)$ is defined as $xz + yw$.