Problem H
Type Charts

You are playing the game Nudgémon, a common element of which is Nudgémon battles. In a battle, you and your opponent each start by sending out a Nudgémon of your choice, and then take turns attacking the opposing Nudgémon.

Each attack has a type (an integer between $1$ and $n$), and the opposing Nudgémon also has either one or two types. Depending on these types, the attack will do different amounts of damage.

When an attack of type $i$ hits a Nudgémon with single type $j$, the attack gets a damage multiplier $a(i,j)$, where $a$ is a type matchup table consisting of entries in $\{ 0, 0.5, 1, 2\} $. If it hits a Nudgémon with double types $j$ and $k$, it gets a damage multiplier of $a(i,j) \cdot a(i,k)$.

Depending on the value $v$ of the damage multiplier, the game will emit different messages:

You are new to this game and do not know what the table $a$ looks like. Trying to learn its first row, you have gathered some observations about the game’s output when attacking various Nudgémon with attacks of type $1$. Now you are trying to reconstruct the first row in a way that is consistent with this data.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^5$), where $n$ is the number of types and $m$ is the number of observations.

Then follow $m$ lines, each containing two integers $i,j$ and a character $c$ ($1 \le i,j \le n$ and $c$ is one of x,-,= or +), where $c$ is the observed effect when attacking a Nudgémon with types $i$ and $j$, as indicated in the table above. If $i = j$, the Nudgémon has just a single type.

Output

Output a single line with $n$ characters, each either x, -, = or +. The $i$th character should describe the effect of attacking a Nudgémon of type $i$ with an attack of type $1$.

If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists.

5 5
1 2 -
2 4 -
4 5 x
2 3 =
3 4 +

=-+=x