正整数 \(x,y,m\ (x \geq y)\) について常に以下の不等式が成り立ちます．

\[ \lfloor\frac{x}{m}\rfloor \geq \lfloor\frac{y}{m}\rfloor+\lfloor\frac{x-y}{m}\rfloor\]

等号成立条件は \(x\bmod m \geq y \bmod m \) です．（証明略）

今回の問題では，\(A\) の最大値を \(A_{\max}\) とすると，\(1\) 以上 \(A_{\max}\) 以下の各 \(m\) について

\[N \lfloor\frac{A_{\max}}{m}\rfloor = \sum_{i=1}^N (\lfloor\frac{A_i}{m}\rfloor+\lfloor\frac{A_{\max}-A_i}{m}\rfloor)\]

かを判定しておけばクエリに高速に答えられます．

\(\lfloor\frac{A_i}{m}\rfloor\) が取り得る値が \(\sqrt{A_i}\) 種類しかないことに注意すれば，商列挙と imos 法を用いてこの問題を解くことができます．

\(A_{\max}\) が小さい場合は imos 法の配列を陽に管理可能で，\(N\) が小さい場合は取り得る値の集合が小さいので，座圧して imos 法を行えばよいです．