공원

시간 제한2.5초메모리 제한256 MB

요약

직사각형 공원 안에 서로 겹치지 않는 나무 원들이 있을 때, 각 방문자 원이 나무나 울타리와 겹치지 않고 도달할 수 있는 입구를 판정한다.

문제

바이트랜드의 수도에는 울타리로 둘러싸인 직사각형 공원이 있다. 공원의 나무와 방문자는 모두 원으로 나타낸다.

공원의 네 모서리에는 출입구가 하나씩 있다. 1번은 왼쪽 아래, 2번은 오른쪽 아래, 3번은 오른쪽 위, 4번은 왼쪽 위다. 방문자는 출입구로만 공원에 들어오거나 나갈 수 있다.

방문자는 출입구가 있는 모서리의 두 변에 동시에 닿는 위치에 있을 때 들어오거나 나갈 수 있다. 공원 안에서는 자유롭게 움직이지만, 나무나 울타리와 겹칠 수는 없다. 닿는 것은 겹치는 것이 아니므로 허용된다.

방문자마다 들어오는 출입구가 주어진다. 각 방문자가 어느 출입구로 나갈 수 있는지 구하라.

첫째 줄에 공원의 나무 수 $n$ 과 방문자 수 $m$ 이 주어진다.

둘째 줄에 공원의 너비 $w$ 와 높이 $h$ 가 주어진다. 공원의 왼쪽 아래 모서리는 $(0, 0)$ , 오른쪽 위 모서리는 $(w, h)$ 다.

다음 $n$ 개 줄에 나무를 설명하는 세 정수 $x$ , $y$ , $r$ 이 주어진다. 나무의 중심은 $(x, y)$ 이고 반지름은 $r$ 이다. 나무는 서로 겹치지 않고 울타리와도 겹치지 않는다.

마지막 $m$ 개 줄에 방문자를 설명하는 두 정수 $r$ 과 $c$ 가 주어진다. $r$ 은 방문자의 반지름이고, $c$ 는 그 방문자가 들어오는 출입구 번호다.

방문자마다 한 줄에 그 방문자가 나갈 수 있는 출입구 번호를 오름차순으로, 사이에 공백 없이 출력한다. 들어온 출입구 $c$ 는 항상 답에 포함한다.

두 도형의 공통점이 정확히 하나면 서로 닿은 것이고, 공통점이 둘 이상이면 겹친 것이다. 따라서 나무 두 개 사이의 빈 폭이 방문자의 지름과 정확히 같으면 방문자는 두 나무에 닿은 채로 그 사이를 지나갈 수 있다. 나무와 울타리 사이도 마찬가지다.

아래 그림은 출입구 주변 영역과 첫 번째 예제에 나오는 각 방문자의 이동 경로를 보여준다.

예제 1

입력

예상 출력

1234
2
14

예제 2

입력

예상 출력