There's only three weeks left until Christmas and Santa is in big trouble: all his elves have gone on strike! Furthermore, the toy-making machines are deteriorating at an alarming rate.

Santa has ~M~​ machines. Each machine can produce toys at a rate given by ~-at+b~, where ~a~​ and ~b~​ are constants unique to the machine and​ ​~t~​ is the time. The machines stop working once they reach a negative rate (at time ~\frac{b}{a}~). Santa may only operate one machine at a time, but with his magical abilities, he can switch between machines instantly.

Santa wants to know if he can finish making all the toys on time, so he has asked you, his only remaining helper, to answer ~Q~​ queries: the number of toys he can produce from time ~x~​ to time ~y~​.

Note: A machine with constants ~a~​ and ~b~​ can produce ~(y-x)(b-\frac{a}{2}(x+y))~ toys from time ~x~​ to ~y~​.

Input​

The first line contains two integers, \(M​, Q\)​.

The next ~M~​ lines each contain two numbers, ~a_m, b_m~ describing the ~m^{th}~ machine.

The next ~Q~​ lines each contain two integers, ~x_q, y_q~ describing a query.

Input​ ​Constraints

\(1 \le M​, Q​ \le 100\) ~000~

\(0 \le a​ \le 1\) \(000, a​ \in​ \mathbb{R}\)

\(1 < b​ \le 10^6\)

\(0 \le x​ < y​ \le 10^5\)

For ~30\%~​ of the points, \(M​ ​=​ ​2\)​.

Output

For each query, output the maximum number of toys that Santa can produce in the given interval of time.
Your answer will be counted as correct if it is within a relative or absolute error of ~10^{-3}~ from the judge's answer.

Sample​ ​Input​ ​1

2 3
2 4
1 3
0 1
1 3
0 4

Sample​ ​Output​ ​1

3.000
2.000
5.000

Explanation​ ​for​ ​Sample​ ​Output​ ​1

For the first query, it is optimal to use the first machine for the entire interval. For the second, it is optimal to use the second machine for the entire interval. For the third query, use the first machine for the first minute, and the second machine for the next two minutes, and past the third minute, all machines are broken.

Sample​ ​Input​ ​2

4 5
2 10
1 7.5
0.5 5
1 6.5
0 1
0 2
0 4
1 2
0 10

Sample​ ​Output​ ​2

9.000
16.000
25.125
7.000
34.375