Coin Statements

John and Ted are playing a game with a sequence of coin results.

John puts several coins on a table. He then takes them back one by one and writes down one character for each coin: P if the upper side is heads, and G if the upper side is tails. This creates a random sequence of length L consisting only of P and G.

After that, John makes N statements. Each statement has the form:

the i-th character is X, or the j-th character is Y

Here i and j are different positions, and each of X and Y is either P or G. For every statement John makes, at least one of its two claims is true.

Ted hears only the statements and wants to reconstruct any sequence that could make all of them true. Write a program that finds one such sequence, or determines that none exists.

The first line contains an integer L (2 <= L <= 1000), the length of the sequence.

The second line contains an integer N (1 <= N <= 100000), the number of statements.

Each of the next N lines contains one statement in the following format:

i X j Y

The values satisfy 1 <= i, j <= L, i != j, and both X and Y are either P or G.

Print one sequence that satisfies every statement.

If no such sequence exists, print -1.

The valid sequence does not have to be unique.