Description

n=3^m个人在玩石头剪刀布，一共有t轮游戏，每轮有m次石头剪刀布。

在同一轮的m次游戏中，每个人的决策必须是提前确定的，也就是说不能采用随机策略，也不能根据前若干局的结果决定下一局的决策；这样，显然一共有n=3^m种决策。

这n=3^m个人会采取两两不同的决策。为了方便表达，对于第x（0≤x<n）个人，将x转换成三进制得到一个m位的数。其中0表示剪刀，1表示石头，2表示布。就得到了第x个人采取的策略。

由于编号是固定的，因此每个人在不同轮的m次游戏中都会采取同一套决策。

第x个人在最初时有一个分数f ~0,x~ 。

在第i轮中，他将和另一个人y进行m次的石头剪刀布的比赛。

我们用W(x,y)表示x在和y的m次比赛中赢的次数；用L(x,y)表示x在和y的m次比赛中输的次数。

在第i轮结束之后，第x个人分数是：

fi,x=∑f~i−1,y~b ~u,v~ (0≤y<n)

其中u=W(x,y)=L(y,x),v=L(x,y)=W(y,x)，平局不计入次数；bu,v则是一个给定的评分数组。

注意即使y和x一样（自己转移到自己）也会乘上一个系数b0,0（即自己跟自己打全为平局）。

显然随着轮数越来越多，分数也会越来越大，这个计分系统和我们平时用的计算机一样，也会溢出。当要储存的分数f大于等于p的时候，就会变成f mod p。

B君想知道t轮之后所有人的分数，也就是f ~t,0~ ,f ~t,1~ ,…,f ~t,n−1~ 。

G君：「诶，我发现这个数p有特殊的性质诶！不存在两个正整数，使得他们倒数的和等于3/p」

B君：「G君好棒！不过这个题怎么做呢？」

Format

Input

第一行三个整数，表示m,t,p。保证0≤m≤12，0≤t≤1000000000，1≤p≤1000000000。

第二行有n=3m个整数，表示f ~0,0~ ,f ~0,1~ ,…,f ~0,n−1~ 。保证0≤f ~0,i~ <p。

接下来的部分是一个数组b，第1行m+1个数，第2行m个数……第m+1行1个数。

其中第i行的第j个数为b ~i−1,j−1~ （i,j≥1,i+j−2≤m），保证0≤b ~i,j~ <p。

不存在两个正整数，使得他们倒数的和等于3/p。即不存在正整数x,y>0，使得1/x+1/y=3/p。

m<=12,T<=10^9

Output

输出n=3^m行，每行一个整数，表示每个人最终的得分。

其中第i行表示第i个人的得分f ~t,i~ 。

Samples

1 1 10009
10 100 1000
2 3
4

4320
3240
2430