Galgame Data Structure Operation

You are given a sequence of length (n) and (m) operations. Initially, the sequence (a[1], a[2], \dots, a[n]) is provided. There are two types of operations:

1. Update Operation: Given integers l, r, x, add (x) to every element in the interval ([l, r]).

2. Query Operation: Given integers l, r, p, compute the following expression and output its value modulo (p):

[ a[l]^{a[l+1]^{a[l+2]^{\dots ^{a[r]}}}} \mod p ]

Note that exponentiation is evaluated from right to left. For example, if (a = [3,2,1]), then the query on ([1,3]) computes (3^{(2^1)} = 3^2 = 9) modulo (p).

This problem requires supporting both range updates and power‐tower queries.

inputFormat

The first line contains two integers (n) and (m) representing the length of the sequence and the number of operations respectively. The second line contains (n) integers (a[1], a[2], \dots, a[n]) — the initial sequence. Then (m) lines follow. Each line describes an operation in one of the following formats:

• 1 l r x: For all indices \(l \le i \le r\), add \(x\) to \(a[i]\).
• 2 l r p: Query the value of \(a[l]^{a[l+1]^{\dots^{a[r]}}} \mod p\).

All indices are 1-indexed.

outputFormat

For each query operation (operation type 2), output the resulting integer on a separate line.

sample

3 3
3 2 1
2 1 3 1000
1 2 3 2
2 1 3 1000

9
281