교차하지 않는 기사의 여행

중세 왕국 수비니움은 일직선으로 길게 뻗은 강의 변에 N개의 성과 M개의 자연경관이 있는 것으로 유명하다. 수비니움 강은 매우 곧아서 이웃 왕국보다 미터법을 일찍 도입했다. 국왕은 서쪽 국경의 좌표를 1, 동쪽 국경의 좌표를 $10^9$으로 두고 나머지 지역의 좌표를 계산했다. 강의 남쪽인지 북쪽인지, 그리고 좌표에 따라 수비니움 왕국은 U1부터 U1000000000, D1부터 D1000000000까지 주소를 매겼다.

N명의 기사가 여름휴가를 맞아 강 건너의 자연경관으로 떠나려 한다. 각 기사는 자신의 성에서 선택한 경관까지 배를 타고 곧바로 건넌다. 기사들은 다른 기사의 방해 없이 여행하고 싶어 하므로, 모두 서로 다른 경관으로 가야 하며 여행 경로는 교차하면 안 된다.

북쪽에 사는 기사도 있고 남쪽에 사는 기사도 있어서, 주의하지 않으면 경로가 쉽게 꼬인다. N명의 기사 모두가 강 건너의 경관으로 갈 수 있는 방법을 찾고, 그런 방법이 있다면 기사마다 갈 곳을 배정하는 프로그램을 작성하라.

첫 번째 줄에는 기사의 수 N과 자연경관의 수 M이 주어진다. ($1 \le N \le 10^4$, $1 \le M \le 10^6$)

두 번째 줄에는 1, 2, ..., N번째 기사가 사는 성의 주소가 주어진다.

세 번째 줄에는 1, 2, ..., M번째 자연경관의 주소가 주어진다.

주소는 [방향][좌표] 형태이며, $1 \le$ 좌표 $\le 10^9$이다. 모든 기사와 자연경관은 서로 다른 곳에 있다.

N명의 기사에게 여행지를 배정할 수 없다면 -1을 출력한다.

배정할 수 있다면 1, 2, ..., N번째 기사가 가야 할 자연경관의 번호를 출력한다.

가능한 답이 여러 개이면 그중 아무거나 출력한다.