[SDOI2019]快速查询

题号：NC50812
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一个长度为n的整数数列，里面的元素依次编号为 $a_1,a_2,a_3, \cdots,a_n$ 。初始的时候，所有元素都为零。现在按照时间顺序提供了若干次关于这个数列的修改或询问，每一次修改或询问一定为以下六种情况之一：

$1 \ i \ \text{val}$ ：将 $a_i$ 赋值为给定整数 $\text{val}$ ；
$2 \ \text{val}$ ：将所有元素同时加上 $\text{val}$ ；
$3 \ \text{val}$ ：将所有元素同时乘上 $\text{val}$ ；
$4 \ \text{val}$ ：将所有元素同时赋值为 $\text{val}$ ；
$5 \ i$ ：询问第i个元素 $a_i$ 现在的值是多少；
6：询问现在所有元素的和。

输入描述:

为了避免读入太大，输入文件采取如下的形式。
第一行给定整数n，表示给定数列长度为n。
第二行给定整数q，并且之后的q行，每一行提供一个修改或询问，输入的格式与题目所述一致，请参见样例。
我们称上述给定的修改或询问为标准操作。
之后给定一个整数t，并且之后的t行每行给定两个正整数和，这里的下标i依次记为1到t。
你需要对初始值全为零的长度为n的序列做总计次操作。
其中第次操作形如第个给定的标准操作（且）。

输出描述:

输出一个整数，表示所有询问答案的累计和。
因为答案可能很大，只要求输出其结果关于取模后的值。
注意：若最终的累计和小于零，你应该输出。

示例1

输入

复制

7
28
6
4 -192321079
3 418379342
1 3 189801569
3 -840249197
4 -751917965
3 649799919
1 5 -92666141
6
4 451258008
5 1
4 696880327
3 772574465
6
4 301010289
3 480168068
5 3
5 2
4 840536237
5 5
5 4
1 7 -792284106
2 604521872
3 966540578
2 -381646699
3 -939378260
2 -20129935
6
2
0 1
197 199

输出

复制

备注:

子任务1（50分）：，且，所有在输入中出现的满足，所有和满足。
子任务2（50分）：，且，所有在输入中出现的满足，所有和满足。