题目描述

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

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

友爱教教父 SY 如砍瓜切菜般教会了 YY 小朋友 Treap。这时候不怎么友爱的 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

数据规模与约定

对于 $100\%$ 的数据，$n\leq 10^5$，$m\leq 3\times 10^5$，其余整数均不超过 int 的范围。
数据保证任意时刻树中 $key$ 和 $priority$ 均不相同。