Maze

时间限制:10s      空间限制:256MB

题目描述

众维拉先后在中土大陆上创造了精灵、人类以及矮人,其中矮人是生性喜好常年居住在地下的洞穴的存在,他们挖掘矿物甚至宝石,甚至用他们的勤劳勇敢智慧在地底下创造出了辉煌宏大的宫殿,错综复杂的迷宫——嗯,没错,现在KPM这个毛小孩要扯上关系的就是迷宫啦~
描述
KPM在矮人的王国发现了一个迷宫,现在这个迷宫是这样的:迷宫的主体由排列成一个整齐的n行m列的矩阵的房间组成,同一行或者是同一列之中相邻的房间的距离为1,我们用(x,y)来表示第x行的第y列的房间,然后KPM惊奇的发现,迷宫的入口(不包含在矩阵状的房间中)与第一行的所有房间之间都有通道连接,其中与第i个房间连接的通道数目为a(i),然后对于任意两个房间(x,y),(u,v),当且仅当两个房间之间的曼哈顿距离不大于k且处于相邻的两行,即|x-u|+|y-v|<=k,且|x-u|=1,房间直接存在通道连接,然后根据KPM第XX定律,KPM发现对于入口到第一行房间的所有通道,KPM只能通过其从入口走向房间,却没办法反过来走,对于两个房间(x,y),(u,v),假如两个房间之间存在连边,KPM只能从行数小的那行走到行数大的那行,而且还要保证他走过的房间的列数是单调不递减的,而且,这如果这两个房间之间的曼哈顿距离为d,这两个房间的直接相连通道数目为b(d),也就是说,假如KPM可以从(x,y)走到(u,v),必须有u=x+1,v>=y,且从(x,y)到(u,v)总共有b(v-y+1)条通道直接连接。现在,KPM无聊的想知道,从入口出发,到达第n行的第i个房间,他总共有多少种走法,由于他有数字恐惧症,所以你只需要告诉他答案对19取模的结果即可。


输入格式

输入第一行包括三个整数n,m,k;
输入第二行包括m个整数,其中第i个整数为a(i);
输入第三行包括k个整数,其中第i个整数为b(i)。


输出格式


输出包括一行,该行包括m个整数,其中第i个整数表示从入口到达(n,i)的方案数对19的取模(注意:只要经过的直接通路序列不同即算成不同方案)。


样例输入

3 2 2
3 4
1 2

样例输出

3 16

提示


样例解释
对于到达(n,1)经过的房间序列有一种S->(1,1)->(2,1)->(3,1),存在3*1*1=3种通路情况;
对于到达(n,2)经过的房间序列有三种,分别为:
S->(1,1)->(2,1)->(3,2),有3*1*2=6种通路情况,
S->(1,1)->(2,2)->(3,2),有3*2*1=6种通路情况,
S->(1,2)->(2,2)->(3,2),用4*1*1=4中通路情况,
因此到达(3,2)总有6+6+4=16种通路情况。(注:S表示入口)
数据范围与约定
对于10%的数据,保证n,m<=1000,k<=10
对于另外20%的数据,保证n<=10^18,m<=100
对于另外20%的数据,保证n<=10^18,m<=400
对于剩下50%的数据,保证n<=10^18,m<=10000
对于100%的数据,保证a(i),b(i)<5,k<=m,min{n,m,k}>0


题目来源

KpmCup #1