시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (추가 시간 없음) 1024 MB 27 6 6 54.545%

문제

중세 왕국 수비니움은 일직선으로 뻗은 강의 변에 N개의 성과 M개의 자연경관이 있는 것으로 유명하다. 수비니움 강은 매우 올곧아서 다른 왕국에 비해 미터법이 일찍 발달했는데 국왕은 서쪽 국경의 좌표를 1으로 두고 동쪽 국경의 좌표를 109으로 두어 나머지 지역의 좌표를 계산하였다. 강을 기준으로 남쪽인지 북쪽인지에 따라, 그리고 지역의 좌표에 따라 수비니움 왕국은 U1 - U1000000000D1 - D1000000000의 주소를 매겼다.

knight

N명의 기사들은 여름 휴가철이 되어 강 건너에 있는 자연경관으로 여행을 가려고 한다. 기사들은 자신의 성에서 원하는 여행지까지 배를 타고 곧바로 건너가는데, 곧게 뻗은 강만큼이나 직설적인 성격을 갖고 있어 일직선으로 강을 건너간다. 기사들은 다른 기사들로부터 방해받지 않고 여행하기를 원하므로 기사들은 서로 다른 지역으로 여행을 가야 하며 기사들의 여행경로는 교차하면 안 된다.

어떤 기사들은 북쪽에 살고 있고 어떤 기사들은 남쪽에 살고 있어서 자칫 잘못하면 경로가 꼬일 수 있다. N명의 기사들이 모두 건너편의 자연경관으로 떠날 수 있는 방법이 있는지 찾고, 있다면 기사들이 갈 여행지를 배정하는 프로그램을 작성하여라.

입력

입력의 첫 번째 줄에는 기사의 수 N, 자연경관의 수 M이 주어진다. (1 ≤ N ≤ 104, 1 ≤ M ≤ 106)

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

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

주소는 [방향][좌표] (1 ≤ 좌표 ≤ 109) 형태로 주어지며 모든 기사와 자연경관은 서로 다른 곳에 있다.

출력

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

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

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

예제 입력 1

4 5
U1 D3 U3 U4
D1 D2 U2 D4 D5

예제 출력 1

1 3 4 5