P7571 "MCOI-05" Power Product.

Bookworm has $10^{10}$ gold medals. Bookworm is organizing his $n$ gold medals. His medals have four types, in order: NOI gold medal, IOI gold medal, IMO gold medal, ICPC WF gold medal. On day $1$ to day $n$, he ACs a contest each day and gets one gold medal of one of the types above. For a given parameter $k$, the value of the gold medal obtained on day $i$ is $1$ if $k=0$, and $i$ if $k=1$. Every day, Bookworm uses some magical method to choose which contest to AC that day. For day $i$, let $i=p_1\times p_2\times\dots p_k$, where $p_1,p_2,\dots,p_k$ are all primes. Bookworm computes $x$, where $x$ is the remainder of $p_1+p_2+\dots+p_k$ modulo $4$, and then ACs the $(x+1)$-th type of contest, obtaining a gold medal of the $(x+1)$-th type. Bookworm has too many medals, so he invites you to help him compute, among these $n$ medals, the sum of **values** in each type. But Bookworm is not satisfied with that. He gives you $m$ and $k$, and asks you to compute the answer for each $1\le i\le\lfloor\sqrt m\rfloor$ when $n=\lfloor\frac mi\rfloor$.

Define the function $f(\prod p_i^{a_i})=\sum a_ip_i$, where $p_i$ are primes. In particular, $f(1)=0$. For $k\in\{0,1\}$, define the function $g$ as: $$g(n,k,r)=\sum_{i=1}^ni^k[f(i)\equiv r\pmod 4]$$ Given $m$ and $k$, for all $1\le i\le\lfloor\sqrt m\rfloor$, compute $g(\lfloor\frac mi\rfloor,k,r)$ for all $0\le r

The first line contains a positive integer $m$. The second line contains a non-negative integer $k$.

Output $\lfloor\sqrt m\rfloor$ lines. The $i$-th line contains four non-negative integers, and the $r$-th non-negative integer is $g(\lfloor\frac mi\rfloor,k,r)$.

#### Explanation of Sample 1 $f=[0,2,3,0,1,1,3,2,2,3,\dots]$ #### Constraints **This problem uses bundled testdata**. | Subtask | Score | $m$ | $k$ | | - | - | - | - | | 1 | 5 pts | $\le 10^7$ | None | | 2 | 15 pts | $\le10^9$ | $=0$ | | 3 | 25 pts | None | $=0$ | | 4 | 25 pts | $\le10^9$ | None | | 5 | 30 pts | None | None | For $100\%$ of the testdata, $1\le m\le10^{10}$ and $0\le k\le1$. Translated by ChatGPT 5