简单数据结构1

题号：NC17190
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

1.区间

加

2.对于区间

，查询 $a[l]^{a[l+1]^{a[l+2]......}}$

，一直到

请注意每次的模数不同。

第一行两个整数 n,m 表示序列长度和操作数

接下来一行，n个整数，表示这个序列

接下来m行，可能是以下两种操作之一：

操作1：区间[l,r]加上 x

操作2：查询区间[l,r]的那个式子mod p的值

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

示例1

复制

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 <= 500000

序列中每个数在 [1,2e9] 内，x <= 2e9 , p <= 2e7