Sau khi học xong bài Vật lí về ánh sáng ở trường, anh ~T~ vô cùng hào hứng và quyết định tự mình thực hiện một thí nghiệm nhỏ.

Anh dọn sạch toàn bộ đồ đạc trong phòng ngủ, kéo kín rèm cửa, tắt hết đèn và chuẩn bị ~N~ chiếc đèn pin cùng rất nhiều tấm cảm quang hấp thụ ánh sáng.

Coi căn phòng là một hình chữ nhật trên mặt phẳng tọa độ. Bốn bức tường của căn phòng lần lượt nằm trên các đường thẳng:

• Bức tường bên trái: ~x = 0~;
• Bức tường bên phải: ~x = W~;
• Bức tường phía dưới: ~y = 0~;
• Bức tường phía trên: ~y = H~.

Bạn được phép đặt đèn pin thứ ~i~ tại một vị trí nguyên bất kỳ ~(0, Y_i)~ trên bức tường bên trái, trong đó

$$ 0 \le Y_i \le H. $$

Đèn pin thứ ~i~ có góc mở bằng ~a_i~ độ và chỉ số xuyên thấu bằng ~K_i~.

Trục chính của mọi đèn pin đều vuông góc với bức tường bên trái, song song với trục ~Ox~ và hướng về phía bức tường bên phải.

Mọi tia sáng của đèn pin thứ ~i~ đều xuất phát từ ~(0, Y_i)~ và tạo với trục ~Ox~ một góc nằm trong khoảng từ ~-\frac{a_i}{2}~ đến ~\frac{a_i}{2}~ độ.

Trong căn phòng có ~M~ tấm cảm quang hấp thụ ánh sáng.

Tấm cảm quang thứ ~j~ được mô tả bởi bốn số nguyên

$$ (x_j, y_j, h_j, k_j) $$

trong đó:

• Cạnh dưới nằm tại ~(x_j, y_j)~;
• Cạnh trên nằm tại ~(x_j, y_j + h_j)~;
• Tấm cảm quang được biểu diễn bởi đoạn thẳng đứng nối hai điểm trên;
• ~k_j~ là chỉ số hấp thụ của tấm.

Một tia sáng được coi là đi qua tấm cảm quang nếu tia cắt đoạn thẳng biểu diễn tấm đó.

Mỗi lần đi qua tấm cảm quang thứ ~j~, tổng chỉ số hấp thụ của tia sáng tăng thêm ~k_j~.

Một tia sáng của đèn pin thứ ~i~ chỉ có thể tiếp tục truyền đi nếu tổng chỉ số hấp thụ của tất cả các tấm cảm quang mà tia đã đi qua luôn nhỏ hơn ~K_i~.

Ngay khi tổng này lớn hơn hoặc bằng ~K_i~, tia sáng bị hấp thụ hoàn toàn và không thể truyền tiếp.

Mọi tia sáng còn tồn tại khi tới được bức tường bên phải (~x = W~) sẽ tạo thành các điểm sáng trên bức tường này.

Một điểm trên bức tường bên phải được coi là được chiếu sáng nếu tồn tại ít nhất một tia sáng của một trong ~N~ chiếc đèn pin đi tới được điểm đó.

Hợp của tất cả các điểm sáng tạo thành một hoặc nhiều đoạn sáng liên tiếp trên bức tường bên phải.

Hãy lựa chọn vị trí đặt của tất cả các đèn pin sao cho tổng chiều dài các đoạn sáng trên bức tường bên phải là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên ~T~ là số lượng bộ dữ liệu.

Mỗi bộ dữ liệu được mô tả như sau:

• Dòng đầu tiên chứa hai số nguyên dương ~H, W~.
• Dòng thứ hai chứa số nguyên dương ~N~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i, K_i~ lần lượt là góc mở và chỉ số xuyên thấu của đèn pin thứ ~i~.
• Dòng tiếp theo chứa số nguyên dương ~M~.
• ~M~ dòng tiếp theo, dòng thứ ~j~ chứa bốn số nguyên ~x_j, y_j, h_j, k_j~ lần lượt là vị trí ~(x_j, y_j)~, chiều cao và chỉ số hấp thụ của tấm cảm quang thứ ~j~.

Output

Với mỗi bộ dữ liệu, in ra hai dòng:

• Dòng thứ nhất gồm ~N~ số nguyên ~Y_1, Y_2, \ldots, Y_N~ là vị trí đặt của các đèn pin (~Y_i~ là vị trí đặt của đèn pin thứ ~i~ tại ~(0, Y_i)~). Nếu tồn tại nhiều cách đặt đạt giá trị lớn nhất, in ra bất kỳ một cách nào.
• Dòng thứ hai in ra một số thực duy nhất là tổng chiều dài lớn nhất của hợp các đoạn sáng trên bức tường bên phải.

Đáp án được coi là đúng nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá ~10^{-6}~, các vị trí đặt hợp lệ và kết quả lớn hơn hoặc bằng so với kết quả của ban tổ chức.

Constraints

• ~1 \le T \le 5~
• ~1 \le N, M \le 25~
• ~10 \le W \le H \le 10^9~
• ~0 < a_i < 180~
• ~1 \le K_i, k_j \le 10^9~
• ~0 < x_j < W~
• ~0 < y_j < H~
• ~1 \le y_j + h_j \le H~

Sample Input

1
20 10
2
90 5
60 3
3
5 5 4 3
5 12 3 4
2 7 4 2

Sample Output

13 0
20.000000000

Subtasks

• Subtask 1 (7%): ~N = 2~.
• Subtask 2 (7%): ~a_i = 90~.
• Subtask 3 (7%): ~k_j = 1~.
• Subtask 4 (7%): ~h_j = 1~.
• Subtask 5 (7%): ~K_i \le k_j~.
• Subtask 6 (7%): ~W, H \le 1000~.
• Subtask 7 (7%): ~N, M \le 5~.
• Subtask 8 (7%): ~N, M \le 15~.
• Subtask 9 (44%): Không có ràng buộc nào thêm.