2797 「CCO 2015」挖掘

本题译自 CCO 2015 Day2 T3「Eggscavation」

度假时间到了！你厌倦了 C shell（编程语言），所以你决定去收集贝壳（Seashell，与 C Shell 同音）。

你决定去游览 Cartesia 国的岛度假。该岛以拥有优美的方形沙滩而著名。该沙滩被划分成 $N\times N$ 的矩阵组成，你带上了你可靠的铲子，你可以用铲子在岛上挖最多 $K\times K$的正方形子矩阵。为了保证你的铲子是可靠的，你所挖的正方形子矩阵要保证所挖的 $K\times K$ 的范围都在沙滩上。

在岛下，有 $M$ 种未探索过的贝壳种类。具体来说，对于每个贝壳种类 $i$，有 $S_i$ 个贝壳在不同的位置。对于每个不同的种类的贝壳，你把它挖出来，然后带回家，然后以每个 $1$ 美元的价格卖给一个科学家。多个同种类的贝壳没有附加价值。

麻烦的是，一种华丽的渡渡鸟在沙滩上跑来跑去。在一个给定时刻，他可能会在一个网格里埋一个蛋，包括那些已经有蛋或者网格的网格。坏消息是，如果你铲子挖出来的 $K\times K$ 的子正方形矩阵里包含渡渡鸟的蛋，科学家会因为你正在危害濒危物种而非常着急，因此没人会给你钱。

想到这些，你决定坐下来，开始写程序，进行模拟挖掘。你将会去计算你的挖掘的可能性，当你在不同时间点以均等可能性选择一个挖掘方案时，需要保证至少一个收入值来偿还你的学生贷款。谁想白忙活一场呢？

第一行包括两个整数 $N,K$，表示岛和铲子的尺寸

第二行一个数 $M$，表示贝壳种类数。接下来 $M$ 行每行表示一个种类 $i$，包含一个整数 $S_i$，接着 $2\times S_i$ 个数，为一些在 $(1,1)$ 与 $(N,M)$ 之间的坐标，表示 $S_i$ 个贝壳埋的位置。

接下来 $T$ 行每行表示一个时间点，按时间由最远到最近排序，每行为如下格式之一： - $1$ $A_i$ $B_i$，表示渡渡鸟在 $(A_i,B_i)$ 下了一个蛋 - $2$ $V_i$，表示我们想计算一个在该时间点获利$>V_i$的随机挖掘的可能性。注意贝壳和蛋在计算时都没有没有被真正地挖出来。

对于每个询问，输出一行表示一次获得至少指定利润的随机挖掘的可能性。你的答案与标准答案之间的差值的绝对值不能大于 $10^{-4}$。

初始时，贝壳的排布如下所示：

我们将用铲子挖至多 $2\times 2$ 的格子，因此我们有 $9$ 种可能的挖掘。 当没有蛋出现时，$8$ 种挖掘包含至少两种贝壳，$3$ 种挖掘包含三种贝壳。

一个蛋掉进了有贝壳 $1,2$ 的方格。

在这种情况下，$\frac{4}{9}$ 的挖掘包含至少两种贝壳且没有蛋，仅有一种挖掘会包含所有种类的贝壳并且没有蛋，那就是挖掘左下角。最终输出指明没有任何一种挖掘包含四种贝壳。

对于至少 $15\%$ 的数据，$1\le N \le 40$；

对于另外 $25\%$ 的数据，所有的更新操作在询问操作前出现；

对于 $100\%$ 的数据，$1\le K \le N\le 2500,$ $0\le M \le 10^5,$ $1\le S_i\le 4,$ $0\le T\le 10000,$ $1\le A_i,B_i \le N,$ $1\le V_i\le 10^9$。