时间限制：4000 ms
内存限制：512 MiB
标准输入输出
题目类型：传统
评测方式：文本比较
waht 先生是一名法力强大的魔法师。
waht 先生为了增强自己的法力，设置了一个法阵。这个法阵中共有 块魔法石，它们从左到右依次排成一列；并且从左数第 块魔法石的编号为 ，其法力值初始为 。
waht 先生可以获取一些魔法石的法力。然而由于这个法阵的特殊性质，在获取法力时，waht 先生必须先选择一块魔法石；并且一旦第 块魔法石被选，接下来必须再选第 块魔法石（这里 表示 的最大公约数），直到 时 waht 先生会立即停止本次法力获取的过程。waht 先生获取的法力将会是过程中所选的所有魔法石的法力值之和。
waht 先生会对这个法阵进行 次操作。具体的，有以下两类操作：
- waht 先生选择两个数 ，对区间 中的所有魔法石施加法术，使得它们的法力值全部乘以 。具体的，对于所有满足 的 ，将 的值修改为 。
- waht 先生选择第 块魔法石，并按照上述的规则获取法力。
每当 waht 先生选择某一块魔法石来获取法力时，你都需要帮他计算出他到底获得了多少法力。由于答案可能很大，你只需要求出答案对 取模的结果。
第一行输入两个正整数 ，表示法阵中魔法石的数量和操作次数。
接下来一行，输入 个正整数，其中第 个为 ，表示魔法石初始的法力值。
接下来 行，先输入一个 ，表示操作种类；
若 ，则再输入三个正整数 ，表示将区间 中的所有魔法石的法力值乘以 ；
若 ，则再输入一个正整数 ，表示获取法力的开始位置。
每当进行一次操作 时，输出一行一个正整数，表示所要查询的答案对 取模的值。
样例输入 1
7 7
1 1 1 1 1 1 1
1 2 6 2
2 1
1 3 5 5
2 3
1 2 7 3
2 3
2 2
样例输出 1
第一次操作，将区间 中的魔法石的法力值乘以 ，法力值序列变为 ；
第二次操作，waht 先生选择第 块魔法石，则编号为 的魔法石会依次被选中，这些魔法石的法力值之和为 ；
第三次操作，将区间 中的魔法石的法力值乘以 ，法力值序列变为 ；
第四次操作，waht 先生选择第 块魔法石，则编号为 的魔法石会依次被选中，这些魔法石的法力值之和为 ；
第五次操作，将区间 中的魔法石的法力值乘以 ，法力值序列变为 ；
第六次操作，waht 先生选择第 块魔法石，则编号为 的魔法石会依次被选中，这些魔法石的法力值之和为 ；
第七次操作，waht 先生选择第 块魔法石，则编号为 的魔法石会依次被选中，这些魔法石的法力值之和为 。
题目来源
来自 2025 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2025）初赛。
题解等资源可在 https://gitlink.org.cn/thusaa/thupc2025pre/tree/master 查看。