向量集 ### 题目描述 维护一个向量集合，在线支持以下操作： - "$A\ x\ y (|x|，|y| \leq 10^8)$"：加入向量 $(x，y)$; - "$Q\ x\ y\ l\ r (|x|，|y| \leq 10^8，1 \leq L \leq R\leq T，其中T为已经加入的向量个数)$：询问第 $L$ 个到第 $R$ 个加入的向量与向量 $(x，y)$ 的点积的最大值。 集合初始时为空。 ### 输入描述 输入的第一行包含整数 $N$ 和字符 $s$，分别表示操作数和数据类别。 接下来 $N$ 行，每行一个操作，格式如上所述。 请注意 $s≠E$时，输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入： ```cpp inline int decode (int x long long lastans) { return x ^ (lastans & Ox7fffffff); } ``` ```txt 其中 x 为程序读入的数，lastans 为之前最后一次询问的答案。在第一次询问之前，lastans=0。注：向量(x，y)和(z，W)的点积定义为xz+yw。 ``` 其中，$1 \leq N \leq 4 \times 10^5$。 ### 输出描述 对每个 $Q$ 操作，输出一个整数表示答案。 ### 输入输出样例 #### 示例 1 >输入 ```txt 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 ``` >输出 ```txt 13 17 17 ```