九条可怜是一个爱打乒乓球的女孩子。

今天实验室组织了一场乒乓球比赛。实验室一共租了 $n$ 个乒乓球桌，因此一共有 $2n$ 个人参加比赛。乒乓球桌的编号从 $1$ 到 $n$，参赛选手的编号从 $1$ 到 $2n$。

可怜给出了一个长度为 $2n$ 的排列 $p$ 表示第一轮比赛的分组情况：第一轮编号为 $p_{2i-1}$ 和 $p_{2i}$ 的选手在第 $i$ 个乒乓球桌前进行比赛。比赛一共有 $m+1$ 轮（包括第一轮），第 $t$ 轮的分组按照如下方式给定：

• 对于 $i \in [2,n-1]$，第 $i$ 桌的比赛双方是第 $t-1$ 轮中第 $i-1$ 桌的胜者和第 $i+1$ 桌的负者。
• 第 $1$ 桌的比赛双方是第 $t-1$ 轮中第 $1$ 桌和第 $2$ 桌的负者。
• 第 $n$ 桌的比赛双方是第 $t-1$ 轮中第 $n$ 桌和第 $n-1$ 桌的胜者。

乒乓球是一个充满魅力的游戏，即使比赛双方水平差距较大，弱势的一方也是有概率获胜的。在这场乒乓球赛的每场对局中，编号小的人有 $\frac{1}{3}$ 的概率获胜，编号大的人有 $\frac{2}{3}$ 的概率获胜（所有随机都是独立的）。

现在，可怜想要预测比赛的走向，因此她想要对每一个选手 $i \in [1,2n]$ 以及每一张桌子 $j \in [1,n]$，计算在第 $m+1$ 轮比赛中，第 $i$ 个选手在第 $j$ 张桌子比赛的概率。你能帮帮她吗？

输入格式

第一行输入两个正整数 $n,m$，分别表示乒乓球桌的数量以及比赛的轮数（准确来讲是轮数减一）。

第二行输入一个长度为 $2n$ 的排列，表示第一轮的分组情况。

输出格式

输出 $2n$ 行每行 $n$ 个整数。第 $i$ 行第 $j$ 个整数表示第 $i$ 个人第 $m+1$ 轮在第 $j$ 张桌子比赛的概率。

请对 $998244353$ 取模后输出，即如果概率的最简分数表示是 $\frac{x}{y}(x \geq 0,y \geq 1, \gcd(x,y) = 1)$，那么输出 $x \times y^{-1} \text{ mod } 998244353$.

样例数据

样例 1 输入

2 2
1 2 3 4

样例 1 输出

665496236 332748118
665496236 332748118
332748118 665496236
332748118 665496236

样例 2 输入

5 10
10 8 2 4 3 6 7 1 9 5

样例 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

子任务

本题分为 $4$ 个子任务，你需要通过所有子任务中的所有测试点，才能拿到这个子任务的分数：

子任务一（$9$ 分），$n \leq 5, m \leq 4$。

子任务二（$17$ 分），$n \leq 5, m \leq 20$。

子任务三（$42$ 分），$n \leq 7, m \leq 20$。

子任务四（$32$ 分），$n \leq 9, m \leq 20$。