#10129. 「一本通 4.3 练习 3」维护序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:AHOI 2009

老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。

有长为 n 的数列,不妨设为 a_1,a_2,\cdots ,a_n 。有如下三种操作形式:

  • 把数列中的一段数全部乘一个值;
  • 把数列中的一段数全部加一个值;
  • 询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 P 的值。

输入格式

第一行两个整数 n P

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

第三行有一个整数 M ,表示操作总数;

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

  • 操作 1 1 t g c,表示把所有满足 t\le i\le g a_i 改为 a_i\times c
  • 操作 2 2 t g c,表示把所有满足 t\le i\le g a_i 改为 a_i+c
  • 操作 3 3 t g,询问所有满足 t\le i\le g a_i 的和模 P 的值。

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

输出格式

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

样例

样例输入

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

样例输出

2
35
8

样例说明

初始时数列为 \{1,2,3,4,5,6,7\}

经过第 1 次操作后,数列为 \{1,10,15,20,25,6,7\}

对第 2 次操作,和为 10+15+20=45 ,模 43 的结果是 2

经过第 3 次操作后,数列为 \{1,10,24,29,34,15,16\}

对第 4 次操作,和为 1+10+24=35 ,模 43 的结果是 35

对第 5 次操作,和为 29+34+15+16=94 ,模 43 的结果是 8

数据范围与提示

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

测试数据规模如下表所示:

数据编号 1 2,3 4 5 6 7 8 9,10
n= 10 10^3 10^4 6\times 10^4 7\times 10^4 8\times 10^4 9\times 10^4 10^5
M=