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

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

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:AHOI 2009

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

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

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

Input

第一行两个整数 nnnPPP

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

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

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

  • 操作 111:1 t g c,表示把所有满足 t≤i≤gt\le i\le gtigaia_iai 改为 ai×ca_i\times cai×c
  • 操作 222:2 t g c,表示把所有满足 t≤i≤gt\le i\le gtigaia_iai 改为 ai+ca_i+cai+c
  • 操作 333:3 t g,询问所有满足 t≤i≤gt\le i\le gtigaia_iai 的和模 PPP 的值。

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


Output

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


Sample Input

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

Sample Output

2
35
8

HINT

对于全部测试数据,1≤t≤g≤n,0≤c,ai≤109,1≤P≤1091\le t\le g\le n,0\le c,a_i\le 10^9,1\le P\le 10^91tgn,0c,ai109,1P109

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

数据编号 111 2,32,32,3 444 555 666 777 888 9,109,109,10
n=n=n= 101010 10310^3103 10410^4104 6×1046\times 10^46×104 7×1047\times 10^47×104 8×1048\times 10^48×104 9×1049\times 10^49×104 10510^5105
M=M=M= 101010 10310^3103 10410^4104 6×1046\times 10^46×104 7×1047\times 10^47×104 8×1048\times 10^48×104 9×1049\times 10^49×104 10510^5105

Source/Category


Submit Status