문제

벚꽃컵에 간단한 문제를 출제해 많은 찬사를 받았던 현중이는 이번 단풍컵에도 간단한 문제를 출제하기로 했다. 문제는 다음과 같다.

• 길이 인 배열의 inversion은 이고 인 쌍을 의미한다. 예를 들어, 배열 에는 개의 inversion이 존재한다. 길이 이고 모든 원소가 이상 이하인 배열 중 하나를 임의로 선택할 때, 배열의 inversion 개수의 기댓값을 구하시오. 조건을 만족하는 모든 배열은 선택될 확률이 같다.

하지만, 간단한 문제에 싫증이 난 찬우는 몰래 쿼리를 추가해 복잡한 문제로 바꿔 버렸다! 따라서, 배열의 길이 과 원소의 범위 이 주어질 때 여러분은 다음과 같은 쿼리를 처리해야 한다.

• : 배열의 번째 원소를 로 확정시킨다. 이후 아직 확정되지 않은 모든 원소를 각각 이상 이하의 임의의 수로 채울 때 배열의 inversion 개수의 기댓값을 구하시오. 모든 수는 선택될 확률이 같다.

쿼리는 누적되며, 쿼리로 주어지는 는 모두 다르다. 즉, 쿼리로 인해 확정된 원소는 이후 쿼리에서도 확정되어 있으며, 바뀌지 않는다. 첫 쿼리 이전에는 배열의 모든 원소가 확정되지 않은 상태이다.

입력

첫째 줄에 배열의 길이 , 원소의 범위 , 쿼리의 개수 가 공백으로 구분되어 주어진다.

둘째 줄부터 개의 쿼리가 한 줄에 하나씩 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

개의 줄에 걸쳐 각 쿼리의 정답을 한 줄에 하나씩 출력한다.

각 쿼리에서 구한 기댓값이 일 때, 해당 쿼리의 정답은 이고 인 정수 이다. 이러한 는 유일함을 증명할 수 있다.

노트

이 소수이므로 페르마의 소정리에 의해 이고 가 의 배수가 아니라면 이다.