[ABC357] F - Two Sequence Queries

F - Two Sequence Queries

Time Limit: 5 sec / Memory Limit: 1024 MB

分数： 分

题面

给定长度为 的序列 和 。
同时给定 个需要按顺序处理的查询。

有三种类型的查询：

• 1 l r x : 将 添加到 的每个元素中。
• 2 l r x : 将 添加到 的每个元素中。
• 3 l r : 输出 在模 下的余数。

限制条件

• 所有输入值均为整数。
• 至少有一个第三类查询。

---

输入

输入从标准输入中以以下格式给出。这里， 是第 个需处理的查询。

每个查询以以下格式之一给出：

输出

如果有 个第三类查询，输出 行。
第 行 () 应包含第 个第三类查询的输出。

---

输入示例 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

输出示例 1

16
25
84

初始时， 且 。查询依以下顺序进行：

• 对于第一个查询，输出 模 的余数，为 。
• 对于第二个查询，将 加到 。现在 。
• 对于第三个查询，输出 模 的余数，为 。
• 对于第四个查询，将 加到 。现在 。
• 对于第五个查询，将 加到 。现在 。
• 对于第六个查询，输出 模 的余数，为 。

因此，第一、第二、第三行应分别包含 、 和 。

---

输入示例 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

输出示例 2

716070898
151723988

确保输出第三类型查询的和模 。