题目描述

临近英语考试，小成准备了一个单词本，会对单词本中的单词进行添加，删除或更改操作。

由于四级单词太多了(其实就是小成懒)，所以小成决定复习时只复习规定区间中字典序最大的单词。

因为小成太懒了，懒的做以上操作，所以现在需要你编程帮助他来完成以上操作，维护单词本并且给出小成需要复习的单词。

给出两个数$n,q$，分别表示当前单词本上已有的单词数量和询问次数，接下来一行输入$n$个单词，接下来$q$次询问，对于每次询问，有以下两种方式:

1. 更改U:给出位置(下标从1开始)和一个单词(字符串)。
2. 查询Q:给出两个数$l,r$表示在区间$[l,r]$中查找字典序最大的单词，并将其输出出来。若该区间无单词，则输出null

输入格式

第一行两个数$n,q$; 接下来$n$行，每行个字符串;

接下来$q$行:

• 输入U表示更改，接下来给出一个字符串$x$;
• 输入Q表示查询，后面两个数$l,r$.

输出格式

一行一个字符串，表示小成需要背的单词(按照查询顺序输出):

3 6
investment
cure
habitat
Q 1 3
U 7 accent
Q 1 9
Q 3 19
U 4 appealing
Q 2 4

investment
investment
habitat
habitat

5 5
investment
cure
habitat
accent
appealing
Q 1 3
U 7 zero
Q 19
U 3 bat
Q 2 4

investment
zero
cure

数据规模与约定

对于$100\%$的数据：$1 <n,q≤ 100000,1 ≤ l,r < 100000$;

字符串长度保证$\le 20$,且保证是四级单词.