P7571 「MCOI-05」幂积

书虫有 $10^{10}$ 块金牌！ 书虫正在整理他的 $n$ 块金牌。他的金牌分四类，依次为：NOI 金牌，IOI 金牌，IMO 金牌，ICPC WF 金牌。他在第 $1$ 到第 $n$ 天中各 AK 了一场比赛，得到以上类金牌之一。对于给定参数 $k$，第 $i$ 天得到的金牌的价值为 $1$ 如果 $k=0$，为 $i$ 如果 $k=1$。 书虫每天会通过奇妙手段选择他当天应该 AK 什么比赛。对于第 $i$ 天，令 $i=p_1\times p_2\times\dots p_k$，其中 $p_1,p_2,\dots,p_k$ 均为质数。书虫会计算 $x$，其中 $x$ 是 $p_1+p_2+\dots+p_k$ 对 $4$ 取模的余数，并且 AK 第 $x+1$ 类比赛，得到一个第 $x+1$ 类比赛的金牌。 书虫的金牌实在太多了，于是他邀请您帮他计算，他这 $n$ 个金牌里，每一类中的**价值**之和。但是书虫不满足于这个，于是他给您 $m$ 和 $k$，请您对每一个 $1\le i\le\lfloor\sqrt m\rfloor$ 计算当 $n=\lfloor\frac mi\rfloor$ 时候的答案。

定义函数 $f(\prod p_i^{a_i})=\sum a_ip_i$，其中 $p_i$ 为质数。特别，$f(1)=0$。 对于 $k\in\{0,1\}$，定义函数 $g$ 为： $$g(n,k,r)=\sum_{i=1}^ni^k[f(i)\equiv r\pmod 4]$$ 给定 $m$ 和 $k$，请对所有 $1\le i\le\lfloor\sqrt m\rfloor$，计算所有 $0\le r

无

无

#### 样例 1 解释 $f=[0,2,3,0,1,1,3,2,2,3,\dots]$ #### 数据规模与约定 **本题采用捆绑测试**。 | Subtask | 分数 | $m$ | $k$ | | - | - | - | - | | 1 | 5 pts | $\le 10^7$ | 无 | | 2 | 15 pts | $\le10^9$ | $=0$ | | 3 | 25 pts | 无 | $=0$ | | 4 | 25 pts | $\le10^9$ | 无 | | 5 | 30 pts | 无 | 无 | 对于 $100\%$ 的数据，$1\le m\le10^{10}$，$0\le k\le1$。