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^{2} + 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 ~H_{i}~ là độ cao của tuyến cáp treo thứ ~i~, thì ~H_{i} = 1 + max(a_{k}x^{2} + b_{k}x + c_{k}~ \| ~1 \leq k \leq N~ và ~L_{i} \leq x \leq R_{i})~ (vớ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 \leq N \leq 300, 1 \leq Q \leq 10000~
• Subtask ~2 (30\%)~: ~1 \leq N \leq 300, 1 \leq Q \leq 500000~
• Subtask ~3 (40\%)~: ~1 \leq N \leq 2000, 1 \leq Q \leq 500000~

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

• ~-10 \leq a_{i} < 0~
• ~-10^{3} \leq b_{i}, c_{i} \leq 10^{3}~
• ~-10^{3} \leq L_{i} \leq R_{i} \leq 10^{3}~
• Các số trong input có không quá ~2~ chữ số sau dấu phẩy.

Đá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}~

Sample 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

Sample Output

7.00
6.00
2.25

Note

~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.