No submission language available for this problem.

题目描述

给你 $n$ 个小球，从左到右编号依次为 $1,2,3,4,5,6.........n$ ，并规定小球 $1$ 的左边的球号为 $n$，小球 $n$ 的右边的球号为 $1$.

现在有以下 $4$ 种操作：

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 为 Q 时，且 x 为 $1$，则询问小球 y 右边的球号

当 s 为 Q 时，且 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$