RFID 추적

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

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

각 센서의 범위는 r이다. 즉, 센서와의 일직선 거리가 많아야 r인 칩의 위치를 알 수 있다는 뜻이다. 하지만, 센서와 물건 사이의 일직선이 벽과 교차하거나 접하는 경우에는 교차하거나 접한 벽의 개수만큼 범위가 줄어든다. 또, 센서가 너무 가까이 있으면 간섭을 일으킬 수 있기 때문에, 모든 센서들 사이의 거리는 적어도 r이다. 센서나 물건이 벽에 위치한 경우는 없다.

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

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

각 테스트 케이스의 첫째 줄에는 센서의 수 s, 센서의 범위 r, 벽의 수 w, 물건의 수 p가 주어진다. (1 ≤ s ≤ 250,000, 1 ≤ r ≤ 20, 0 ≤ w ≤ 10, 1 ≤ p ≤ 10,000)

다음 s개 줄에는 센서의 위치 (xi, yi)가 주어진다. 각 센서 간의 거리는 적어도 r이다. (-10,000 ≤ xi, yi ≤ 10,000)

다음 w개 줄에는 네 정수 bxi, byi, exi, eyi가 주어진다. (-10,000 ≤ bxi, byi, exi, eyi ≤ 10,000) 벽은 (bxi, byi)와 (exi, eyi)를 잇는 선분이고, 선분의 길이는 양수이다.

마지막 p개 줄에는 물건의 위치 (pxi, pyi)가 주어진다. (-10,000 ≤ pxi, pyi ≤ 10,000)

각 테스트 케이스에 대해서, 각 물건을 감지할 수 있는 센서의 개수와 위치를 출력한다. 만약, 센서가 여러 개라면, x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순으로 출력한다.