题目背景
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。
题目描述
有一个长为 n 的数列 {an},有如下三种操作形式:
- 格式
1 t g c
,表示把所有满足 t≤i≤g 的 ai 改为 ai×c ;
- 格式
2 t g c
表示把所有满足 t≤i≤g 的 ai 改为 ai+c ;
- 格式
3 t g
询问所有满足 t≤i≤g 的 ai 的和,由于答案可能很大,你只需输出这个数模 p 的值。
输入格式
第一行两个整数 n 和 p。
第二行含有 n 个非负整数,表示数列 {ai} 。
第三行有一个整数 m,表示操作总数。
从第四行开始每行描述一个操作,同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。
输出格式
对每个操作 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 解释
- 初始时数列为 {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 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9,10 |
n= |
10 |
1000 |
10000 |
60000 |
70000 |
80000 |
90000 |
100000 |
m= |
对于全部的测试点,保证 0≤p,ai,c≤109,1≤t≤g≤n。