시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

2차원 평면에 n(1≤n≤1,000)개의 점으로 이루어진 도형과 m(1≤m≤10,000)개의 사각형이 있다. 서로 다른 두 사각형은 면적을 갖는 부분을 공유하지 않는다. 이 때, 주어진 사각형들 중 몇 개를 선택하면 도형을 덮을 수 있다. 도형을 덮을 때에는, 도형의 바깥으로 벗어나는 사각형을 사용할 수 없으며, 도형의 내부에 사각형으로 덮이지 않은 부분이 있어서는 안 된다.

입력

첫째 줄에 두 자연수 n, m이 주어진다. 다음 n개의 줄에는 차례로 도형의 점들이 주어진다. 다음 m개의 줄에는 네 정수로 각 사각형의 대각선으로 마주 보는 두 꼭지점의 x, y좌표가 주어진다.

출력

첫째 줄에 선택한 사각형의 개수 C를 출력한다. 다음 C개의 줄에는 선택한 사각형의 번호를 오름차순으로 출력한다. 만약 덮을 수 없다면 C=0을 출력한다.

예제 입력

4 3
0 0
0 2
2 2
2 0
1 0 0 2
1 0 2 2
10 9 9 10

예제 출력

2
1
2

힌트