Uncrossed Knights' Tour

The medieval kingdom of Suvinium is known for its N castles and M natural landmarks along the banks of a long, straight river. The Suvinium River is so straight that the kingdom adopted the metric system earlier than its neighbors. The king set the coordinate of the western border to 1 and the eastern border to $10^9$, and computed the coordinates of every other place from there. Based on whether a place lies south or north of the river and on its coordinate, the kingdom assigned addresses from U1 to U1000000000 and from D1 to D1000000000.

N knights want to spend their summer vacation at the natural landmarks across the river. Each knight sails straight from their castle to the landmark they chose. The knights want to travel without interference, so each knight must go to a different landmark, and the travel routes must not cross.

Some knights live in the north and some live in the south, so the routes can easily tangle if they are not planned carefully. Find a way for all N knights to reach landmarks across the river, and if one exists, write a program that assigns a destination to each knight.

The first line contains the number of knights N and the number of natural landmarks M. ($1 \le N \le 10^4$, $1 \le M \le 10^6$)

The second line contains the addresses of the castles of knights 1, 2, ..., N.

The third line contains the addresses of the natural landmarks 1, 2, ..., M.

Each address has the form [direction][coordinate], where $1 \le$ coordinate $\le 10^9$. All knights and landmarks are at different places.

If the N knights cannot all be assigned destinations, print -1.

If they can be assigned, print the numbers of the natural landmarks that knights 1, 2, ..., N must go to.

If several answers are possible, print any one of them.