RT.
思路是根号分治，分别用ST表和主席树，一直WA on test 4，而且所有的Query都会输出0.不太明白是什么原因导致输出0，检查了一下，自认为所有的该取模的地方都取模了，也没有什么溢出的情况。

代码有点长，放二楼。