YY的Treap

题目描述

志向远大的YY小朋友在学完快速排序之后决定学习平衡树，左思右想再加上SY的教唆，YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap（一种平衡树，通过对每个节点随机分配一个priority，同时保证这棵平衡树关于priority是一个小根堆以保证效率）。这时候不怎么友爱的510跑了出来，他问了YY小朋友一个极不和谐的问题：怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你来做，但只要求出树中两点的LCA。

 

---

输入格式

第一行两个整数n，m

第二行n个整数表示每个元素的key

第三行n个整数表示每个元素的priority

接下m行，每行一条命令

I A B，插入一个元素，key为A, priority为B

D A，删除一个元素，key为A

Q A B，询问key分别为A和B的LCA的key

 

---

输出格式

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

 

---

样例输入

2 2

1 2

4 5

Q 1 2

I 3 3

 

 

---

样例输出

1

---

提示

数据保证n<=10^5,m<=3*10^5

其余整数均不超过long的范围

数据保证任意时刻树中key和priority均不相同

---

题目来源

没有写明来源