410017: GYM103914 G 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$$$.

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

=
<
>