{"raw_statement":[{"iden":"background","content":"在一条 R 河流域，繁衍着一个古老的名族 Z。他们世代沿河而居，也在河边发展出了璀璨的文明。\n\nZ 族在 R 河沿岸修建了很多建筑，最近，他们热衷攀比起来。他们总是在比谁的建筑建得最奇特。\n\n幸好 Z 族人对奇特的理解都差不多，他们很快给每栋建筑都打了分，这样评选谁最奇特就轻而易举了。\n\n于是，根据分值，大家很快评出了最奇特的建筑，称为大奇迹。后来他们又陆续评选了第二奇特、第三奇特、……、第七奇特的建筑，依次称为第二大奇迹、第三大奇迹、……、第七大奇迹。\n\n最近，他们开始评选第八奇特的建筑，准备命名为第八大奇迹。在评选中，他们遇到了一些问题。"},{"iden":"statement","content":"首先，Z 族一直在发展，有的建筑被拆除又建了新的建筑，新建筑的奇特值和原建筑不一样，这使得评选不那么容易了。\n\n其次，Z 族的每个人所生活的范围可能不一样，他们见过的建筑并不是所有的建筑，他们坚持他们自己所看到的第八奇特的建筑就是第八大奇迹。\n\nZ 族首领最近很头疼这个问题，他害怕因为意见不一致导致 Z 族发生分歧。他找到你，他想先了解一下，民众自己认为的奇迹是怎样的。\n\n现在告诉在 R 河周边的建筑的变化情况，以及在变化过程中一些人的生活范围，请编程求出每个人认为的第八大奇迹的奇特值是多少。"},{"iden":"input","content":"输入的第一行包含两个整数 $L$, $N$，分别表示河流的长度和要你处理的信息的数量。开始时河流沿岸没有建筑，或者说所有的奇特值为 $0$。接下来 $N$ 行，每行一条你要处理的信息。\n\n如果信息为 `C p x`，表示流域中第 $p$ 个位置 $(1 \\le p \\le L)$ 建立了一个建筑，其奇特值为 $x$。如果这个位置原来有建筑，原来的建筑会被拆除。\n\n如果信息为 `Q a b`，表示有个人生活的范围是河流的第 $a$ 到 $b$ 个位置（包含 $a$ 和 $b$，$a \\le b$），这时你要算出这个区间的第八大奇迹的奇特值，并输出。如果找不到第八大奇迹，输出 $0$。"},{"iden":"output","content":"对于每个为 $Q$ 的信息，你需要输出一个整数，表示区间中第八大奇迹的奇特值。"},{"iden":"note","content":"对于 $20\\%$ 的评测用例，$1 \\le L \\le 1000$，$1 \\le N \\le 1000$。\n\n对于 $40\\%$ 的评测用例，$1 \\le L \\le 10000$，$1 \\le N \\le 10000$。\n\n对于 $100\\%$ 的评测用例，$1 \\le L \\le 10^5$，$1 \\le N \\le 10^5$。所有奇特值为不超过 $10^9$ 的非负整数。\n\n蓝桥杯 2019 年国赛 B 组 I 题。"}],"translated_statement":null,"sample_group":[["10 15\nC 1 10\nC 2 20\nC 3 30\nC 4 40\nC 5 50\nC 6 60\nC 7 70\nC 8 80\nC 9 90\nC 10 100\nQ 1 2\nQ 1 10\nQ 1 8\nC 10 1\nQ 1 10","0\n30\n10\n20\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}