Tại thủ đô của Byteland có một công viên hình chữ nhật được bao quanh bởi hàng rào. Các cây và khách tham quan trong công viên được biểu diễn bằng các hình tròn.

Công viên có bốn cổng, mỗi cổng nằm ở một góc: \(1\) là góc dưới bên trái, \(2\) là góc dưới bên phải, \(3\) là góc trên bên phải và \(4\) là góc trên bên trái. Khách tham quan chỉ có thể vào và ra khỏi công viên qua các cổng này.

Một khách tham quan có thể vào hoặc ra khỏi công viên khi hình tròn biểu diễn người đó tiếp xúc với cả hai cạnh tạo thành góc của cổng tương ứng. Khách tham quan có thể di chuyển tự do trong công viên, nhưng không được chồng lấn với bất kỳ cây nào hoặc với hàng rào.

Hai đối tượng được gọi là tiếp xúc nếu chúng có đúng một điểm chung. Hai đối tượng được gọi là chồng lấn nếu chúng có nhiều hơn một điểm chung.

Với mỗi khách tham quan, biết cổng mà người đó sẽ đi vào, hãy xác định những cổng mà người đó có thể đi ra.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số cây trong công viên và số khách tham quan.

Dòng thứ hai chứa hai số nguyên \(w\) và \(h\): chiều rộng và chiều cao của công viên. Góc dưới bên trái có tọa độ \((0,0)\), còn góc trên bên phải có tọa độ \((w,h)\).

\(n\) dòng tiếp theo mô tả các cây. Mỗi dòng chứa ba số nguyên \(x\), \(y\) và \(r\): cây có tâm tại \((x,y)\) và bán kính \(r\). Các cây không chồng lấn với nhau hoặc với hàng rào.

Cuối cùng là \(m\) dòng mô tả các khách tham quan. Mỗi dòng chứa hai số nguyên \(r\) và \(e\): bán kính của khách tham quan và cổng mà người đó sẽ đi vào công viên.

Ngoài ra, tại mỗi góc công viên có một vùng hình vuông kích thước \(2k \times 2k\) mà không cây nào chồng lấn lên, trong đó \(k\) là bán kính của khách tham quan lớn nhất.

Dữ liệu ra

Với mỗi khách tham quan theo thứ tự trong dữ liệu vào, in ra một dòng gồm số hiệu các cổng mà người đó có thể đi ra, theo thứ tự tăng dần và không có dấu cách ở giữa.

Ràng buộc

Trong mọi phân nhóm, \(4k < w,h \le 10^9\), trong đó \(k\) là bán kính của khách tham quan lớn nhất.

Phân nhóm

1. Nhóm 1 (27 điểm): \(1 \le n \le 2000\); \(m=1\).
2. Nhóm 2 (31 điểm): \(1 \le n \le 200\); \(1 \le m \le 10^5\).
3. Nhóm 3 (42 điểm): \(1 \le n \le 2000\); \(1 \le m \le 10^5\).

Ví dụ

5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

1234
2
14

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ nhất, bài B.