题目描述

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君好棒！不过这个题怎么做呢？」

输入格式

第一行三个整数，表示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

输出格式

输出n=3^m行，每行一个整数，表示每个人最终的得分。 其中第i行表示第i个人的得分f_{t,i}。

1 1 10009
10 100 1000
2 3
4

4320
3240
2430

提示

没有写明提示

题目来源

没有写明来源