$O(n^2)$预处理,对于每个询问O(1)查询，略微卡常，直接全过

提交记录如下

https://www.luogu.com.cn/record/75938310

建议管理员增强数据，否则将导致复杂度不正确的算法通过本题