Eggscavation

휴가를 떠날 때가 됐다. C 셸 스크립트는 지겨워졌으니 이번에는 조개껍데기를 모으기로 한다.

섬나라 카르테시아의 해변은 정사각형 칸 $N \times N$개로 이루어진 정사각형 모래밭이다. 가져온 삽은 해변에서 $K \times K$ 크기의 정사각형 부분격자를 한 번에 퍼낸다. 이 부분격자는 해변 안에 완전히 들어가야 하므로 퍼낼 수 있는 자리는 정확히 $(N - K + 1)^2$개다.

칸 아래에는 아직 알려지지 않은 조개 $M$종이 묻혀 있다. $i$번째 종의 조개는 $S_i$개이고 $S_i$개의 칸에 하나씩 묻혀 있으며, $1 \le S_i \le 4$이다. 집으로 가져온 조개는 종류 하나마다 학자가 1달러를 준다. 이미 가진 종을 더 캐도 값은 늘지 않는다. 즉 한 번 퍼낸 이익은 퍼낸 부분격자 안에 조개가 하나 이상 있는 종의 개수다.

해변에는 도도새가 돌아다닌다. 도도새는 이따금 아무 칸에나 알을 묻고, 이미 알이나 조개가 있는 칸에도 묻는다. 퍼낸 $K \times K$ 부분격자에 도도새 알이 하나라도 들어 있으면 학자들은 멸종위기종을 해쳤다며 화를 내고 아무도 값을 치르지 않는다. 그때 그 삽질의 이익은 0달러다.

여러 시점에서, 퍼낼 수 있는 모든 자리 가운데 하나를 균일한 확률로 골랐을 때 이익이 주어진 금액 이상일 확률을 구하려고 한다.

첫째 줄에 해변의 크기 $N$과 삽의 크기 $K$가 주어진다. ($1 \le N \le 2500$, $1 \le K \le N$)

둘째 줄에 조개 종의 수 $M$이 주어진다. ($0 \le M \le 10^5$) 이어지는 $M$개의 줄 가운데 $i$번째 줄은 $i$번째 종을 나타낸다. 각 줄은 정수 $S_i$ ($1 \le S_i \le 4$)로 시작하고, 그 뒤에 정수 $2 \times S_i$개가 이어진다. 이 정수는 그 종의 조개 $S_i$개가 묻힌 칸의 좌표이며 $(1, 1)$부터 $(N, N)$ 사이다. 칸 $(r, c)$는 $r$행 $c$열의 칸이다.

다음 줄에 $T$가 주어진다. ($1 \le T \le 10\,000$) 이어지는 $T$개의 줄은 오래된 시점부터 최근 시점까지 차례대로 한 시점씩 나타내고, 각 줄은 다음 두 형태 가운데 하나다.

• 1 A B: 도도새가 방금 칸 $(A, B)$에 알을 묻었다. ($1 \le A, B \le N$)
• 2 V: 이 시점에 무작위로 한 번 퍼냈을 때 이익이 $V$달러 이상일 확률을 구한다. ($1 \le V \le 10^9$) 확률을 계산해도 조개와 알은 그대로 남는다.

2 V 줄마다 무작위로 한 번 퍼냈을 때 이익이 $V$달러 이상일 확률을 한 줄에 하나씩 출력한다.

확률은 소수점 아래 다섯째 자리까지 반올림해 그 형태 그대로 출력한다. 소수점 아래 여섯째 자리가 5 이상이면 올린다. 확률이 $8/9$이면 0.88889, 0이면 0.00000, 1이면 1.00000을 출력한다.