Rt，否则此题存在严格快于（我完全不会的）"分散层叠算法"的时间复杂度$O(nk+Q)$、空间$O(nk)$的做法。可以参见这个提交。

我想了很多点子，最后觉得应该使用Hash搞。就是最最常见的Hash：

$H(a)=\left(\sum_{i=1}^{k}ans_iB^{i-1}\right)\bmod M$

每次强制在线的询问里同时给出Hash函数的进制$B$和模数$M$即可。可以防止预处理。

另：就算直接把$Qk$个答案全部输出，也存在显然的时间复杂度$O(k\sqrt{nQ}+(nk+Q)\log{nk}+Qk)$、空间复杂度$O(k\sqrt{nQ}+nk)$的做法，即分大小为$k\sqrt{\dfrac{n}{Q}}$的块。实际上还能更快，因为memcpy的常数远小于$1$，假设其常数为$\dfrac{1}{w}$，就可以把分块大小改成$k\sqrt{\dfrac{n}{Qw}}$。参见我自己的提交。征求能够把这种做法卡掉的$n,Q,k$。