DZY Loves March

时间限制:10s      空间限制:256MB

题目描述

在一片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

提示

样例还看不懂就看下图


【数据范围】
n≤100000,m≤10^18。保证军队在移动过程中不会超出边界。
每个军队集结后会回到原来的驻地


题目来源

By Dzy