25721번 - 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$.

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

The first line contains an integer $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 one 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}$.

It is guaranteed that both the sum of $n$ and the sum of $q$ over all tests do not exceed $10^5$.

For each test case:

For each query, output "<" if $A_x$ is lexicographically smaller than $A_y$; output ">" if $A_x$ is lexicographically greater than $A_y$ (in other words, $A_y$ is lexicographically smaller than $A_x$); output "=" if $A_x = A_y$.