题目背景

本题和 P3934 [Ynoi2016]炸脖龙I 完全一致，但为了赛题的一致性，展示题面而不予提交。

[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$
4	$n = 1000$	$m = 1000$	查询区间长度不大于2
5	$n = 100000$	$m = 100000$
6	$n = 1000$	$m = 1000$	$a_i \le 2$
7			$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]$内