Max Building Height After Operations

You are given n buildings with initial heights and m operations. Each operation is represented by three integers l, r, and x, meaning that you should add x to each building's height in the index range [l, r] (1-indexed). After each operation, you need to determine and output the maximum height among all buildings.

Mathematically, let \( h_1, h_2, \dots, h_n \) denote the initial heights of the buildings. For each operation \( (l, r, x) \), update the heights as follows:

[ h_i = \begin{cases} h_i + x, & \text{if } l \le i \le r, \ h_i, & \text{otherwise.} \end{cases} ]

After each operation, compute and output \( \max_{1 \le i \le n} h_i \).

Note: Input is read from standard input and output should be written to standard output.

inputFormat

The first line contains two integers n and m separated by a space, where n is the number of buildings and m is the number of operations. The second line contains n integers representing the initial heights of the buildings. Each of the next m lines contains three integers l, r, and x describing an operation.

outputFormat

Output m integers in one line separated by spaces. Each integer represents the maximum height of the buildings after performing the corresponding operation.## sample

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

7 10 11