#102770. [BZOJ 2770] YY的Treap

志向远大的 YY 小朋友在学完快速排序之后决定学习平衡树，左思右想再加上 SY 的教唆，YY 决定学习 Treap。

Treap 是一种平衡树，通过对每个节点随机分配一个 ，同时保证这棵平衡树关于 是一个小根堆以保证效率。

友爱教教父 SY 如砍瓜切菜般教会了 YY 小朋友 Treap。这时候不怎么友爱的 510 跑了出来，他问了 YY 小朋友一个极不和谐的问题：怎么求 Treap 中两个点之间的路径长度。

YY 秒了之后决定把这个问题交给你来做，但只要求出树中两点的 LCA。

第一行两个整数 。
第二行 个整数表示每个元素的 。
第三行 个整数表示每个元素的 。
接下 行，每行一条命令：

• I A B，插入一个元素， 为 ， 为 。
• D A，删除一个元素， 为 。
• Q A B，询问 分别为 和 结点的 LCA 的 。

对于每个 Q 输出一个整数。

样例输入 #1

2 2
1 2
4 5
Q 1 2
I 3 3

样例输出 #1

1

对于 的数据，，，其余整数均不超过 int 的范围。
数据保证任意时刻树中 和 均不相同。