给一个长为 $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$。

输出格式

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

样例数据

样例 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 输出

1
3
1

样例 2 输入

5 5
2 3 3 3 3
1 1 1 530739835
2 1 1 8356089
2 1 4 5496738
1 1 2 66050181
1 2 4 138625417

样例 2 输出

4306230
697527

子任务

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

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

共10组数据