Exponential Array Maintenance

Informatik verbindet dich und mich. 信息将你我连结。

You are given an array of length \( n \) (with indices from \( 1 \) to \( n \)). Initially, the array is provided as \( a_1, a_2, \dots, a_n \). You are also given a constant \( c \) and a modulus \( p \). There will be \( m \) operations on the array, each in one of the following two forms:

• 0 l r: For each index \( i \) such that \( l \le i \le r \), update \( a_i \) to \( c^{a_i} \) (i.e. replace \( a_i \) by \( c^{a_i} \)). The power is written in LaTeX as \( c^{a_i} \).
• 1 l r: Query the sum over indices \( l \) to \( r \), i.e. compute \( \sum_{i=l}^{r} a_i \) and output the result modulo \( p \). The summation is given in LaTeX as \( \sum_{i=l}^{r} a_i \).

It is guaranteed that all operations follow the formats described above.

inputFormat

The first line contains four integers \( n, m, c, p \) representing the length of the array, the number of operations, the constant \( c \), and the modulus \( p \) respectively.

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

The following \( m \) lines each contain an operation in one of the following formats:

• 0 l r — update operation, which sets \( a_i = c^{a_i} \) for every \( i \) from \( l \) to \( r \).
• 1 l r — query operation, which asks for \( \sum_{i=l}^{r} a_i \) modulo \( p \).

outputFormat

For each query operation (i.e. operations starting with 1), output a single line containing the result: the sum over the given range modulo \( p \).

sample

5 3 2 1000
1 2 3 4 5
0 2 4
1 1 5
1 2 3

34
12