4228. [Ynoi Easy Round 2016] Nephren Ruq Insania

【题目背景】

奈芙莲·卢可·印萨尼亚(Nephren-Ruq-Insania)

同为妖精仓库的成体妖精兵，天赋不如珂朵莉一般，只是一个平凡的妖精.

睡觉时如同毯子一般在威廉身上为其保暖。习惯于粘着威廉，在梦境中与艾尔梅莉亚交谈时，自称就像是威廉的宠物一样。

本题题面中含有大量的剧透，建议做题之前将这部番剧看完（bushi

【题目描述】

她只是一个非常普通的黄金妖精。

在援救打捞队的作战中，他们不幸与（几乎是所有的）第六兽相遇了。

此时的珂朵莉因为接触到星神艾露可本体，正处于昏迷之中。而威廉也无法离开珂朵莉。

默默守护在房间外的她，提起圣剑，走向了战场。

作为本身天赋只是一般的妖精少女，她难以对抗无数倍于自己的六号兽。

没有多久，她开始体力不支。

终于，在源源不断的六号兽面前，她难以抵挡了……

终于，由于魔力过度激发，她已经处在了魔力失控的边缘……

”威廉，拯救，是我们黄金妖精的使命。“

”况且，威廉之前已经救过我们了。“

”所以，已经没有问题了。“

威廉想要救下奈芙莲，但是他自己也已经处于崩溃的边缘。

冥冥之中他想起了曾经学习过的一种魔法。在这最后一刻，或许已经是唯一的办法了。

这种魔法操作的对象是一个咒语组成的序列，每一个单独的咒语拥有自己的法力值。

威廉需要不断地按照之前的记忆，对某一段区间的法力值加上一个数，或者求出某一段区间的法咒共鸣。

法咒共鸣具体而言是这么计算的：

对于区间 $[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$，输出一行表示答案。

【样例输入】

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

【样例说明】

无。

【数据规模与约定】

【来源】

[Ynoi Easy Round 2016] Nephren Ruq Insania