Sequence Operations and Maximum Query

You are given a sequence \(a[1\ldots n]\) of length \(n\). The sequence supports the following three types of operations:

• Operation 1: Given an interval \([l,r]\), change every number in the interval to \(x\). (Assignment update)
• Operation 2: Given an interval \([l,r]\), add \(x\) to every number in this interval. (Increment update)
• Operation 3: Given an interval \([l,r]\), output the maximum value within the interval. (Query)

Note: All formulas are represented in \( \LaTeX \) format. For example, the sequence is denoted as \(a\) and the interval by \([l,r]\).

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 representing the initial sequence \(a[1\ldots n]\).

Each of the following \(m\) lines describes an operation in one of the following formats:

• For operations of type 1 and 2: op l r x (where op is 1 or 2).
• For operations of type 3: op l r (where op is 3).

Indices are 1-indexed.

outputFormat

For each operation of type 3, output one line containing the maximum value in the specified interval.

sample

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

5
5
4