Majority Element Queries

You are given an array of N integers and Q queries. There are two types of queries:

• Type 1: Update the element at a given index to a new value.
• Type 2: Find the majority element in a subarray defined by indices L to R (inclusive).

An element is considered a majority element if it appears more than \(\lfloor\frac{R-L+1}{2}\rfloor\) times in the specified subarray. If no such element exists, output \(-1\).

Input is read from stdin and output is written to stdout.

inputFormat

The first line contains two integers, \(N\) and \(Q\), separated by a space.

The second line contains \(N\) space-separated integers representing the initial array.

Each of the next \(Q\) lines contains a query in one of the following formats:

• 1 i x — Update the element at position \(i\) (1-indexed) to x.
• 2 L R — Query for the majority element in the subarray from index \(L\) to \(R\) (1-indexed).

outputFormat

For each query of type 2, output the majority element if it exists; otherwise, output \(-1\). Each answer should be printed on a new line.

## sample

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

2
-1
-1
-1

</p>