Johnny 成了道路中心的一名调度员。他的任务是调查在一系列暴风雪期间，某条道路上扫雪工作的有效性。这条道路被划分为连续的、长度为 1 千米的路段，用从 $1$ 到 $n$ 的连续整数进行编号。Johnny 迅速投入工作，并收集了有关事件的信息：

• 气象中心向他提供了有关暴风雪的信息；暴风雪的强度由两个参数 $f, g$ 决定：在这种暴风雪的第 $i$ 分钟（$i \ge 1$），整条道路上到处都会降下 $f \cdot i + g$ 毫米的雪。每场暴风雪都在下一场暴风雪开始的前一分钟结束。时间经过了校准，使得第一场暴风雪在正数分钟开始，且在第 $0$ 分钟时道路上没有积雪。
• 扫雪中心向 Johnny 提供了关于扫雪车和撒盐车的信息。扫雪车或撒盐车的每条路线总是由连续编号的路段组成的一段道路区间。如果扫雪车在第 $t$ 分钟清扫了某些路段，那么在第 $t$ 分钟结束时，被清扫的路段上没有积雪。同样地，在第 $t$ 分钟向某些路段撒上质量为 $s$ 的盐，可以确保在第 $t, t + 1, \dots, t + s$ 分钟结束时，这些路段上没有积雪。不同的盐（即使质量相同）相互独立作用，互不影响；同样地，扫雪车不会清除道路上的盐。
• 道路中心发送了询问——给出在给定分钟结束时，由连续编号的路段组成的给定道路区间上的最大积雪厚度（以毫米为单位）。

Johnny 对收集到的数据进行了预处理和排序。不幸的是，计算询问的答案对他来说太难了。请帮助他！写一个程序来计算道路中心询问的答案。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^9$，$1 \le q \le 300\,000$），它们之间用单个空格分隔，分别表示道路的千米路段数和事件数。

在接下来的 $q$ 行中，每行包含对以下四种类型之一的事件的描述：

• t L a b：表示扫雪车在第 $t$ 分钟清扫了由编号从 $a$ 到 $b$ 的路段组成的道路区间。
• t S a b s：表示撒盐车在第 $t$ 分钟向由编号从 $a$ 到 $b$ 的路段组成的道路区间撒了质量为 $s$ 的盐。
• t ? a b：表示道路中心想要知道在第 $t$ 分钟结束时，由编号从 $a$ 到 $b$ 的路段组成的道路区间上的最大积雪厚度。
• t B f g：表示第 $t$ 分钟是前一场暴风雪（如果存在）的最后一分钟，而第 $(t + 1)$ 分钟是强度为 $f, g$ 的新暴风雪的第一分钟。

在所有事件中，均满足以下条件：$1 \le t \le 10^9$，$1 \le a \le b \le n$，$1 \le s, f, g \le 10^9$。

此外，连续事件的 $t$ 值是严格递增的，且第一个事件总是 B 类型。

输出格式

对于每个 ? 事件，在单独的一行中输出在指定道路区间、给定分钟结束时的最大积雪厚度模 $10^9 + 7$ 的余数。

样例

输入样例 1

3 4
2 B 1 2
3 ? 2 2
4 L 1 3
5 ? 1 3

输出样例 1

3
5

输入样例 2

1 3
1 B 1 1
2 B 3 3
3 ? 1 1

输出样例 2

8

输入样例 3

5 5
1 B 1 2
2 S 1 3 5
3 ? 3 4
4 ? 1 1
10 ? 1 1

输出样例 3

7
0
30

说明

下表显示了样例 1 中每个路段在每分钟结束时的积雪覆盖情况。它还显示了每分钟的降雪量。加粗的数字对应于询问。

在第一次询问之前，整条道路上降了 $1 \cdot 1 + 2 = 3$ 毫米的雪。在第 4 分钟扫雪车通过与第二次 ? 询问之间，又降了 $3 \cdot 1 + 2 = 5$ 毫米的雪。

样例 2 说明：

在 ? 事件之前，第一场暴风雪持续了 1 分钟，第二场暴风雪也持续了 1 分钟。

样例 3 说明：