题目描述

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

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

1. 第$x$个军队向一个方向（向上($U$)向下($D$)向左($L$)向右($R$)）移动了$d$个单位：
2. 第$x$个军队需要集结和它在同一行或同一列的且编号在$[l,r]$的军队，也就是说，这些军队需要赶到第$x$个军队的驻地。

定义第$i$个军队赶到第$j$个军队所需的花费为$cost(i,j)=(x_i-x_j)^2+(y_i-y_j)^2$

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

输入格式

第一行，两个数$n$和$m$。

接下来$r$行，每行两个数$x_i,y_i$

下一行，一个数$t$。

描下来$t$行，每行的格式为下列两种格式之一

1. S x d,其中$S\in\{U,L,D,R\}$，代表第一种事：
2. Q x L R，代表第二种事件。

为了体现在线询问,每次你读进$x'$后，真正的$x=x' \oplus \text{lastans}$,其中$\text{lastans}$是上一次答案对$10^9+7$取模后的结果，一开始$\text{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

提示

样例还看不懂就看下图

数据范围

对于$100\%$的数据：$n\le 100000，m\le 10^{18}$。保证军队在移动过程中不会超出边界。

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