考虑枚举左右边界，则可以得到一个 $W\times H$ 的矩形，而正方形能取到的最大边长即为 $\min\{W,H\}$。这样的复杂度是每次询问 $O(N^2)$。

注意到在右端点向右移动的过程中，$W$ 是递增的，而 $H$ 是递减的。找到第一个 $W\ge H$ 的位置，然后就只需要考虑这个位置和前一个位置。找到这个位置可以用二分，这样每次询问就是 $O(N\log N)$。

注意到在左端点向左移动的过程中，同样有 $W$ 是递增的，$H$ 是递减的。因此上一段所说的位置只会向左移动，即可做到 $O(N)$。

总复杂度 $O(NQ)$。