Tree Height Operations on Road Segments

You are given a straight road with n consecutive segments (numbered from 1 to n). Initially, each segment contains a tree with height \(h_i\). Then, you need to process \(q\) operations of the following types:

• 1 l r c: Increase the height of all trees in segments \(l\) to \(r\) by \(c\) units.
• 2 l r h: Use a knife fixed at height \(h\) to trim the trees in segments \(l\) to \(r\); for each tree, if its height is greater than \(h\), it is reduced to \(h\).
• 3 l r h: Plant a new tree with height \(h\) in every segment from \(l\) to \(r\). Note that a segment may contain multiple trees.
• 4 l r: Query and output the maximum tree height among all trees in segments \(l\) to \(r\).

Note: Tree heights are measured relative to a baseline and can be negative.

inputFormat

The first line contains two integers \(n\) and \(q\) — the number of segments and the number of operations.

The second line contains \(n\) integers \(h_1, h_2, \ldots, h_n\) representing the initial heights of the trees in each segment.

Each of the next \(q\) lines contains an operation in one of the following formats:

1 l r c
2 l r h
3 l r h
4 l r

outputFormat

For each operation of type 4, output the maximum tree height in the specified range on a new line.

sample

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

5
8
5