Background

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$.

Problem Description

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:

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<4$.

Input Format

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

Output Format

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)$.

10 0

2 2 3 3
2 1 1 1
1 0 1 1

Hint

Explanation of Sample 1

$f=[0,2,3,0,1,1,3,2,2,3,\dots]$

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le m\le10^{10}$ and $0\le k\le1$.

Translated by ChatGPT 5