题目描述
仓库有 $n$ 个货格排成一行，初始各有存货量 $a_i$。三种操作：
1 t g c：区间 $[t, g]$ 每格存货量乘以 $c$；2 t g c：区间 $[t, g]$ 每格存货量加 $c$；3 t g：询问 $[t, g]$ 存货量之和 mod $P$。
对每个询问操作输出结果。所有乘法与加法均在 mod $P$ 意义下执行。
输入格式
第一行两个整数 $n$ 和 $P$；
第二行 $n$ 个非负整数 $a_1 \ldots a_n$；
第三行一个整数 $M$；
接下来 $M$ 行，每行为 1 t g c、2 t g c 或 3 t g。
输出格式
对每个询问操作输出一行一个整数。
数据范围
$$1 \le n, M \le 3000$$
，$$1 \le P \le 10^9$$
，$$0 \le a_i, c < P$$
。