考虑两个长度为 $n$ 的排列 $a$ 和 $p$。初始时，对于所有 $1 \le i \le n$，有 $a_i = p_i = i$。令 $A$ 为一个排列序列，满足 $A_1 = a$，且对于所有 $i \ge 1$ 和 $1 \le j \le n$，有 $A_{i,j} = A_{i-1, p_j}$。

有三种类型的操作，其中 $x$ 和 $y$ 为正整数：

1. swap_a x y：交换 $a_x$ 和 $a_y$，其中 $1 \le x, y \le n$；
2. swap_p x y：交换 $p_x$ 和 $p_y$，其中 $1 \le x, y \le n$；
3. cmp x y：按字典序比较 $A_x$ 和 $A_y$。

对于每种类型 3 的操作，输出 $A_x$ 和 $A_y$ 之间的关系。当且仅当存在一个下标 $i$，使得 $s_i < t_i$ 且对于所有 $1 \le j < i$ 都有 $s_j = t_j$ 时，称排列 $s$ 字典序小于排列 $t$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示排列的长度和操作次数。

接下来的 $q$ 行，每行包含一个字符串 $f$ 和两个整数 $x$ 和 $y$，表示一个操作。字符串 $f$ 为 swap_a、swap_p 或 cmp 中的一种。如果 $f$ 为 swap_a 或 swap_p，则 $1 \le x, y \le n$。如果 $f$ 为 cmp，则 $1 \le x, y \le 10^{18}$。

保证所有测试数据中 $n$ 的总和与 $q$ 的总和均不超过 $10^5$。

输出格式

对于每组测试数据：

对于每个查询，如果 $A_x$ 字典序小于 $A_y$，输出 <；如果 $A_x$ 字典序大于 $A_y$（换句话说，$A_y$ 字典序小于 $A_x$），输出 >；如果 $A_x = A_y$，输出 =。

样例

输入 1

2
5 5
cmp 1 2
swap_p 1 2
cmp 1 2
swap_a 1 2
cmp 1 2
1 1
swap_a 1 1

输出 1

=
<
>