Background

Along a river basin called River $R$, there lives an ancient ethnic group $Z$. They have lived by the river for generations, and have built a brilliant civilization there.

The $Z$ people built many buildings along the banks of River $R$. Recently, they became keen on comparing with each other. They always compete to see whose building is the most “unique”.

Fortunately, the $Z$ people have a similar understanding of what “unique” means. They quickly gave every building a score, making it easy to decide which one is the most unique.

So, based on the scores, they soon selected the most unique building, called the Great Wonder. Later, they also selected the 2nd most unique, 3rd most unique, $\ldots$, and the 7th most unique buildings, called the Second Great Wonder, Third Great Wonder, $\ldots$, Seventh Great Wonder, respectively.

Recently, they started selecting the 8th most unique building, and plan to name it the Eighth Great Wonder. During the selection, they ran into some problems.

Problem Description

First, the $Z$ tribe keeps developing. Some buildings are demolished and new ones are built. The uniqueness value of a new building is different from the original one, which makes the selection less straightforward.

Second, each person in the $Z$ tribe may live within a different range. The buildings they have seen are not all the buildings, and they insist that the 8th most unique building they see is the Eighth Great Wonder.

The leader of the $Z$ tribe has been troubled by this recently. He fears that disagreements may cause division within the tribe. He comes to you, hoping to first understand what “wonder” the people themselves believe in.

Now you are given the changes of buildings around River $R$, and during these changes, the living ranges of some people. Please write a program to find the uniqueness value of the Eighth Great Wonder as believed by each person.

Input Format

The first line contains two integers $L$, $N$, representing the length of the river and the number of pieces of information you need to process. Initially, there are no buildings along the river banks, or equivalently, all uniqueness values are $0$. The next $N$ lines each contain one piece of information you need to process.

If the information is C p x, it means that at position $p$ $(1 \le p \le L)$ in the basin, a building is constructed with uniqueness value $x$. If there was a building at this position before, the original building will be demolished.

If the information is Q a b, it means a person’s living range is from position $a$ to position $b$ of the river (including $a$ and $b$, $a \le b$). At this time, you need to compute the uniqueness value of the Eighth Great Wonder within this interval and output it. If the Eighth Great Wonder cannot be found, output $0$.

Output Format

For each piece of information of type $Q$, output one integer, representing the uniqueness value of the Eighth Great Wonder in the interval.

10 15
C 1 10
C 2 20
C 3 30
C 4 40
C 5 50
C 6 60
C 7 70
C 8 80
C 9 90
C 10 100
Q 1 2
Q 1 10
Q 1 8
C 10 1
Q 1 10

0
30
10
20

Hint

For $20\%$ of the testdata, $1 \le L \le 1000$, $1 \le N \le 1000$.

For $40\%$ of the testdata, $1 \le L \le 10000$, $1 \le N \le 10000$.

For $100\%$ of the testdata, $1 \le L \le 10^5$, $1 \le N \le 10^5$. All uniqueness values are non-negative integers not exceeding $10^9$.

Lanqiao Cup 2019 National Contest Group B, Problem I.

Translated by ChatGPT 5