Range Mode Query with Updates

Alice has a sequence \(a_1,a_2,\dots,a_n\). She now needs Bob to support two types of operations:

• Query Operation: Given a range \([l, r]\), determine the mode (i.e. the most frequent element) in the subarray \(a_l,a_{l+1},\dots,a_r\). In case of a tie, report the smallest value among those with the maximum frequency.
• Update Operation: Modify the value at a given index \(i\) to a new value \(x\), i.e. set \(a_i=x\).

You are given the initial sequence and then \(q\) operations. Process the operations in order and for each query operation, output the mode of the specified interval.

inputFormat

The first line contains two integers \(n\) and \(q\) (the number of elements in the sequence and the number of operations, respectively). The second line contains \(n\) integers representing the initial sequence \(a_1,a_2,\dots,a_n\). Each of the following \(q\) lines represents an operation in one of the following formats:

• Q l r — a query operation asking for the mode in the subarray from index \(l\) to \(r\) (1-indexed).
• U i x — an update operation which sets \(a_i = x\) (1-indexed).

outputFormat

For each query operation, output a single line containing the mode in the specified interval. If there are multiple values with the same maximum frequency, output the smallest among them.

sample

5 5
1 2 2 3 1
Q 1 5
U 3 1
Q 1 3
U 5 2
Q 1 5

1
1
1