单点时限: 2.0 sec
内存限制: 512 MB
Cuber QQ 在研究动态规划时收获了快乐。他想把这份快乐通过这题传达给你。
Cuber 有 $x_1, x_2, \cdots, x_n$ 这 $n$ 个变量。其中，$x_i$ 可以是区间 $[l_i, r_i]$ 内的任何整数。
现在，Cuber 会进行 $m$ 次操作，每次操作都是下面两种之一：
M k u v：Cuber 将 $[l_k, r_k]$ 改为 $[u, v]$；Q p q：Cuber 让你回答若 $x_i$ 在范围内任意取值，$|x_p - x_{p + 1}| + |x_{p + 1} - x_{p + 2}| + \cdots + |x_{q - 1} - x_q|$ 最小是多少。第一行两个整数 $n, m$（$1 \le n \le 10^5, 1 \le m \le 2 \times 10^5$）。
接下来 $n$ 行，每行两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le 10^9$）。
接下来 $m$ 行，每行一个操作。操作要么形如 M k u v（$1 \le k \le n, 1 \le u \le v \le 10^9$），要么形如 Q p q（$1 \le p \le q \le n$）。
对于每个询问，输出一行一个整数，表示答案。
5 9 1 2 3 6 4 5 2 5 1 3 Q 1 3 Q 2 4 Q 3 5 Q 1 1 Q 1 5 M 1 2 4 Q 1 4 M 3 1 2 Q 1 5
2 0 1 0 3 0 1
5 10 19 50 13 58 35 94 32 36 22 76 M 4 98 98 Q 1 4 M 3 55 57 Q 1 1 M 3 65 82 Q 4 5 M 4 37 41 Q 1 3 M 2 39 83 Q 4 5
48 0 22 15 0