RFID Tracking

Sunyoung runs a warehouse. When a customer places an order, she finds the item in the warehouse, packs it into a box, and ships it.

Every item stored in the warehouse has a single RFID chip attached to it. Sensors are mounted on the ceiling of the warehouse to track the positions of the items.

Each sensor has a range of $r$. That is, a sensor can locate any chip whose straight-line distance from the sensor is at most $r$. However, if the line segment connecting a sensor and an item crosses or touches walls, the sensor's range is reduced by the number of walls it crosses or touches. In other words, for a given item the sensor's effective range equals $r$ minus the number of walls that the segment between the sensor and the item crosses or touches, and the sensor can read the chip only when the straight-line distance between the sensor and the item is at most this effective range.

Also, because sensors placed too close together cause interference, the distance between every pair of sensors is at least $r$. No sensor or item ever lies on a wall.

For each item, write a program that finds all sensors that can read that item's RFID chip.

The first line contains the number of test cases, which is at most 100.

The first line of each test case contains the number of sensors $s$, the sensor range $r$, the number of walls $w$, and the number of items $p$. ($1 \le s \le 250000$, $1 \le r \le 20$, $0 \le w \le 10$, $1 \le p \le 10000$)

The next $s$ lines each contain the coordinates $x_i$, $y_i$ of a sensor. The distance between every pair of sensors is at least $r$. ($-10000 \le x_i, y_i \le 10000$)

The next $w$ lines each contain four integers $bx_i$, $by_i$, $ex_i$, $ey_i$. ($-10000 \le bx_i, by_i, ex_i, ey_i \le 10000$) Each wall is the line segment joining $(bx_i, by_i)$ and $(ex_i, ey_i)$, and its length is positive.

The last $p$ lines each contain the coordinates $px_i$, $py_i$ of an item. ($-10000 \le px_i, py_i \le 10000$)

For each test case, for each item output the number of sensors that can detect it, followed by the coordinates of those sensors. If there are multiple sensors, print them in increasing order of $x$ coordinate, breaking ties by increasing $y$ coordinate. Write each sensor's coordinates in the form (x,y), and separate the count and each coordinate by a single space. If no sensor can detect the item, print only 0.