Description

For every $0 \le i, j < 4$, you are given $x(i, j)$ such that:

1. Commutativity: $x(i,j)=x(j,i)$.
2. Associativity: $x(x(i,j),k)=x(i,x(j,k))$.
3. Identity element: $x(0,i)=i$.

Define a function $f(n)$ such that:

1. $f(p^k)=pk\bmod 4$.
2. When $\gcd(a,b)=1$, $f(ab)=x(f(a),f(b))$.

In particular, $f(1)=0$.

Define the function $g$ as:

Given $m$ and $k$, for all $1 \le i \le \lfloor \sqrt m \rfloor$, compute the values of $g\left(\left\lfloor \frac{m}{i} \right\rfloor, k, r\right)$ for all $0 \le r < 4$. Take all answers modulo $998244353$.

Input Format

The first line contains two integers $m$ and $k$.
Then follow $4$ lines, each with $4$ integers. The $j$-th integer on the $i$-th line is $x(i-1,j-1)$.

Output Format

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

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

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

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

457599333 476580683 403589597 762762658
361221912 612412943 661908092 483645330
242804711 682542199 535167020 465246643
913280460 516845083 917292729 390364642
39265044 919790719 181416471 421087779
530140662 31014314 181416471 226287885
982924733 31014314 851084249 226287885
982924733 938693280 851084249 226287885
982924733 938693280 851084249 435036575
982924733 938693280 851084249 138976409

Hint

This problem does not use bundled tests, and the testdata has a slight difficulty gradient.

For $16\%$ of the testdata, $m \le 10^6$.

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

Translated by ChatGPT 5