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

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

题目描述

原题来自:AHOI 2009

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

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

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

输入格式

第一行两个整数 nnPP

第二行含有 nn 个非负整数,从左到右依次为 a1,a2,,ana_1,a_2,\cdots ,a_n

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

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

  • 操作 111 t g c,表示把所有满足 tigt\le i\le gaia_i 改为 ai×ca_i\times c
  • 操作 222 t g c,表示把所有满足 tigt\le i\le gaia_i 改为 ai+ca_i+c
  • 操作 333 t g,询问所有满足 tigt\le i\le gaia_i 的和模 PP 的值。

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

输出格式

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

样例

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,2,3,4,5,6,7\}

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

对第 22 次操作,和为 10+15+20=4510+15+20=45,模 4343 的结果是 22

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

对第 44 次操作,和为 1+10+24=351+10+24=35,模 4343 的结果是 3535

对第 55 次操作,和为 29+34+15+16=9429+34+15+16=94,模 4343 的结果是 88

数据范围与提示

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

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

数据编号 11 2,32,3 44 55 66 77 88 9,109,10
n=n= 1010 10310^3 10410^4 6×1046\times 10^4 7×1047\times 10^4 8×1048\times 10^4 9×1049\times 10^4 10510^5
M=M=