背景

书虫有 $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$ 为：

给定 $m$ 和 $k$，请对所有 $1\le i\le\lfloor\sqrt m\rfloor$，计算所有 $0\le r<4$ 的 $g(\lfloor\frac mi\rfloor,k,r)$ 值。

输入格式

第一行一个正整数 $m$。
第二行一个非负整数 $k$。

输出格式

输出 $\lfloor\sqrt m\rfloor$ 行。
第 $i$ 行包含四个非负整数，第 $r$ 非负整数为 $g(\lfloor\frac mi\rfloor,k,r)$。

10 0

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

提示

样例 1 解释

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

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le m\le10^{10}$，$0\le k\le1$。