在一片 的地上．驻扎着 个军队,编号依次为 ,第 个军队的位置可用二元组 表示，可能有多个军队驻扎在同一个位置。
接下来有 个时刻，每个时刻会发生下列两种事件之一：
U
D
L
R
定义第 个军队赶到第 个军队所需的花费为 。
请你输出每次集结时，所有被集结的军队的花费之和，对 取模。
第一行，两个数 和 。
接下来 行，每行两个数 。
接下一行，一个数 。
接下来 行，每行的格式为下列两种格式之一：
S x d
Q x L R
为了体现在线询问,每次你读进 后，真正的 ，其中 是上一次答案对 取模后的结果，一开始 。
对于每一个 Q 事件，输出一个答案，对 取模。
Q
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
。保证军队在移动过程中不会超出边界。每个军队集结后会回到原来的驻地。
By Dzy
