24527번 - 이상한 나라의 갈톤보드 스페셜 저지

Francis Galton은 중심 극한 정리 중 충분한 표본 크기에서 이항분포가 정규분포에 근접한다는 것을 증명하기 위해 갈톤보드를 발명하였다. 갈톤보드는 보드와 보드에 수직으로 세워진 못으로 구성되어 있다. 위에서 구슬을 떨어뜨리면 여러 줄의 못과 부딪혀 왼쪽 또는 오른쪽으로 튕겨 나가는 과정을 반복한다. 바닥에 도착한 구슬은 칸막이에 의해 나눠지며 일반적인 갈톤보드는 위와 같이 정규분포를 보인다. 하지만 이상한 나라의 이상한 갈톤보드는 시작지점에서 도착가능한 모든 지점에 동일한 확률로 떨어진다. 모든 도착지점에 비슷한 개수의 구슬이 떨어지면 재미없기 때문에 구슬을 떨어뜨리는 시작지점을 선택할 수 있게 만들었다.

높이가 5인 이상한 갈톤보드의 시작지점과 도착지점 번호는 위와 같은 규칙을 가진다.

만약 시작지점 2에서 떨어뜨린다면 도착지점 [1, 5]에 모두 같은 확률로 도착한다. 만약 시작지점 6에서 떨어뜨린다면 도착지점 [3, 6]에 모두 같은 확률로 도착한다.

이상한 나라의 앨리스는 이상한 갈톤보드에 구슬을 떨어뜨리고 도착지점의 구슬 개수를 세려고 했지만 구슬이 너무 많아 포기했다. 대신 도착지점의 구슬 개수 기댓값을 구해 개수를 추측하려고 한다. 앨리스를 도와 구슬의 기댓값을 출력하는 프로그램을 작성하자.

프로그램은 두 쿼리를 수행한다.

구슬을 떨어뜨리는 쿼리가 $Q$개 주어진다.

$a$, $b$ : $a$번째 시작지점에 $b$개의 구슬이 떨어진다.

모든 구슬이 떨어진 후 도착지점에 존재하는 구슬 개수의 기댓값을 구하는 쿼리가 $R$개 주어진다.

$a, b$ : 도착지점[$a, b$]에 떨어지는 구슬 개수의 기댓값을 출력한다.

프로그램은 기댓값 쿼리를 모두 처리한 후 종료한다.

첫째 줄에 높이 $H$가 주어진다. ($1 \le H \le 100,000$)

둘째 줄에는 구슬을 떨어뜨리는 쿼리의 개수 $Q$와 기댓값을 묻는 쿼리의 개수 $R$이 주어진다. ($1 \le Q \le 100,000$, $1 \le R \le 100,000$)

셋째 줄부터 $Q$개의 쿼리 $a, b$가 주어진다. ($1 \le a \le \frac{H(H + 1)}{2}$, $1 \le b \le 100,000$)

3 + $Q$번째 줄부터 $R$개의 쿼리 $a$, $b$가 주어진다. ($1 \le a \le b \le H + 1$)

각 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

절대/상대 오차는 $10^{-4}$까지 허용한다.