Forest Frequency Queries

You are given an array representing a forest where each element is a positive integer indicating the species of a tree. The forest is 1-indexed initially.

You will receive q operations. There are two types of operations:

• Update Query: 1 i x — update the i-th tree in the forest to species x.
• Frequency Query: 2 l r — determine the most frequent tree species in the subarray from index l to r (both inclusive). In case of a tie, choose the smallest species number.

Note: The indices i, l, and r are all 1-indexed. For every frequency query, output the result on a new line. If a query is an update, no output is produced.

Mathematical representation:

For a frequency query we need to compute:

[ \text{MostFrequent}(l, r) = \min\left{ x ;:; x \in \arg\max_{y}; f(y, l, r) \right} ]

where \(f(y, l, r)\) is the frequency of species \(y\) in the subarray spanning from \(l\) to \(r\).

inputFormat

The input is read from stdin and has the following format:

 n q
 a1 a2 ... an
 op1 ...
 opq

Here:

• n is the number of trees in the forest.
• q is the number of queries.
• The next line contains n integers representing the initial species of each tree.
• Each of the following q lines represents an operation and has one of the two formats:
• For an update query: 1 i x
• For a frequency query: 2 l r

outputFormat

For each frequency query (operation type 2), output the result (the most frequent species in the query range) on a new line to stdout. No output should be produced for update queries.

## sample

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

1
1
1
1

</p>