Lexicographic Comparison

Consider $a$ and $p$, two permutations of length $n$. Initially, $a\_i=p\_i=i$ for all $1\le i\le n$. Let $A$ be a sequence of permutations such that $A\_1=a$ and $A\_{i,j}=A\_{i-1,p\_j}$ for all $i\ge 1$ and $1\le j\le n$.

There are three types of operations, where $x$ and $y$ are positive integers:

1. swap_a $x$ $y$: swap $a\_x$ and $a\_y$, where $1\le x, y\le n$.
2. swap_p $x$ $y$: swap $p\_x$ and $p\_y$, where $1\le x, y\le n$.
3. cmp $x$ $y$: compare $A\_x$ with $A\_y$ lexicographically.

For each operation of type 3, output the relationship between $A\_x$ and $A\_y$. A permutation $s$ is lexicographically smaller than a permutation $t$ if and only if there exists an index $i$ such that $s\_i<t\_i$ and $s\_j=t\_j$ for all $1\le j<i$.

The first line contains an integer $T$ ($1\le T\le 10^5$), the number of test cases. For each test case:

The first line contains integers $n$ and $q$ ($1\le n, q\le 10^5$), the length of the permutations and the number of operations.

Each of the following $q$ lines contains a string $f$ and two integers $x$ and $y$ representing an operation. The string $f$ is one of swap_a, swap_p, and cmp. If $f$ is swap_a or swap_p, then $1 \le x, y \le n$. If $f$ is cmp, then $1 \le x, y \le 10^{18}$.

The sum of $n$ and the sum of $q$ over all tests do not exceed $10^5$.

For each test case, output one line per cmp query. Output < if $A\_x$ is lexicographically smaller than $A\_y$, > if $A\_x$ is lexicographically greater than $A\_y$ (that is, $A\_y$ is lexicographically smaller than $A\_x$), and = if $A\_x = A\_y$.