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 has either one or two types. Depending on these types, the attack does 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 with 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) \times a(i, k)$.

The game prints a message based on the damage multiplier $v$:

You are new to this game and do not know what the table $a$ looks like. You have observed the game output when attacking various Nudgémon with attacks of type 1, and you want to reconstruct the first row of $a$ consistent with those observations.

The first line 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.

Each of the next m lines contains two integers i and j and a character c ($1 \le i, j \le n$, and c is one of x, -, =, +). The character c is the observed effect when attacking a Nudgémon with types i and j. If i = j, the Nudgémon has only one type.

Output a single line with n characters. The i-th character describes the effect of attacking a Nudgémon of type i with an attack of type 1. If several solutions are valid, print any of them. A solution is guaranteed to exist.