[SDOI2014] 向量集

维护一个向量集合，在线支持以下操作： - `A x y`（$|x|,|y| \le 10^8$）：加入向量 $(x,y)$； - `Q x y l r`（$|x|,|y| \le 10^8$，$1 \le l \le r \le t$，其中 $t$ 为已经加入的向量个数）：询问第 $l$ 个到第 $r$ 个加入的向量与向量 $(x,y)$ 的点积的最大值。 集合初始时为空。

输入的第一行包含整数 $N(1 \le N \le 4 \times 10^5)$ 和字符 $s$，分别表示操作数和数据类别； 接下来 $N$ 行，每行一个操作，格式如上所述。 请注意 $s$ 不为 `E` 时，输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入： ``` inline int decode(int x, long long lastans) { return x ^ (lastans & 0x7fffffff); } ``` 其中 `x` 为程序读入的数，`lastans` 为之前最后一次询问的答案。在第一次询问之前，`lastans` 为 $0$。注：向量 $(x, y)$ 和 $(z, w)$ 的点积定义为 $xz+yw$。

对每个 `Q` 操作，输出一个整数表示答案。

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

样例解释：解密之后的输入为 ``` 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 ```