서울과 학기-술 대학교

현재 공릉동에는 서울과학기술대학교가 위치해 있습니다. 하지만, 어떤 평행세계의 공릉동에는 "서울과 학기-술 대학교"가 있습니다.

"서울과 학기-술 대학교"에 재학 중인 대학생인 카프리는 현재 수강할 과목을 결정하는 데 어려움을 겪고 있습니다. 그도 그럴 것이, 서울과학기술대학교의 최대 평점은 $4.5$이지만, "서울과 학기-술 대학교"의 최대 평점은 $10\\, 000.0$입니다. 그래서 교수 또한 각 학생에게 $0$ 이상 $10\\, 000$ 이하의 정수로 평점을 매깁니다.

각 과목은 $15$ 이하의 자연수인 학점 $H$와 $10\\, 000$ 이하의 음이 아닌 정수인 예상 평점 $P$를 가지고 있습니다. $k$개의 과목을 수강하였을 때 각 과목의 학점이 $h\_1,h\_2,\cdots ,h\_k$이고 평점이 $p\_1,p\_2,\cdots ,p\_k$라면, 학기 최종 평점은 다음과 같습니다.

$\frac{{h\_1p\_1+h\_2p\_2+\cdots +h\_kp\_k}}{{h\_1+h\_2+\cdots +h\_k}}$

카프리는 여러 가지 시나리오를 고려하여 이번 학기 시간표를 정하려고 합니다. 카프리가 고려할 시나리오의 종류는 다음과 같습니다.

• $l\\,\\, r$: 이번 학기에는 모든 과목을 합쳐 총 $l$학점 이상 $r$학점 이하의 학점을 얻어야 합니다.

"서울과 학기-술 대학교"의 교칙에 따라 모든 재학생은 각 학기 최대 $L$학점을 수강할 수 있습니다. 또한, 어떤 과목도 수강하지 않을 경우 제적될 수 있으므로, 모든 재학생은 각 학기 적어도 $1$학점 이상을 수강해야 합니다. 다시 말해, 각 시나리오에 대해 $1\le l\le r\le L$이 성립합니다.

카프리가 모든 과목에 대해 평점을 예상한 대로 정확하게 받을 수 있다고 가정할 때, 각 시나리오에 대해 카프리의 학기 최종 평점의 최댓값을 구해 주세요.

첫 번째 줄에 수강할 수 있는 과목의 수 $n$과 학점 제한 $L$이 공백으로 구분되어 주어집니다. ($1\le n\le 10^5$, $1\le L\le 5\cdot 10^5$)

두 번째 줄부터 $n$개의 줄에 걸쳐 과목의 정보가 주어집니다.

$n$개의 줄 각각에는 각 과목의 학점 $H\_i$와 수강하였을 때의 평점 $P\_i$가 공백으로 구분되어 주어집니다. ($1\le H\_i\le 15$, $0\le P\_i\le 10\\, 000$)

$n+2$번째 줄에 시나리오의 개수 $q$가 주어집니다. ($1\le q\le 10^5$)

그다음 줄부터 $q$개의 줄에 걸쳐 시나리오의 정보가 주어집니다.

$q$개의 줄 각각에는 시나리오를 나타내는 두 정수 $l\_i$와 $r\_i$가 공백으로 구분되어 주어집니다. ($1\le l\_i\le r\_i\le L$)

주어진 시나리오 각각에 대해 카프리가 얻을 수 있는 학기 최종 평점의 최댓값을 새로운 줄에 출력합니다.

단, 총 학점이 $l\_i$학점 이상 $r\_i$학점 이하가 되도록 수강 신청을 할 수 있는 방법이 없다면 $0$을 출력합니다.

모든 시나리오에 대해 정답과 출력한 값 간의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하인 경우 정답으로 인정됩니다.