Dynamic Array Query Processing

You are given an array of N integers and are required to process Q queries on this array. The queries are of the following three types:

• Type 1: 1 X Y – Update the array element at position X (1-indexed) to the value Y.
• Type 2: 2 L R – Find and output the maximum value in the subarray from index L to R (inclusive, 1-indexed).
• Type 3: 3 L R Z – Count and output the number of times the integer Z occurs in the subarray from index L to R (inclusive, 1-indexed).

For queries of type 2 and type 3, you must write the result to the standard output. All indices in the queries are 1-indexed.

In mathematical notation, if the array is denoted by \(A=[a_1, a_2, \dots, a_N]\), then:

• For a query of type 2: output \(\max_{L \leq i \leq R} a_i\).
• For a query of type 3: output \(\#\{i \mid L \leq i \leq R \text{ and } a_i = Z\}\).

Your solution should read input from stdin and write output to stdout.

inputFormat

The input is read from stdin in the following format:

Line 1: Two integers N and Q, representing the number of elements in the array and the number of queries, respectively. Line 2: N space-separated integers representing the initial array. The next Q lines: Each line describes a query. The query format is one of the following:

• For update queries: 1 X Y
• For maximum queries: 2 L R
• For count queries: 3 L R Z

Note: The array indices are 1-indexed.

outputFormat

For each query of type 2 and 3, output the result in a new line to stdout.## sample

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

5
10
2
1
10