Nephren Ruq Insania

本题和 [P3934 [Ynoi2016]炸脖龙I](https://www.luogu.com.cn/problem/P3934) 完全一致，但为了赛题的一致性，展示题面而不予提交。 [Ynoi2016]炸脖龙I 题面备份 https://www.luogu.org/discuss/show/45962 大样例下发链接: https://pan.baidu.com/s/1nuVpRS1 密码: sfxg **注意：本题大样例4的输出文件修改为 https://pan.baidu.com/s/1bUWuZW** 奈芙莲·卢可·印萨尼亚(Nephren-Ruq-Insania)  同为妖精仓库的成体妖精兵，天赋不如珂朵莉一般，只是一个平凡的妖精. 睡觉时如同毯子一般在威廉身上为其保暖。习惯于粘着威廉，在梦境中与艾尔梅莉亚交谈时，自称就像是威廉的宠物一样。  本题题面中含有大量的剧透，建议做题之前将这部番剧看完（

她只是一个非常普通的黄金妖精。 在援救打捞队的作战中，他们不幸与（几乎是所有的）第六兽相遇了。 此时的珂朵莉因为接触到星神艾露可本体，正处于昏迷之中。而威廉也无法离开珂朵莉。  默默守护在房间外的她，提起圣剑，走向了战场。  作为本身天赋只是一般的妖精少女，她难以对抗无数倍于自己的六号兽。 没有多久，她开始体力不支。 终于，在源源不断的六号兽面前，她难以抵挡了……  终于，由于魔力过度激发，她已经处在了魔力失控的边缘…… ”威廉，拯救，是我们黄金妖精的使命。“ ”况且，威廉之前已经救过我们了。“ ”所以，已经没有问题了。“  威廉想要救下奈芙莲，但是他自己也已经处于崩溃的边缘。 冥冥之中他想起了曾经学习过的一种魔法。在这最后一刻，或许已经是唯一的办法了。 这种魔法操作的对象是一个咒语组成的序列，每一个单独的咒语拥有自己的法力值。 威廉需要不断地按照之前的记忆，对某一段区间的法力值加上一个数，或者求出某一段区间的法咒共鸣。 法咒共鸣具体而言是这么计算的： 对于区间$[l,r]$， 查询 $ a[l]^{a[l+1]^{a[l+2]^{.....}}} \bmod \ p$，一直到 $ a[r] $ 请注意每次的模数不同。 时间不够了，威廉自己无力计算这么复杂的魔法。但是这是最后的希望了。 能否拯救奈芙莲，就靠您了。 

第一行两个整数$n,m$,表示序列长度和操作数。 接下来一行，$n$个整数$a_i$表示这个序列。 接下来$m$行，可能是以下两种操作之一： - `1 l,r,x`，表示区间$[l,r]$加上$x$ - `2 l,r,p` ,表示进行一次法咒共鸣，模数为$p$

对于每个操作2，输出一行表示答案。

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

1
3
1

测试点　　　|n的范围　　　　| m的范围　　　　| 特殊限制 -|-|-|- 1| $n = 5 $ |$m = 5 $ |$a_i \le 3$ 2| $n = 1000 $ |$m = 1000 $ |查询区间长度为1 3| $n = 100000$ |$m = 100000$ |查询区间长度为1 4| $n = 1000 $ |$m = 1000 $ |查询区间长度不大于2 5| $n = 100000$ |$m = 100000$ |查询区间长度不大于2 6| $n = 1000 $ |$m = 1000 $ |$a_i \le 2$ 7| $n = 1000 $ |$m = 1000 $ |$p = 2$ 8| $n = 100000$ |$m = 100000$ |$p = 2$ 无修改 9| $n = 1000 $ |$m = 1000 $ |$p \le 100000$ 无修改 10| $n = 500000$ |$m = 500000$ |无 对于100%的数据，$n , m \le 500000$ , 序列中每个数在$[1,2\cdot 10^9]$内，$p \le 2 \cdot 10^7 $, 每次加上的数在$[0,2\cdot 10^9]$内