考虑依次选取以下 $7$ 个「关键营地」（需要指出的是，这 $7$ 个「关键营地」不一定都存在）：

- $0$ 号「关键营地」为输入的第一个营地。
- $1$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标相同，$y$ 坐标不同的营地。
- $2$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标相同的营地。
- $3$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同的营地。
- $4$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同，与 $3$ 号「关键营地」$x$ 坐标相同，$y$ 坐标不同的营地。
- $5$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同，与 $3$ 号「关键营地」$x$ 坐标不同，$y$ 坐标相同的营地。
- $6$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同，与 $3$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同的营地。

可以证明，如果某个询问有解，则这 $7$ 个「关键营地」中必有一个是该询问的合法解，证明此处从略。

最终的时间复杂度为 $O(n + q)$，空间复杂度为 $O(1)$。