#2029. 「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

输出

2
35
8

解释

初始时数列为 ；

经过第 次操作后，数列为 ；

对第 次操作，和为 ，模 的结果是 ；

经过第 次操作后，数列为 ；

对第 次操作，和为 ，模 的结果是 ；

对第 次操作，和为 ，模 的结果是 。

对于全部测试数据，。

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