线段树解法：不仅要在 query 函数内取模，输出时也要取模，否则会在 $n$ 为二整数幂时被卡。

例如 #4 的数据就能卡掉：

Input
1
1000000000