#794. [AHOI2009] 维护序列

[AHOI2009] 维护序列

[AHOI2009] 维护序列

题目背景

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

题目描述

有一个长为 nn 的数列 {an}\{a_n\},有如下三种操作形式:

  1. 格式 1 t g c,表示把所有满足 tigt\le i\le gaia_i 改为 ai×ca_i\times c ;
  2. 格式 2 t g c 表示把所有满足 tigt\le i\le gaia_i 改为 ai+ca_i+c ;
  3. 格式 3 t g 询问所有满足 tigt\le i\le gaia_i 的和,由于答案可能很大,你只需输出这个数模 pp 的值。

输入格式

第一行两个整数 nnpp

第二行含有 nn 个非负整数,表示数列 {ai}\{a_i\}

第三行有一个整数 mm,表示操作总数。

从第四行开始每行描述一个操作,同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。

输出格式

对每个操作 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

提示

样例输入输出 1 解释

  • 初始时数列为 {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 2 3 4 5 6 7 8 9,10
n=n= 1010 10001000 1000010000 6000060000 7000070000 8000080000 9000090000 100000100000
m=m=

对于全部的测试点,保证 0p,ai,c1090 \leq p, a_i, c \leq 10^91tgn1 \leq t \leq g \leq n