H. Neogene Warehouse
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

With the rise of mammoths and mastodons, the animals are trying to learn from the lessons of their ancestors. They have decided the best way to store all their food is in a humongous warehouse, where people regularly come and go. Jeff Bezoic is now trying to figure out how to keep up with all of this traffic!

The warehouse is conveniently split up into 26 sectors labeled from 'A' to 'Z'. Mr. Bezoic has also come up with a way to categorize all the traffic into two categories of people:

  • Inventory: An animal will simply come in to make note of the amount of stock in a sector, and then go on with their day.
  • Delivery: An animal will come in and modify a sector (either increasing or decreasing the food in it), and then leave.

Jeff was originally given a list of all the traffic that would be occurring the next day. Every entry in the log contains the ID of the person, their category (Inventory or Delivery), and what sector of the warehouse they're going to. Complications have arose in the warehouse, however, such that a person cannot enter the warehouse more than once a day. That is, once a worker enters, they must do all of their inventory and delivery before leaving. Jeff is fine with reorganizing the log to let these workers know ahead of time, but there are certain requirements he needs to make sure of:

  • If the original log has Worker 'A' doing inventory before Worker 'B' does delivery in the same warehouse sector, 'A' must come before 'B' in the new log, so that 'A' isn't affected by modifications that should come later.
  • If the original log has Worker 'A' doing delivery before Worker 'B' does inventory in the same warehouse sector, 'A' must also come before 'B' so that 'B' records the right inventory.

Note that once a new order is decided, a worker will come in and do all their tasks in the same order as they would have in the original larger log.

With so many potential workers, Jeff naturally wants to automate this as much as possible. However, he wants the order to be as lexicographically smallest$$$^\dagger$$$ possible. Can you help him out?

$$$^\dagger$$$ Note that all orderings will be a permutation of the numbers from $$$1$$$ to $$$n$$$, so I will define it here along that definition. If permutation $$$a$$$ is lexicographically smaller than permutation $$$b$$$, $$$a[i] \lt b[i]$$$ in the first position where $$$a[i] \ne b[i]$$$.

Input

The first line of input will contain two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 10^5$$$, $$$n \le m \le 2n$$$), the number of unique workers and the number of entries in the original log respectively.

The next $$$m$$$ lines will be in the form $$$x$$$ $$$c$$$ $$$d$$$. $$$x$$$ will be the ID of the worker ($$$1 \le x \le n$$$), $$$c$$$ is the warehouse sector being visited (an uppercase letter from 'A' to 'Z'), and $$$d$$$ is either 'I' (inventory) or 'D' (delivery).

It is guaranteed all $$$n$$$ IDs will appear in the list of $$$m$$$ logs.

Output

Output a space-separated list of $$$n$$$ integers, which represents the lexicographic smallest ordering that satisfies all of the original log's orderings. If no such ordering exists, simply output $$$-1$$$.

Examples
Input
3 5
1 A I
2 B I
3 B I
2 B D
2 A D
Output
1 3 2
Input
3 6
1 A I
2 B I
3 B I
2 B D
2 A D
3 B I
Output
-1
Note

In the first test case, the 3rd and 4th logs force $$$3$$$ before $$$2$$$, while the 1st and 5th force $$$1$$$ before $$$2$$$. The two possible orderings are $$$[1, 3, 2]$$$ and $$$[3, 1, 2]$$$.

In the second test case, the 3rd and 4th logs force $$$3$$$ before $$$2$$$. However, the 4th and 6th logs force $$$2$$$ before $$$3$$$. This cycle causes a contradiction, so there is no ordering that keeps the warehouse running smoothly.