输入描述:

第一行两个整数N和P(1 ≤ P ≤ 1000000000）。
第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0 ≤ ai ≤ 1000000000,1 ≤ i ≤ N)。
第三行有一个整数M，表示操作总数。
从第四行开始每行描述一个操作，输入的操作有以下三种形式： 
操作1：“1 t g c”(不含双引号)。表示把所有满足t ≤ i ≤ g的ai改为ai×c (1 ≤ t ≤ g ≤ N,0 ≤ c ≤ 1000000000)。
操作2：“2 t g c”(不含双引号)。表示把所有满足t ≤ i ≤ g的ai改为ai+c (1 ≤ t ≤ g ≤ N,0 ≤ c ≤ 1000000000)。 
操作3：“3 t g”(不含双引号)。询问所有满足t ≤ i ≤ g的ai的和模P的值 (1 ≤ t ≤ g ≤ N)。 
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出描述:

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

备注:

对于全部的测试点，保证