Problem Description

In Minecraft, one way to become stronger is to have armors and weapons enchanted. Enchanted books play a crucial role.

The most important attribute of an enchanted book is its level. The higher the level, the better the book. Two books of the same level \( l \) can be merged into a new book (the original two will disappear). The level of the new book is \( l+1 \), and the merger costs \( 2^{l+1} \).

Now, Steve has \( n \) enchanted books numbered from 1 to \( n \). Initially, the \( i \)-th book's level is \( a_i \). Steve asks you to help him with the following four operations:

1. Given two integers \( l, r \) ( \( 1 \le l \le r \le n \) ), calculate the maximum level Steve can reach by merging books numbered from \( l \) to \( r \).
2. Given three integers \( l, r \) ( \( 1 \le l \le r \le n \) ) and \( k \), follow these steps:
   - Step 1: Steve merges all the books numbered from \( l \) to \( r \) until there are no two books with the same level.
   - Step 2: Steve adds one new book with level \( k \) to the books he gets in Step 1.
   - Step 3: Steve needs to merge the books he gets in Step 2, aiming to maximize the number of merges. Calculate and output the total cost modulo \( 10^9+7 \) in Step 3.
   - Note that, after calculating, the sequence is restored. This operation does NOT actually change the sequence.
3. Given two integers \( pos, k \), Steve changes the level of the book numbered \( pos \) to \( k \).
4. Given one integer \( t \), Steve restores the sequence to the state after the \( t \)-th operation. If \( t=0 \), Steve restores the sequence to the initial state.

Input Format

The first line contains five integers \( n, m, A, p, q \) ( \( 1 \leq n \leq 10^6 \), \( 1 \leq m \leq 10^6 \), \( 1 \leq A \leq 19\,260\,817 \), \( 1 \leq p \leq 4 \), \( 1 \leq q \leq 30 \) ).

To avoid large input files, the actual input is constructed using the following strategy:

Function rnd():
\[ A \leftarrow (7A + 13) \bmod 19\,260\,817 \]
return \( A \)

First, \( n \) integers \( a_1, a_2, \cdots, a_n \) are generated sequentially:
\[ a_i \leftarrow rnd() \bmod q + 1 \]

Then, the parameters for all operations are generated.

For each operation, the operation number \( opt \) is generated:
\[ opt \leftarrow rnd() \bmod p + 1 \]

Depending on the operation number, different methods are used to generate parameters:

• For operation 1: Generate \( l \) and \( r \) using:
• \( L \leftarrow rnd() \bmod n + 1 \)
• \( R \leftarrow rnd() \bmod n + 1 \)
• \( l \leftarrow \min(L, R) \)

• \( r \leftarrow \max(L, R) \)

• For operation 2: Generate \( l, r, \) and \( k \) using:

• \( L \leftarrow rnd() \bmod n + 1 \)
• \( R \leftarrow rnd() \bmod n + 1 \)
• \( l \leftarrow \min(L, R) \)
• \( r \leftarrow \max(L, R) \)

• \( k \leftarrow rnd() \bmod q + 1 \)

• For operation 3: Generate \( pos \) and \( k \) using:

• \( pos \leftarrow rnd() \bmod n + 1 \)

• \( k \leftarrow rnd() \bmod q + 1 \)

• For operation 4: Generate \( t \) using:

• \( t \leftarrow rnd() \bmod i \)

Here, \( i \) represents the \( i \)-th operation.

Output Format

For each operation 1 and 2, output a single line with an integer representing the answer to operation 1 and 2 modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

6 3 2 1 3

Sample Output #1

1
3
2

Sample Input #2

10 15 5 4 7

Sample Output #2

0
9
9
0
64
0
0

Notes/Hints

Function max means the maximum value among the parameters. Function min means the minimum value among the parameters.

In example 1, the initial books are \([1, 2, 3, 1, 2, 3]\). The three operations' ranges are \([4, 4]\), \([1, 3]\), and \([4, 5]\).

见题面 Input 部分

见题面 Output 部分