Botanist Lab: Range Update and Query

Bob, a dedicated botanist, is experimenting with an array of plants, all initially having a health score of 0. There are N plants arranged in a row. Bob performs Q operations on these plants. Each operation is of one of two types:

1. Update Operation: Increase the health score of every plant in the range [u, v] by 1.
2. Query Operation: Determine the maximum health score among the plants in the range [u, v].

You are required to process all the Q operations and output the result of each query operation. The operations will be provided via standard input and the output should be printed to standard output.

The update and query operations are meant to be handled efficiently, hinting at the necessity of employing a lazy propagation segment tree. The use of lazy propagation ensures that range updates and queries are processed in (O(\log N)) time complexity per operation on average.

Formally, you are given an integer (N) and an integer (Q). Then (Q) operations follow. For an update operation, the input format is: [ 1\ u\ v ] For a query operation, the input format is: [ 2\ u\ v ] where (1 \leq u \leq v \leq N).

Your task is to implement the functionality to perform these operations and return the result of the query operations in the order they appear.

inputFormat

The first line contains two space-separated integers: (N) (the number of plants) and (Q) (the number of operations). Each of the next (Q) lines contains an operation in one of the following two formats:

For an update operation: 1 u v

For a query operation: 2 u v

For an update operation, increase the health score for every plant in the range ([u, v]) by 1. For a query operation, output the maximum health score in the range ([u, v]).

outputFormat

For each query operation, output a single line containing the maximum health score among the plants in the given range.## sample

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

2
2