No submission language available for this problem.

题目描述

体育课上有 $n$ 个学生正在做热身游戏，规则是先将学生进行从左到右进行编号：$1，2，3，4 ... n$ 。然后围成一个环。即 $1$ 号学生的左边是 $n$。

老师会为了锻炼学生的反应力，会以学生的编号进行四种反应力测试。为了简化问题描述，将四种测试如下设计：

• A x y 表示编号为 x 学生移动到编号为 y 的学生左边。
• B x y 表示编号为 x 学生移动到编号为 y 的学生右边。
• Q 1 m 表示询问编号为 m 的学生右边的学生编号。
• Q 0 m 表示询问编号为 m 的学生左边的学生编号。

输入格式

第一行有一个整数 $t$, 表示有 $t$ 组测试数据

随后每一组测试数据第一行是两个整数 $n, m$，其中 $n$ 表示球的个数，$m$ 表示操作的的次数

随后的 $m$ 行，每行有三个数 s x y，s 表示操作的类型，x，y 为小球号。

当 s 为 A 时，学生 x 要移动到学生 y 的左边。

当 s 为 B 时，学生 x 要移动到学生 y 的右边。

当 s 为 Q 时，若 x 为 1，则询问学生 y 右边的编号，若 x 为 0，则询问学生 y 左边的球号。

输出格式

输出每次询问的编号。

样例 #1

样例输入 #1

1
6 3
A 1 4
B 3 5
Q 1 5

样例输出 #1

3

提示

$对于50\%的数据0<n,m<=100$ $另有30\%的数据0<n,m<=10000$ $对于100\%的数据0<n,m<=100000,0<t<=10$