Tracking RFIDs

Jeroen operates a warehouse storage facility for the North Western Electrical Resource Company (NWERC). When a customer places an order with NWERC, this order is conveyed to the warehouse. Jeroen’s task is to then find the products ordered, pack them into a box, and ship them to the customer.

NWERC has an unusual warehouse policy: the products are not arranged in any particular order, and are strewn all over the place. However, it is possible for Jeroen to do his job because each product is tracked using RFID technology¹. Specifically, each product is assigned a wireless RFID chip as soon as it enters the warehouse, and sensors located on the warehouse ceiling are used to automatically track the products.

By default, each sensor has a range of r units – that is, it can read any RFID chip that is located at most r units from it in a straight line. However, if the line segment between a sensor and a product intersects with or touches x walls, the range of the sensor is reduced by x units in that direction. Furthermore, the sensors may fail to read an RFID chip due to interference from other sensors, so the distance between any pair of sensors in the warehouse is guaranteed to be at least r units. You may further assume that no sensor or product is placed on a wall.

Jeroen now wants to determine, for each product, which sensors can read its RFID chip. Can you help him?

Figure 1: Illustration of sensors, walls and products as in the Sample Input.

 

Input

On the first line one positive integer: the number of test cases, at most 100. After that per test case:

• one line with four integers s (1 ≤ s ≤ 250 000), r (1 ≤ r ≤ 25), w (0 ≤ w ≤ 10) and p (1 ≤ p ≤ 10 000) where s represents the number of sensors, r the range of each sensor, w the number of walls and p the number of products.
• s lines containing two integers x_i and y_i (-10 000 ≤ x_i,y_i ≤ 10 000). Each such line represents a sensor at location (x_i, y_i). The distance between any pair of sensors is guaranteed to be at least r units.
• w lines containing four integers bx_i, by_i, ex_i and ey_i (-10 000 ≤ bx_i,by_i,ex_i,ey_i ≤ 10 000). Each such line represents a wall, which should be considered as straight line segment from (bx_i, by_i) to (ex_i, ey_i). The length of this line segment will be positive.
• p lines, each containing two integers px_i and py_i (-10 000 ≤ px_i,py_i ≤ 10 000). Each such line represents a product at location (px_i, py_i).

Output

Per test case:

• p lines, each representing a product in the order they appear in the input. Each line should contain an integer t, the number of sensors that can track the product; this integer should then be followed by a list of t ordered pairs representing the corresponding sensor locations. If there are multiple sensors, they should be sorted in increasing order by x-coordinate. If multiple sensors have the same x-coordinate, they should be sorted in increasing order by y-coordinate.

Sample in- and output

1
4 3 4 7
0 0
-1 3
2 3
11 5
-4 -1 5 -1
3 5 6 1
11 4 11 3
12 5 12 8
1 1
0 -2
4 4
11 2
13 5
13 7
14 5

3 (-1,3) (0,0) (2,3)
1 (0,0)
0
0
1 (11,5)
0
0

¹Objects, that have a radio-frequency identification (RFID) tag attached, can be tracked using radio waves.

Copyright notice

This problem text is copyright by the NWERC 2011 jury. It is licensed under the Creative Commons Attribution-Share Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/by-sa/3.0/legalcode