26528번 - 이항분포에서 가장 큰 직사각형 스페셜 저지

문제

$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}$까지 허용한다.

제한

힌트