Enchanted Book Merging in Minecraft

In Minecraft, one way to become stronger is to have your armors and weapons enchanted. Enchanted books play an important role. The most important attribute of an enchanted book is its level. The higher the level is, the better the book is.

Steve has n enchanted books numbered from 1 to n. Initially, the i-th book's level is a_i. You need to process m operations. There are four types of operations:

1. Query Type 1: Given two integers l and r (1 ≤ l ≤ r ≤ n), if you take the books numbered from l to r and repeatedly merge any two books with the same level into a new book with level increased by 1 (i.e. two books of level l become one book of level l+1), what is the maximum level you can achieve? Note that merging is performed greedily so that no two books of the same level remain.

2. Query Type 2: Given three integers l, r (1 ≤ l ≤ r ≤ n) and k, perform the following steps:

   1. Step 1: Consider the books numbered from l to r and merge them until no two books share the same level. (This merging has no cost.)
   2. Step 2: Add one new book with level k to the set obtained from Step 1.
   3. Step 3: Merge the books from Step 2 (using the same process) in such a way that maximizes the number of merges performed. Each time two books of level l are merged into one book of level l+1, it costs \(2^{l+1}\) (in other words, the cost is \(2^{l+1}\) for a merge at level \(l\)). Compute the total cost modulo \(10^9+7\).

   Note: This operation does not permanently change the sequence of books.

3. Update Operation (Query Type 3): Given two integers pos and k, change the level of the book numbered pos to k.

4. Restore Operation (Query Type 4): Given one integer t, restore the sequence of books to its state immediately after the \(t\)-th operation. If \(t = 0\), restore to the initial state.

Merging Process Explanation:

When merging books, if you have two books of level \(l\), they are merged to a single book of level \(l+1\) at a cost of \(2^{l+1}\). This process is repeated until no two books have the same level. For both Query Type 1 and Query Type 2, the merging is done by repeatedly checking for any level with at least two books and merging them.

Input / Output Restore: Only Query Types 1 and 2 produce output. Operations of types 3 and 4 modify (or restore) the sequence, and the effect carries on for subsequent operations (except that Query Type 2 is a simulation which does not affect the sequence permanently).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of books and the number of operations.

The second line contains \(n\) integers \(a_1, a_2, ..., a_n\) where \(a_i\) is the initial level of the \(i\)-th book.

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

• For Query Type 1: 1 l r
• For Query Type 2: 2 l r k
• For Update Operation (Type 3): 3 pos k
• For Restore Operation (Type 4): 4 t

It is guaranteed that the operations are valid and that \(1 \le l \le r \le n\) and \(1 \le pos \le n\). For Query Type 4, \(t\) is between 0 and the number of operations performed so far.

outputFormat

For each Query Type 1 and Query Type 2 operation, output the answer on a single line. For Query Type 1, output the maximum level obtained after merging. For Query Type 2, output the total cost in Step 3 modulo \(10^9+7\).

sample

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

3
0
3