您正在打 galgame，然后您觉得这个 gal 不知所云，于是您弃坑了，开始写数据结构题：
给一个长为 $n$ 的序列，$m$ 次操作，每次操作：
区间 $[l,r]$ 加 $x$
对于区间 $[l,r]$，查询 $a[l]^{a[l+1]^{a[l+2] \cdots}} \bmod p$，一直到 $a_r$
请注意每次的模数不同。
第一行两个整数 $n,m$ 表示序列长度和操作数
接下来一行，$n$ 个整数，表示这个序列
接下来 $m$ 行，可能是以下两种操作之一：
1 l r x表示区间 $[l,r]$ 加上 $x$
1 l r x
2 l r p表示对区间 $[l,r]$ 进行一次查询，模数为 $p$
2 l r p
对于每个询问，输出一个数表示答案。
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
$n , m \le 500000$，序列中每个数在 $[1，2\times 10^9]$ 内，$p \le 10^7$， 每次加上的数在 $[0, 2 \times 10^9]$。
Comet OJ