#3542. DZY Loves March

题目描述

在一片m*m的地上．驻扎着n个军队,编号依次为1~n,第i个军队的位置可用二元组(xi,yi)表示，可能有多个军队驻扎在同一个位置。

接下来有t个时刻，每个时刻会发生下列两种事件之一：

(1)第x个军队向一个方向（向上(U)向下(D)向左(L)向右(R)）移动了d个单位：

(2)第x个军队需要集结和它在同一行或同一列的且编号在[l,r]的军队，也就是说，这些军队需要赶到第x个军队的驻地。

定义第i个军队赶到第j个军队所需的花费为cost(i,j)=(xi-xj)^2+(yi-yj)^2

请你输出每次集结时，所有被集结的军队的花费之和，对10^9+7取模。

输入格式

第一行，两个数n和M。
描下来r一行，每行两个数xi,yi
下一行，一个数t。
描下来t行，每行的格式为下列两种格式之一
(l)S x d,其中S∈{U,L,D,R}，代表第一种事：
(2)Q x L R，代表第二种事件。
为了体现在线询问,每次你读进x'后，真正的x=x' xor lastans,其中lastans是上一次答案对10^9+7取模后的结果，一开始lastans=0

输出格式

对于每一个Q事件，输出一个答案，对10^9+7取模

样例

样例输入

【样例输入】  

5 3  

1 2  

2 2  

3 2  

2 1  

2 3  

7  

Q 2 1 5  

Q 6 3 4  

D 1 1  

Q 0 1 5  

Q 7 1 5  

L 5 1  

Q 4 1 5  

样例输出

4  

2  

3  

6  

4  

【样例解释】  

解密后的输入：  

Q 2 1 5  

Q 2 3 4  

D 3 1  

Q 2 1 5  

Q 4 1 5  

L 3 1  

Q 2 1 5  

数据范围与提示

.jpg)

样例还看不懂就看下图

【数据范围】

n≤100000，m≤10^18。保证军队在移动过程中不会超出边界。

每个军队集结后会回到原来的驻地