408003 - 星际争霸

第一次大规模星际演习正式开始,由红方琳琳,蓝方小光各率领十万余艘太空战舰模拟对抗。 小光将星域战场划分成30 000列,每列依次编号为1,2,…,30 000。之后,他把自己的战舰也依次编号为1,2,…,30 000,让第i号战舰处于第i列(i=1,2,…,30 000),形成“一字长蛇阵”,诱敌深入。这是初始阵形。当进犯之敌到达时,小光会多次发布合并指令,将大部分战舰集中在某几列上,实施密集攻击。合并指令为M i j,含义为让第i号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 但琳琳早已在战略上取得了主动。在交战中,她可以通过庞大的情报网络随时监听小光的舰队调动指令。 在小光发布指令调动舰队的同时,琳琳为了及时了解当前小光的战舰分布情况,也会发出一些询问指令:C i j。该指令会询问电脑,小光的第i号战舰与第j号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。 作为一个资深的高级程序员,你被要求编写程序分析小光的指令,以及回答琳琳的询问。

输入

输入的第1行有1个整数T(1≤T≤500 000),表示总共有T条指令。 以下有T行,每行有一条指令。指令有两种格式: (1) M i j :i和j是两个整数(1≤i,j≤30 000),表示指令涉及的战舰编号。该指令是琳琳监听到的小光发布的舰队调动指令,并且保证第i号战舰与第j号战舰不在同一列。 (2) C i j :i和j是两个整数(1≤i,j≤30 000),表示指令涉及的战舰编号。该指令是琳琳发布的询问指令。

输出

你的程序应当依次对输入的每一条指令进行分析和处理: 如果是小光发布的舰队调动指令,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息; 如果是琳琳发布的询问指令,你的程序要输出一行,仅包含一个整数,表示在同一列上,第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上,则输出-1。

样例

输入

4
M 2 3
C 1 2
M 2 4
C 4 2

输出

-1
1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题