Description

您正在打 galgame，然后您觉得这个 gal 不知所云，于是您弃坑了，开始写数据结构题：

给一个长为 $n$ 的序列，$m$ 次操作，每次操作：

1. 区间 $[l,r]$ 加 $x$；
2. 对于区间 $[l,r]$，查询：

Input Format

第一行两个整数 $n,m$ 表示序列长度和操作数。

接下来一行，$n$ 个整数表示这个序列。

接下来 $m$ 行，可能是以下两种操作之一：

• $1\ l\ r\ x$ 表示区间 $[l,r]$ 加上 $x$；
• $2\ l\ r\ p$ 表示对区间 $[l,r]$ 进行一次查询，模数为 $p$。

Output Format

对于每个询问，输出一个数表示答案。

6 4
1 2 3 4 5 6
2 1 2 10000007
2 2 3 5
1 1 4 1
2 2 4 10

1
3
1

5 5
2 3 3 3 3
1 1 1 530739835
2 1 1 8356089
2 1 4 5496738
1 1 2 66050181
1 2 4 138625417

4306230
697527

Hint

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于100%的数据，$n , m \le 500000$ , 序列中每个数在$[1,2\cdot 10^9]$内，$p \le 2 \cdot 10^7$, 每次加上的数在$[0,2\cdot 10^9]$内

共10组数据