时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
临近四级考试，小成准备了一个单词本，会对单词本中的单词进行添加，删除或更改操作。
由于四级单词太多了(其实就是小成懒)，所以小成决定复习时只复习规定区间中字典序最大的单词。
因为小成太懒了，懒的做以上操作，所以现在需要你编程帮助他来完成以上操作，维护单词本并且给出小成需要复习的单词。
给出两个数n，q，分别表示当前单词本上已有的单词数量和询问次数，接下来一行输入n个单词，接下来q次询问，对于每次询问，有以下两种方式：
- 更改('U')：给出位置(下标从1开始)和一个单词(字符串)。
- 查询('Q')：给出两个数 l , r 表示在区间 [l , r] 中查找字典序最大的单词，并将其输出出来。若该区间无单词，则输出“null”。
输入描述:
第一行两个数 n，q；
接下来n行n个字符串；
接下来q行：
输入 U 表示更改，接下来给出一个字符串x；
输入 Q 表示查询，后面两个数 l，r；
输出描述:
一行一个字符串，表示小成需要背的单词(按照查询顺序输出)；
示例1
输入
复制
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
示例2
输入
复制
5 5
investment
cure
habitat
accent
appealing
Q 1 3
U 7 zero
Q 1 9
U 3 bat
Q 2 4
备注:
众所周知，ACM组长对待组员十分善良
所以决定将刚学会的线段树出道题目作为此次选拔赛的压轴题
因为组长实在过于善良，本题不涉及懒标记(^-^)
1 ≤ n , q ≤ 10⁵；
1 ≤ l , r ≤ 10⁵；
字符串长度保证小于等于20（且保证是四级单词【手动狗头】）；