Giải bài trực tuyến

Sau thành công của Bà Nà - Đường lên tiên cảnh, Alex muốn đầu tư vào một dự án du lịch khác trên dãy núi Trường sơn. Cùng với đoàn thám hiểm miệt mài tìm kiếm, cuối cùng Alex cũng tìm được một địa điểm vô cùng lý tưởng để khởi công xây dựng dự án này. 

Vùng núi gồm N ngọn núi mà Alex chọn có cấu trúc rất đặc biệt. Nếu quan sát trên bản đồ 2D (mặt phẳng tọa độ Oxy) thì mỗi ngọn núi có thể được biểu diễn bởi một đường Parabola có phương trình là ax² + bx + c (với a < 0). Trên bản đồ này, Alex tiến hành thiết kế các tuyến cáp treo. Có Q tuyến cáp treo sẽ được quy hoạch, vị trí cụ thể của điểm khởi đầu và điểm kết thúc của chúng chưa được xác định vì chưa có bản thống kê kinh phí chi tiết. Tuy nhiên, theo dự kiến ban đầu thì tuyến cáp treo thứ i sẽ bắt đầu tại hoành độ L_i và kết thúc tại hoành độ R_i trên bản đồ 2D.

Alex đặt AN TOÀN lên mọi tiêu chí trong quá trình thi công dự án này. Có hai điều Alex quan tâm nhất:

• Để cho du khách có cảm giác an toàn nhất, độ cao của cáp treo so với mực nước biển sẽ không đổi trong suốt đường đi. Nói cách khác, tuyến cáp treo có thể được mô tả bởi một đường thẳng song song với trục x của bản đồ 2D. 
• Độ cao của cáp sẽ phải lớn hơn độ cao của tất cả các ngọn núi mà nó đi qua ít nhất 1 đơn vị. Cụ thể hơn, nếu Hi là độ cao của tuyến cáp treo thứ i, thì H_i = 1 + max(a_kx² + b_kx + c_k | 1 ≤ k ≤ N và L_i ≤ x ≤ R_i)  (a_k, b_k, c_k là thông số của Parabola biểu diễn ngọn núi thứ k).

Bạn hãy giúp Alex tính toán độ cao an toàn tối thiểu của mỗi đường cáp treo nhé.

Input

• Dòng đầu chứa 2 số nguyên N và Q tương ứng với số đỉnh núi và số tuyến cáp treo.
• Dòng thứ i trong số N dòng tiếp theo chứa 3 số thực a_i, b_i và c_i mô tả ngọn núi thứ i.
• Dòng thứ i trong số Q dòng cuối chứa 2 số thực L_i và R_i mô tả tuyến cáp treo thứ i.

Output

• Xuất ra Q dòng, dòng thứ i chứa 1 số thực là độ cao H_i tìm được cho mỗi tuyến cáp treo, với ít nhất 2 chữ số sau dấu phẩy.

Giới hạn

• Subtask 1 (30%): 1 ≤ N ≤ 300, 1 ≤ Q ≤ 10000
• Subtask 2 (30%): 1 ≤ N ≤ 300, 1 ≤ Q ≤ 500000 
• Subtask 3 (40%): 1 ≤ N ≤ 2000, 1 ≤ Q ≤ 500000

Ngoài ra trong tất cả các test:

• -10 ≤ a_i < 0
• -10³ ≤ b_i, c_i ≤ 10³
• -10³ ≤ L_i ≤ R_i ≤ 10³
• Các số trong input có không quá 2 chữ số sau dấu phẩy

Ví dụ

Input:

2 3
-1.0 3.0 0.0
-1.0 0.0 6.0
-1.0 0.4
1.0 2.0
2.5 3.0

Output:

7.00
6.00
2.25

Chấm điểm

• Đáp số của bạn được coi là đúng nếu đáp án của bạn và ban tổ chức chênh nhau không quá 10-2
• Trong thời gian thi, bài của bạn sẽ chỉ được chấm với duy nhất 1 test có trong đề bài.

Hình minh họa  

Chú thích: 2 ngọn núi tương ứng với 2 parabola, 3 tuyến cáp treo được biểu diễn bởi các đoạn thẳng màu đen trên trục hoành, 3 điểm màu đỏ là độ cao lớn nhất của các ngọn núi mà các tuyến cáp treo tương ứng đi qua.