见这个附件 https://www.luogu.com.cn/problem/U283884

能把裸暴力卡掉，放了分块

$q = 1.5 \times 10 ^ 4$，其他和原题范围一样