Kelian Jiutiao is a girl who loves playing table tennis.
Today, the laboratory organized a table tennis tournament. The laboratory rented $n$ table tennis tables, so there are $2n$ people participating in the tournament. The table tennis tables are numbered from $1$ to $n$, and the participants are numbered from $1$ to $2n$.
Kelian provided a permutation $p$ of length $2n$ representing the grouping for the first round: in the first round, the participants numbered $p_{2i-1}$ and $p_{2i}$ compete at table $i$. There are a total of $m+1$ rounds (including the first round). The grouping for round $t$ is determined as follows:
- For $i \in [2, n-1]$, the match at table $i$ is between the winner of table $i-1$ and the loser of table $i+1$ from round $t-1$.
- The match at table $1$ is between the loser of table $1$ and the loser of table $2$ from round $t-1$.
- The match at table $n$ is between the winner of table $n$ and the winner of table $n-1$ from round $t-1$.
Table tennis is a fascinating game; even if there is a large skill gap between the two players, the weaker side still has a chance to win. In every match of this tournament, the person with the smaller number has a $\frac{1}{3}$ probability of winning, and the person with the larger number has a $\frac{2}{3}$ probability of winning (all random events are independent).
Now, Kelian wants to predict the course of the tournament. Therefore, for every participant $i \in [1, 2n]$ and every table $j \in [1, n]$, she wants to calculate the probability that participant $i$ plays at table $j$ in the $(m+1)$-th round. Can you help her?
Input
The first line contains two positive integers $n$ and $m$, representing the number of table tennis tables and the number of rounds (specifically, the number of rounds minus one).
The second line contains a permutation of length $2n$, representing the grouping for the first round.
Output
Output $2n$ lines, each containing $n$ integers. The $j$-th integer in the $i$-th line represents the probability that participant $i$ plays at table $j$ in the $(m+1)$-th round.
Please output the results modulo $998244353$. That is, if the simplest fractional representation of the probability is $\frac{x}{y}$ ($x \geq 0, y \geq 1, \gcd(x, y) = 1$), output $x \times y^{-1} \pmod{998244353}$.
Examples
Input 1
2 2 1 2 3 4
Output 1
665496236 332748118 665496236 332748118 332748118 665496236 332748118 665496236
Input 2
5 10 10 8 2 4 3 6 7 1 9 5
Output 2
47875968 906617325 11968992 57681074 972345348 438541320 276952489 426902261 487715346 366377291 448252084 558334467 922032067 549111872 517002570 583492040 55073960 225988679 57913693 75775982 404707960 237395064 269883170 427433686 657068827 244577760 932979114 917209059 905241238 992970242 471889317 515941754 455505693 9295155 543856788 735864854 669298224 418128683 606426632 565014667 534196032 890427380 448954830 868220734 252934084 83580079 946446343 894648333 23937984 47875968
Subtasks
This problem is divided into 4 subtasks. You must pass all test cases in a subtask to receive the points for that subtask:
Subtask 1 (9 points): $n \leq 5, m \leq 4$.
Subtask 2 (17 points): $n \leq 5, m \leq 20$.
Subtask 3 (42 points): $n \leq 7, m \leq 20$.
Subtask 4 (32 points): $n \leq 9, m \leq 20$.