时间限制：1000 ms
内存限制：512 MiB
标准输入输出
题目类型：传统
评测方式：文本比较
原题来自：AHOI 2009
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为 的数列，不妨设为 。有如下三种操作形式：
- 把数列中的一段数全部乘一个值；
- 把数列中的一段数全部加一个值；
- 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 的值。
第一行两个整数 和 ；
第二行含有 个非负整数，从左到右依次为 ；
第三行有一个整数 ，表示操作总数；
从第四行开始每行描述一个操作，输入的操作有以下三种形式：
- 操作 ：
1 t g c，表示把所有满足 的 改为 ；
- 操作 ：
2 t g c，表示把所有满足 的 改为 ；
- 操作 ：
3 t g，询问所有满足 的 的和模 的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
对每个操作 ，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
样例输入
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
样例输出
样例说明
初始时数列为 ；
经过第 次操作后，数列为 ；
对第 次操作，和为 ，模 的结果是 ；
经过第 次操作后，数列为 ；
对第 次操作，和为 ，模 的结果是 ；
对第 次操作，和为 ，模 的结果是 。