Problem A
Disjoint Sets (Simple)

Maintain a family of disjoint sets, initially the singletons $ \{ 0\} ,\{ 1\} , \ldots ,\{ n-1\} $, under the following operations:

? (query)

The query operation takes two elements $s$ and $t$ and determines if $s$ and $t$ belong to the same set. More precisely, when $s\in S$ and $t\in T$ then print “1” if $S=T$ and print “0” if $S\neq T$.

= (union)

The union operation takes two elements $s$ and $t$ and creates the union of the two sets containing $s$ and $t$. More precisely, when $s\in S$ and $t\in T$ with $S\neq T$ then $S$ and $T$ are removed from the family and replaced by the set $S\cup T$. (If $S=T$ then nothing happens.)

Note that these operations maintain invariantly that the sets in the family are disjoint.

Input

The input starts with two positive integers $n$, $m$, on the first line. The integer $n$ is the initial number of singletons. The following $m$ lines are of the form “? $s$ $t$” or “= $s$ $t$” representing query and union, respectively. You can assume $0\leq s< n$, $0\leq t< n$, and $m\geq 1$.

Output

For each query, write a single line containing 1 or 0 as described above.

4 9
? 0 1
= 0 1
? 0 1
= 1 2
? 1 2
? 0 3
= 2 3
? 2 3
? 0 3

0
1
1
0
1
1

2 2
= 0 0
? 0 1

0