U503807 【模板】动态开点线段树

动态开点线段树板子。

已知一个长度为 $n$ 的数列，下标从 $1$ 开始，初始均为 $0$。 你需要进行下面三种操作： - 将某区间每一个数乘 $x$。 - 将某区间每一个数加 $x$。 - 求出某区间每一个数的和。

第一行包含三个整数 $n,q,m$，分别表示该数列数字的个数、操作的总个数和模数。 接下来 $q$ 行每行包含若干个整数，表示一个操作，具体如下： 操作 $1$： 格式：`1 x y k` 含义：将区间 $[x,y]$ 内每个数乘 $k$。 操作 $2$： 格式：`2 x y k` 含义：将区间 $[x,y]$ 内每个数加 $k$。 操作 $3$： 格式：`3 x y` 含义：输出区间 $[x,y]$ 内每个数的和对 $m$ 取模所得的结果。 对于所有操作，数据保证：$1 \le x \le y \le n$，$1 \le k \le 10^9$。

输出包含若干行整数，即为所有操作 $3$ 的结果。

对于 $100\%$ 的数据：$1 \le n \le 10^9$，$1 \le q \le 10^5$，$1 \le m \le 10^9+7$。