给定序列 $a$，$q$ 次询问，每次询问区间内所有数的出现次数是否为 $k$ 的倍数

$n,q \le 10^6,a_i \le 10^9$

怎么做？如果 $k=2$ 有没有比较优秀的做法呢