RFID 추적

선영이는 창고를 하나 운영하고 있다. 고객이 물건을 주문하면, 선영이는 물건을 창고에서 찾아 박스에 포장해 택배로 보낸다.

창고에 보관되는 모든 물건에는 RFID 칩이 하나씩 붙어 있다. 또한 창고의 천장에는 물건의 위치를 추적하기 위한 센서가 설치되어 있다.

각 센서의 범위는 $r$이다. 즉, 센서와의 직선 거리가 최대 $r$인 칩의 위치를 알 수 있다. 하지만 센서와 물건을 잇는 선분이 벽과 교차하거나 접하면, 교차하거나 접한 벽의 개수만큼 범위가 줄어든다. 다시 말해 어떤 물건에 대한 센서의 유효 범위는 $r$에서 그 센서와 물건을 잇는 선분이 교차하거나 접하는 벽의 개수를 뺀 값이며, 센서와 물건의 직선 거리가 이 유효 범위 이하일 때에만 그 센서가 칩을 읽을 수 있다.

또한 센서가 너무 가까이 있으면 간섭이 생기므로, 모든 센서 쌍 사이의 거리는 적어도 $r$이다. 센서나 물건이 벽 위에 놓이는 경우는 없다.

각 물건에 대해, 그 물건의 RFID 칩을 읽을 수 있는 센서를 모두 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 센서의 수 $s$, 센서의 범위 $r$, 벽의 수 $w$, 물건의 수 $p$가 공백으로 구분되어 주어진다. ($1 \le s \le 250000$, $1 \le r \le 20$, $0 \le w \le 10$, $1 \le p \le 10000$)

다음 $s$개 줄에는 각 센서의 좌표 $x_i$, $y_i$가 주어진다. 모든 센서 쌍 사이의 거리는 적어도 $r$이다. ($-10000 \le x_i, y_i \le 10000$)

다음 $w$개 줄에는 네 정수 $bx_i$, $by_i$, $ex_i$, $ey_i$가 주어진다. ($-10000 \le bx_i, by_i, ex_i, ey_i \le 10000$) 각 벽은 $(bx_i, by_i)$와 $(ex_i, ey_i)$를 잇는 선분이며, 그 길이는 양수이다.

마지막 $p$개 줄에는 각 물건의 좌표 $px_i$, $py_i$가 주어진다. ($-10000 \le px_i, py_i \le 10000$)

각 테스트 케이스에 대해, 각 물건마다 그 물건을 감지할 수 있는 센서의 개수를 출력하고, 이어서 감지 가능한 센서들의 좌표를 출력한다. 센서가 여러 개이면 $x$좌표가 증가하는 순서로, $x$좌표가 같으면 $y$좌표가 증가하는 순서로 출력한다. 각 센서의 좌표는 (x,y) 형식으로 쓰고, 개수와 각 좌표는 공백 하나로 구분한다. 감지할 수 있는 센서가 없으면 0만 출력한다.