题目描述

老师交给小理一个维护数列的任务，现在小理希望你来帮他完成。 有长为 $N$ 的数列，不妨设为 $a_1,a_2,...,a_N$ 。

有如下三种操作形式：

• 把数列中的一段数全部乘一个值;

• 把数列中的一段数全部加一个值;

• 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 $P$ 的值。

输入格式

第一行两个整数 $N$ 和 $P$ 。

第二行含有 $N$ 个非负整数,从左到右依次为$a_1,a_2,...,a_N$ 。

第三行有一个整数 $M$ ，表示操作总数。

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

操作 $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。询问所有满足 $t ≤ i ≤ g$ 的 $a_i$ 的和模 $P$ 的值 。

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

输出格式

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

数据范围

对于 $100%$ 的数据，保证 $10 \le N,M \le 10^5,0≤p,a_i,c≤10^9,1≤t≤g≤n$ 。