Orange的区间修改V

题目描述

Orange将给定数列 $a[1], a[2], \dots, a[n]$，你需要依次进行 $M$ 个操作，操作有三类：

• 1 l r x：给定 $l,r,x$，对于所有 $i\in[l,r]$，将 $a[i]$ 乘上 $x$（换言之，将 $a[l], a[l+1], \dots, a[r]$ 分别乘上 $x$）；
• 2 l r x：给定 $l,r,x$，对于所有 $i\in[l,r]$，将 $a[i]$ 加上 $x$（换言之，将 $a[l], a[l+1], \dots, a[r]$ 分别加上 $x$）；
• 3 l r：给定 $l,r$，求 $\sum_{i=l}^ra[i] \bmod P$ 的值（换言之，求 $(a[l]+a[l+1]+\dots+a[r]) \bmod P$ 的值）。

输入格式

第一行两个整数 $n$ 和 $P$；

第二行含有 $n$ 个非负整数，从左到右依次为 $a_1,a_2,\cdots ,a_n$；

第三行有一个整数 $M$，表示操作总数；

从第四行开始每行描述一个操作，输入的操作有以下三种形式：

• 操作 1：1 l r x，表示把所有满足 $l\le i\le r$ 的 $a_i$ 改为 $a_i\times x$；
• 操作 2：2 l r x，表示把所有满足 $l\le i\le r$ 的 $a_i$ 改为 $a_i+x$；
• 操作 3：3 l r，询问所有满足 $l\le i\le r$ 的 $a_i$ 的和模 $P$ 的值。

同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

数据范围

对于全部测试数据，$1\le t\le g\le n,0\le c,a_i\le 10^9,1\le P\le 10^9+7$。

输出格式

对每个操作 $3$，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

样例 #1

样例输入 #1

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

样例输出 #1

2
35
8