Coin Statements

Time limit1sMemory limit128 MB

Summary

Given L positions and N clauses of the form (position i is X) OR (position j is Y), reconstruct any assignment satisfying all clauses, or report impossibility (2-SAT).

Level: Medium6 of 10
Topics: Graph, DFS, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

Output

Print one sequence that satisfies every statement.

If no such sequence exists, print -1.

The valid sequence does not have to be unique.

Examples3

Example 1
Input
```
2
3
1 P 2 G
1 G 2 P
1 P 2 P
```
Expected output
```
PP
```
Example 2
Input
```
3
3
1 P 2 G
2 G 3 P
1 P 3 P
```
Expected output
```
PGP
```

Example 3

Input

3
6
1 G 2 G
2 G 3 G
1 G 3 G
2 P 3 P
1 G 2 P
1 P 3 G

Expected output

GPG