Problem C
Friend of a Friend

Image by PSDgraphics; Used with permission

Snark Muckleburg, CEO of renowned social network Friendface, wants to keep a close eye on how connected the users of his platform are. You have been assigned to write a monitoring program that tracks the connection status of every pair of users, namely whether they are Friendface friends, or, if not, whether they are indirectly connected by a sequence of friend relations. Your program needs to process two kinds of commands. The command

friend x y

means the database should be updated to reflect the fact that users $x$ and $y$ are now friends, and the command

status x y

asks for the status of the relationship between users $x$ $\textrm{and}~ y,$ for which there are three possible responses:

1. $x$ and $y$ are friends (directly connected)

2. $x$ and $y$ are not friends but are indirectly connected, meaning there is a sequence of $k \geq 1$ users, $u_1, \ldots , u_k,$ such that $x$ is friends with $u_1,$ $u_i$ is friends with $u_{i+1}$ for $1 \leq i < k,$ and $u_k$ is friends $\textrm{with}~ y$

3. $x$ and $y$ are not connected, directly or indirectly

Since the $n$ users of the Friendface platform are indexed $0, 1, \ldots , (n-1),$ the values $x$ and $y$ in each of the commands are numbers in this range.

Can you complete this task, thereby increasing the already obscene net worth of Snark Muckleburg?

Input

The first line of input contains two space-separated integers, $n~ \textrm{and}~ m,$ the number of Friendface users and the number of commands you need to process, respectively $(2 \leq n \leq 200\, 000,$ $1 \leq m \leq 400\, 000).$ This is followed by $m$ lines, each containing a single command. The commands are the same as above, but given in a compact form. A line containing $\texttt{f}~ x~ y$ means that users $x$ and $y$ are now friends, and a line containing $\texttt{s}~ x~ y$ asks for the status of users $x$ and $y.$ In each case, $0 \leq x,y \leq (n-1),$ with $x \neq y,$ and consecutive elements in a command are separated by a single space. There is at least one $\texttt{s}~ x~ y$ command, and no two $\texttt{f}~ x~ y$ commands will involve the same pair of users.

Output

Note that the $m$ commands should be processed in order, from first to last. After reading a $\texttt{f}~ x~ y$ command, your program should print no output. After reading a $\texttt{s}~ x~ y$ command, your program should print a line containing either $x~ \texttt{+}~ y$ if $x$ and $y$ are friends, $x~ \texttt{-}~ y$ if $x$ and $y$ are not friends but are indirectly connected by a path of friends as described above, or $x~ \texttt{?}~ y$ if $x$ and $y$ are not directly or indirectly connected. Separate consecutive elements in each line of output by a single space. In each case, the status of $x$ and $y$ is based on the commands processed so far.

3 6
f 0 1
s 0 1
s 1 2
f 2 1
s 1 2
s 0 2

0 + 1
1 ? 2
1 + 2
0 - 2

8 16
f 0 1
s 0 7
f 1 2
s 1 2
f 2 3
s 0 3
f 3 0
s 0 3
f 4 5
f 5 6
s 0 6
f 6 7
s 0 7
f 7 4
f 3 4
s 0 7

0 ? 7
1 + 2
0 - 3
0 + 3
0 ? 6
0 ? 7
0 - 7