Modular Summation over a Multiplicative Function with Modulo 4

You are given two integers m and k. Define a binary operation \(x(i,j)\) over the set \( \{0,1,2,3\}\) satisfying the following properties for every \(0 \le i,j < 4\):

• Commutativity: \(x(i,j)=x(j,i)\).
• Associativity: \(x(x(i,j),k)=x(i,x(j,k))\) for all \(k\).
• Identity: \(x(0,i)=i\).

In this problem, we take \(x(i,j)\) to be addition modulo 4 (i.e. \(x(i,j)=i+j\ \(\bmod\ 4\)\)), which indeed satisfies the conditions above.

Using \(x\), we define a multiplicative function \(f(n)\) for every positive integer \(n\) as follows:

1. For a prime power \(p^k\), \(f(p^k)= pk \;\bmod\; 4\).
2. For \(a\) and \(b\) with \(\gcd(a,b)=1\), \(f(ab)= x(f(a), f(b))\). (In particular, \(f(1)=0\).)

Define the function \(g(n,k,r)\) as

\[ g(n,k,r)= \sum_{i=1}^{n} i^k \cdot [f(i)=r], \]

where \([f(i)=r]\) is an indicator function (it equals 1 if \(f(i)=r\) and 0 otherwise).

Your task is: For each integer \(i\) satisfying \(1 \le i \le \lfloor \sqrt{m} \rfloor\), let \(n = \lfloor \frac{m}{i} \rfloor\). For each residue \(r\) in \(\{0,1,2,3\}\), compute \(g(n,k,r)\) modulo \(998244353\).

Input Format: The input consists of a single line with two integers m and k.

Output Format: Output \(\lfloor \sqrt{m} \rfloor\) lines. The i-th line (for \(1 \le i \le \lfloor \sqrt{m} \rfloor\)) should contain 4 space-separated integers, corresponding to \(g(\lfloor m/i \rfloor,k,0)\), \(g(\lfloor m/i \rfloor,k,1)\), \(g(\lfloor m/i \rfloor,k,2)\), and \(g(\lfloor m/i \rfloor,k,3)\), each taken modulo \(998244353\).

Note: Since \(f(n)\) is multiplicative and defined using the operation \(x\) (which we interpret as addition modulo 4), for any prime power \(p^a\) we have \(f(p^a)= (p \times a)\ \(\bmod\ 4\) and for two coprime numbers \(a\) and \(b\), \(f(ab)= (f(a)+f(b))\ \(\bmod\ 4\)).

inputFormat

The input consists of a single line containing two integers m and k separated by a space.

Constraints (for implementation purposes):

• 1 \(\le m \le 10^5\)
• 0 \(\le k \le 10^5\)

outputFormat

For each \(i\) from \(1\) to \(\lfloor \sqrt{m} \rfloor\), output a line with 4 space-separated integers: the values of \(g(\lfloor m/i \rfloor,k,0)\), \(g(\lfloor m/i \rfloor,k,1)\), \(g(\lfloor m/i \rfloor,k,2)\) and \(g(\lfloor m/i \rfloor,k,3)\) modulo \(998244353\).

sample

10 1

5 11 19 20
5 5 2 3
1 0 2 3

</p>