P11503 [NordicOI 2018] Nordic Camping

译自 Nordic Olympiad in Informatics 2018 [Nordic Camping](https://noi18.kattis.com/contests/noi18/problems/camping)。 upd 2025/1/3 13:18：**本题原题未说明 $K$ 代表什么。搬题人经过 assert 认为是网格中 `#` 的个数。**

在北欧高地露营时，能否找到可靠的水源是生死攸关的问题。传统上，北欧露营者总是将帐篷搭在水源上，这样可以随时取水，而不必出门。北欧人的另一个奇怪传统是他们的帐篷。他们只使用正方形帐篷。 北欧高地的营地可能非常崎岖。Jon 正在设置一个新营地，他已经调查了所有可用的区域，并将无法使用的区域标记出来。我们可以将营地建模为一个 $N \times M$ 的网格，其中每个格子要么是崎岖的（不可用），要么是平坦的（可用）。 对于每一个水源，你能帮助 Jon 确定能够覆盖该水源的最大正方形帐篷的大小吗？  图1：第二个样例以及覆盖水源 $(3, 2)$ 的最大正方形帐篷的区域。这也恰好是覆盖水源 $(5, 4)$ 的最大正方形帐篷。

无

无

你的解法将在一组子任务上进行评分。每个子任务包含多个测试用例。要获得子任务的分数，你的解法必须通过子任务中的所有测试用例。 | 子任务 | 分数 | 限制条件 | | ------ | ---- | ------------------------------------------ | | $1$ | $20$ | $N,M\leq 50$，$Q\leq 1000$ | | $2$ | $25$ | $N,M\leq 800$，$K\leq 10^5$，$Q\leq 10^5$ | | $3$ | $20$ | $N\leq 10$，$M\leq 2000$，$Q\leq 500$ | | $4$ | $35$ | $N,M\leq 2000$，$K\leq 10^5$，$Q\leq 10^5$ |