给一个长为 $n$ 的序列，$m$ 次操作，每次操作：
- 区间 $[l,r]$ 加 $x$；
- 对于区间 $[l,r]$，查询：
$$a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p$$
输入格式
第一行两个整数 $n,m$ 表示序列长度和操作数。
接下来一行，$n$ 个整数表示这个序列。
接下来 $m$ 行，可能是以下两种操作之一：
- $1\ l\ r\ x$ 表示区间 $[l,r]$ 加上 $x$；
- $2\ l\ r\ p$ 表示对区间 $[l,r]$ 进行一次查询，模数为 $p$。
输出格式
对于每个询问，输出一个数表示答案。
样例数据
样例 1 输入
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 输出
1
3
1样例 2 输入
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样例 2 输出
4306230
697527子任务
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组数据