You are given a commutative associative unitary function \(x(i,j)\) defined over all \(0\le i,j,x(i,j)\lt 4\). In other words, this function satisfies, for all \(0\le i, j, k \lt 4\):

1. \(x(i,j)=x(j,i)\)
2. \(x(x(i, j), k)=x(i, x(j, k))\)
3. \(x(0, i)=i\)

Define a function \(f(n)\) for all positive integers \(n\) such that:

1. \(f(p^k)=(pk)\bmod 4\), that is, the remainder when \(pk\) is divided by 4
2. If \(\gcd(a, b)=1\), then \(f(ab)=x(f(a),f (b))\)

Define:

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

where \([f(i)=r]\) is the Iverson bracket.

Given the function \(x\) and two integers \(m\), \(k\), for all integers \(1\le i\le\lfloor\sqrt n\rfloor\), calculate \(g(\lfloor\frac ni\rfloor, k, 0...3)\) modulo \(998\ 244\ 353\).

Input

The first line contains two integers \(m\) and \(k\). (\(1\le m\le 10^{10}\), \(0 \le k \le 1000\))

The following 4 lines contains 4 integers each. The i-th row j-th integer contains \(x(i-1,j-1)\).

Output

Output \(\lfloor\sqrt n\rfloor\) lines containing 4 integers each. The i-th row j-th integer contains \(g(\lfloor\frac ni\rfloor, k, j-1)\) modulo \(998244353\).

Example

Input:

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

Output:

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

Input:

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

Output:

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