시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB144201426.923%

문제

$B(n, p)$는 앞면이 나올 확률이 $p$인 동전을 $n$번 던질 때 앞면이 나오는 횟수에 대한 확률분포이다. 즉 확률변수 $X \sim B(n, p)$에 대해, $X = i$일 확률 $P(X = i)$는 동전을 던져서 앞면이 $i$번 나올 확률과 같다.

이 확률변수 $X$의 확률질량함수로 길이 $n+1$의 히스토그램을 만들자. 막대는 왼쪽부터 차례대로 $0, \cdots, n$의 번호가 붙어 있고, 막대 $i$는 너비가 $1$이고 높이가 $P(X = i)$이다.

히스토그램이 있으니 역시 히스토그램의 영역 안에 포함되는 가장 큰 직사각형의 넓이를 구해야 될 것 같다. 단, 직사각형의 한 변이 히스토그램의 밑변과 평행해야 한다.

$[l, r]$로 표현되는 쿼리 $Q$개가 주어진다. 각 쿼리에 대해, 막대 $l$부터 $r$까지로만 이루어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하시오.

입력

첫 번째 줄에 $n$, $p$, $Q$가 주어진다. $p$는 소수점 아래 최대 4자리까지 주어진다. $(1 \leq n \leq 200\,000;$ $0 < p < 1;$ $1 \leq Q \leq 200\,000)$

다음 $Q$개의 줄에 정수 $l$과 $r$이 공백으로 구분되어 주어진다. $(0 \leq l \leq r \leq n)$

출력

각 쿼리에 대해 가장 큰 직사각형의 넓이를 한 줄에 하나씩 출력한다. 절대/상대오차는 $10^{-6}$까지 허용한다.

예제 입력 1

10 0.5 3
0 10
2 5
5 5

예제 출력 1

0.615234375000
0.410156250000
0.246093750000