문제

고작 9개월밖에 남지 않은 크리스마스를 즐기기 위해 베개는 전구 개를 구매해 한 줄로 연결했다. 베개는 여기에 스위치를 달아 스위치를 켜면 모든 전구가 켜지도록 멋진 설계를 끝마쳤다.

하지만 전구 설계를 관찰하던 베개는 전구가 너무 낡아서, 스위치를 켤 때 번째 전구가 확률로만 켜진다는 사실을 알아 버렸다!

물론 모든 전구가 인테리어에 필수적인 것은 아니기에, 베개는 스위치를 켜면 전구가 어떻게 켜질 지 알고 싶어졌다.

스위치를 직접 켜는 것은 전기가 많이 드는 일이다. 따라서 베개는 당신에게 시뮬레이션을 부탁했다! 다음 쿼리를 처리하는 프로그램을 작성하라.

• l r: 번째부터 번째까지의 전구만을 보았을 때, 스위치를 켜면 나타나는 켜져 있는 전구들이 이루는 연속된 덩어리의 개수의 기댓값을 구해 출력한다.

각 전구가 켜지는 사건은 독립적이라고 가정한다.

입력

첫 번째 줄에 전구의 개수 과 쿼리의 개수 가 주어진다.

두 번째 줄에 개의 수 가 공백을 사이에 두고 소수 둘째 자리까지 주어진다.

세 번째 줄부터 개의 줄에 걸쳐, 각 줄마다 쿼리가 주어진다.

출력

쿼리가 주어질 때마다, 한 줄에 하나씩 쿼리의 답을 출력한다. 절대/상대 오차는 까지 허용된다.