原題來(lái)自：AHOI 2009

老師交給小可可一個(gè)維護(hù)數(shù)列的任務(wù)，現(xiàn)在小可可希望你來(lái)幫他完成。

有長(zhǎng)為 n 的數(shù)列，不妨設(shè)為 a1,a2,?,an 。有如下三種操作形式：

把數(shù)列中的一段數(shù)全部乘一個(gè)值；

把數(shù)列中的一段數(shù)全部加一個(gè)值；

詢問(wèn)數(shù)列中的一段數(shù)的和，由于答案可能很大，你只需輸出這個(gè)數(shù)模 P 的值。

第一行兩個(gè)整數(shù) n 和 P；

第二行含有 n 個(gè)非負(fù)整數(shù)，從左到右依次為 a1,a2,?,an ；

第三行有一個(gè)整數(shù) M，表示操作總數(shù)；

從第四行開始每行描述一個(gè)操作，輸入的操作有以下三種形式：

操作 1：1 t g c，表示把所有滿足 t≤i≤g 的 a_i 改為 a_i×c；

操作 2：2 t g c，表示把所有滿足 t≤i≤g 的 a_i 改為 a_i+c；

操作 3：3 t g，詢問(wèn)所有滿足 t≤i≤g 的 ai 的和模 P 的值。

同一行相鄰兩數(shù)之間用一個(gè)空格隔開，每行開頭和末尾沒有多余空格。

對(duì)每個(gè)操作 3，按照它在輸入中出現(xiàn)的順序，依次輸出一行一個(gè)整數(shù)表示詢問(wèn)結(jié)果。

樣例說(shuō)明:

初始時(shí)數(shù)列為 {1,2,3,4,5,6,7}；

經(jīng)過(guò)第 1 次操作后，數(shù)列為 {1,10,15,20,25,6,7}；

對(duì)第 2 次操作，和為 10+15+20=45，模 43 的結(jié)果是 22；

經(jīng)過(guò)第 3 次操作后，數(shù)列為 {1,10,24,29,34,15,16}；

對(duì)第 4 次操作，和為 1+10+24=35，模 43 的結(jié)果是 35；

對(duì)第 5 次操作，和為 29+34+15+16=94，模 43 的結(jié)果是 8。

數(shù)據(jù)范圍與提示：

對(duì)于全部測(cè)試數(shù)據(jù)，1≤t≤g≤n,0≤c,a_i≤10⁹,1≤P≤10⁹ 。

測(cè)試數(shù)據(jù)規(guī)模如下表所示：

信息學(xué)一本通 數(shù)據(jù)結(jié)構(gòu)