4318. 数据结构题

【题目背景】

数据结构题

【题目描述】

您正在打 galgame，然后您觉得这个 gal 不知所云，于是您弃坑了，开始写数据结构题：

给一个长为 $n$ 的序列，$m$ 次操作，每次操作：

1：区间 $[l,r]$ 加 $x$；

2：对于区间 $[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$。

【输出格式】

对于每个询问，输出一个数表示答案。

【样例输入】

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

【数据规模与约定】

对于10%的数据，$n,m \le 5000$

对于20%的数据，$n \le 5000, m \le 10^5$，且操作2次数不超过 $5000$ 次

对于100%的数据，$n , m \le 500000$ , 序列中每个数在$[1,2\cdot 10^9]内，p \le 2 \cdot 10^7$ , 每次加上的数在$[0,2\cdot 10^9]$内