#3533. [Sdoi2014]向量集

题目描述

维护一个向量集合，在线支持以下操作：
"A x y (|x|，|y| < =10^8)"：加入向量(x，y);
" Q x y l r (|x|，|y| < =10^8，1 < =L < =R < =T，其中T为已经加入的向量个数)询问第L个到第R个加入的向量与向量(x，y)的点积的最大值。
集合初始时为空。

输入格式

输入的第一行包含整数N和字符s，分别表示操作数和数据类别；  
接下来N行，每行一个操作，格式如上所述。  
请注意s≠'E'时，输入中的所有整数都经过了加密。你可以使用以下程序  

得到原始输入：
inline int decode (int x long long lastans) {
return x ^ (lastans & Ox7fffffff);
}
function decode
begin
其中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

数据范围与提示

1 < =N < =4×10^5

新加数据一组..2015.315