E. Exponentiation
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Image by callmetak on Freepik

In her spare time, Zoe develops an online calculator. Unfortunately, the calculator was targeted by a denial-of-service attack last week. The attacker created a lot of integer variables, exponentiated them with each other, and tried to do a bunch of comparisons. The huge integers were too much for the server to handle, so it crashed. Before Zoe fixes the issue, she decides to actually perform the calculations that the attacker requested.

There are $$$n$$$ integer variables $$$x_1, x_2, \dots, x_n$$$. At the start, each variable is set to $$$2023$$$. You have to perform $$$m$$$ instructions of the following two types:

  • Operations, of the form "! $$$i$$$ $$$j$$$", where $$$i \neq j$$$. This means that $$$x_i$$$ gets set to $$$x_i^{x_j}$$$.
  • Queries, of the form "? $$$i$$$ $$$j$$$", where $$$i \neq j$$$. This means that you should print '>' if $$$x_i$$$ is greater than $$$x_j$$$, '=' if $$$x_i$$$ is equal to $$$x_j$$$, and '<' if $$$x_i$$$ is smaller than $$$x_j$$$.

Consider the first sample. After the $$$5$$$ operations, the values of the variables are:

$$$$$$ x_1=\left({2023}^{2023}\right)^{{2023}^{2023}},\, x_2=\left({2023}^{{2023}^{2023}}\right)^{2023},\, x_3={2023},\, x_4={2023}^{2023}. $$$$$$

Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 1000$$$, $$$1 \leq m \leq 1000$$$), the number of variables and the number of instructions.
  • $$$m$$$ lines, each containing a character $$$c$$$ (either '!' or '?') and two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$), describing the instructions.
Output

For every query in the input, output its answer.

Examples
Input
4 8
! 1 4
! 2 1
! 4 3
! 1 4
! 2 3
? 3 4
? 2 4
? 2 1
Output
<
>
=
Input
4 9
! 2 4
! 1 2
? 3 1
? 1 2
! 2 3
? 1 2
! 1 3
! 3 2
? 1 3
Output
<
>
>
<