[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); } ``` 其中x为程序读入的数,lastans为之前最后一次询问的答案。在第一次询问之前,lastans=0。注:向量(x,y)和(z,W)的点积定义为xz+yw。

输出格式


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

输入输出样例

输入样例 #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

输出样例 #1

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