题目描述

给定三个整数矩阵 $Q$、$K$、$V$，尺寸均为 $L\times D$，以及 $G$ 个全局位置，它们构成集合 $P$。

对位置 $i$，先确定可参与注意力的下标集合 $C_i$：

集合内同一位置只计一次。

对 $j\in C_i$，注意力分数定义为

只保留满足 $score(i,j)>0$ 的位置，再从中选出至多 $T$ 个分数最大的候选，得到 $A_i$。分数相同时，下标 $j$ 较小者优先。若正分数候选个数不超过 $T$，则全部保留。

输出矩阵 $O$：当 $A_i$ 非空时

当 $A_i$ 为空时，$O[i]$ 的每一维都是 $0$。

请输出最终的 $L\times D$ 矩阵 $O$。

输入描述

第一行五个整数：

L D G W T

依次为序列长度、特征维数、全局位置个数、局部窗口半径、每个位置最多保留的候选数。

若 $G>0$，下一行 $G$ 个互不相同的整数：

p1 p2 ... pG

表示全局位置，下标从 $0$ 开始。

若 $G=0$，则没有这一行，接下来直接读矩阵 $Q$。

随后 $L$ 行，每行 $D$ 个整数，为矩阵 $Q$。

随后 $L$ 行，每行 $D$ 个整数，为矩阵 $K$。

随后 $L$ 行，每行 $D$ 个整数，为矩阵 $V$。

输出描述

输出 $L$ 行，每行 $D$ 个整数，表示矩阵 $O$。

同一行相邻整数之间用一个空格分隔。

样例1

输入：

5 2 2 1 2
0 3
1 0
1 0
2 0
0 1
1 1
2 0
1 0
3 0
0 2
-1 1
1 1
2 2
3 3
4 4
5 5

输出：

11 11
11 11
22 22
13 13
10 10

说明

全局位置集合为 $P=\{0,3\}$。

对 $i=1$（非全局）：$C_1=\{0,1,2,3\}$，分数为 $2,1,3,0$。丢掉非正分数后，按 $T=2$ 取位置 $2$ 与 $0$：

对全局位置 $i=3$：$C_3=\{0,1,2,3,4\}$，正分数只有 $2$（对应 $j=3$）和 $1$（对应 $j=4$）：

对 $i=4$：$C_4=\{0,3,4\}$，分数为 $2,2,0$。$0$ 被丢掉，两个分数 $2$ 并列时先取较小下标 $0$，再取 $3$：

样例2

输入：

3 1 0 0 1
1
2
-1
-2
3
1
10
20
30

输出：

0
120
0

说明

本例 $G=0$，没有全局位置行。$W=0$，每个位置的 $C_i$ 只含自己。

$i=0$ 的分数为 $-2$，不进入 $A_0$，输出 $0$。

$i=1$ 的分数为 $6$，因此

$i=2$ 的分数为 $-1$，输出 $0$。

提示

$1\le L\le 10000$

$1\le D\le 64$

$0\le G\le \min(L,32)$

$0\le W\le 128$

$1\le T\le \min(L,16)$

$0\le p_i<L$

全局位置两两不同

$-10\le Q[i][j],K[i][j],V[i][j]\le 10$

全局位置的输入顺序不影响结果。

矩阵与序列下标均从 $0$ 开始。

中间结果和最终结果均在 $64$ 位有符号整数范围内。