Range Update and Exponent Sum Query

This problem requires you to maintain a sequence \(a_1,a_2,\ldots,a_n\) and support the following two operations:

• Update Operation: Given integers \(l\), \(r\), \(u\), \(v\) and \(w\), update every \(a_i\) for \(l \le i \le r\) satisfying \(u \le a_i \le v\) to \(w\). That is, for every index \(i\) in \([l, r]\) if \(a_i\) is within the interval \([u,v]\), then set \(a_i = w\).
• Query Operation: Given integers \(l\), \(r\), \(t\) and \(k\), compute \[ S = \sum_{i=l}^{r}a_i^t \bmod k, \] and output the result.

Note: The submission automatically uses the O2 optimization flag.

inputFormat

The first line of input contains two integers \(n\) and \(q\) representing the length of the sequence and the number of operations respectively.

The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\) representing the initial array.

Each of the following \(q\) lines describes an operation. An operation is in one of the following two formats:

• For an update operation: 1 l r u v w
• For a query operation: 2 l r t k

All indices are 1-indexed.

outputFormat

For each query operation, output the corresponding answer on a separate line. There is no output for update operations.

sample

5 3
1 2 3 4 5
2 1 5 1 100
1 2 4 2 4 10
2 1 5 2 100

15
26