Book Reviewers

Interview

Time limit6sMemory limit1024 MB

Summary

Assign ratings from 1 to M to N books so that every <, =, or ≤ comparison holds, or report -1 if no assignment exists.

Level: Medium6 of 10
Topics: Topological sort, Union-find, Dynamic programming
Solved: No attempts yet

Problem

A book reviewer has to review $N$ books. Each review ends with the book being given a rating on a scale from $1$ to $M$ . Choosing an absolute rating for each book directly is hard, so the reviewer finds it much easier to compare two books at a time and state which one is better.

The reviewer has numbered the books with integers from $1$ to $N$ and wants to determine their ratings $a_1, a_2, \dots, a_N$ . To do this, the reviewer has made $R$ comparisons that describe the relation between $a_i$ and $a_j$ for some pairs of books $i, j$ .

The reviewer is satisfied with any rating assignment as long as all requirements from the comparisons are met. Help the reviewer find such an assignment.

Input

The first line contains three integers $N$ ( $1 \leq N \leq 100000$ ), $M$ ( $1 \leq M \leq 100000$ ), and $R$ ( $1 \leq R \leq 500000$ ), which are the number of books, the highest possible rating, and the number of comparisons.

Then follow $R$ lines, each describing a relation that must hold. Each line has the format <i> <relation> <j>, meaning that $a_i$ <relation> $a_j$ must hold. $i$ and $j$ are integers between $1$ and $N$ , with $i \neq j$ . The relation is one of the strings <, =, or ≤. No pair of books is compared more than once.

Output

Print a list of integers $a_1, a_2, \ldots, a_N$ such that every relation holds and every number lies in the range $[1, M]$ . If there are several solutions, print any of them. If it is impossible, print $-1$ .

Hint

In the first sample input, 1 2 1 3 3 is a valid solution. This can be verified by checking that all numbers lie in $[1, 3]$ and that they satisfy the four relations $a_1 < a_2$ , $a_2 < a_4$ , $a_3 < a_2$ , and $a_2 < a_5$ .

Examples4

Example 1

Input

Expected output

1 2 1 3 3

Example 2
Input
```
3 10 3
1 < 2
2 < 3
3 < 1
```
Expected output
```
-1
```

Example 3

Input

Expected output

2 1 2 4 3 2

Example 4

Input

7 3 8
1 <= 2
5 = 7
2 <= 7
6 < 1
5 <= 1
2 < 3
6 <= 4
4 = 3

Expected output

2 2 3 3 2 1 2