题目内容

某词元推理服务保存了 $n$ 个位置的隐藏状态，要按多头缩放点积注意力更新每个位置。注意力只使用因果窗口内的键，窗口结果经输出投影后与原隐藏状态相加。

头数为 $H$，每头维度为 $d$，模型宽度 $D=H \cdot d$。位置从 $0$ 编号到 $n-1$。第 $i$ 个位置的隐藏状态 $X_i$ 是长度为 $D$ 的整数向量。另有四个 $D \times D$ 整数矩阵 $W_q,W_k,W_v,W_o$。矩阵乘向量规定为 $(Wx)_r=\sum_{c=0}^{D-1} W_{r,c} x_c$。

更新步骤

对每个位置先做线性投影

第 $h$ 头（$h=0,1,\ldots,H-1$）取上述向量中下标落在 $[hd,(h+1)d)$ 的连续一段，记为 $Q_i^{(h)},K_i^{(h)},V_i^{(h)}$。

位置 $i$ 能注意到位置 $j$，当且仅当 $0 \le i-j < w$。对每个头、每个位置，只在可见的 $j$ 上计算

$\sqrt{d}$ 为正平方根，点积为对应分量乘积之和。记该行可见分数的最大值为 $m_{h,i}$。可见位置的权重为

权重与 $C_i^{(h)}$ 的求和都只含可见位置。该头上下文为

把 $C_i^{(0)},\ldots,C_i^{(H-1)}$ 按头序首尾相接得到 $U_i$，再计算

指数、除法与求和使用双精度浮点。$Y_i$ 的每个分量按四舍五入保留 4 位小数，一半远离 0，输出固定 4 位小数。

输入描述

第一行四个整数 $n,H,d,w$。

接下来 $n$ 行，每行 $D$ 个整数，依次是 $X_0,\ldots,X_{n-1}$。

接下来 $D$ 行，每行 $D$ 个整数，按行优先给出 $W_q$。其后用同样的格式依次给出 $W_k,W_v,W_o$。

约束

$1 \le n \le 100$，$1 \le H \le 4$，$1 \le d \le 6$，$1 \le w \le n$，且 $D=H \cdot d \le 16$。

$X_i$ 与 $W_q,W_k,W_v,W_o$ 的每个元素都是整数，绝对值不超过 $4$。

输出描述

输出 $n$ 行。第 $i$ 行为 $Y_i$ 的 $D$ 个分量，同一行内用一个空格分隔。

样例1

输入

2 2 1 2
1 0
0 1
1 0
0 1
1 0
0 1
1 0
0 1
1 0
0 1

输出

2.0000 0.0000
0.5000 1.7311

说明

四个矩阵都是单位阵，因此 $Q=K=V=X$，输出投影不改变 $U_i$。$d=1$，分数就是对应分量的乘积。头 0 取第 0 分量，头 1 取第 1 分量。$w=2$ 时位置 0 只看到自己，位置 1 看到 0 和 1。

位置 0 两头的上下文是 $1$ 和 $0$，与 $X_0$ 相加得 $2.0000\ 0.0000$。

位置 1 头 0 的两个分数都是 $0$，上下文是 $0.5$。头 1 的分数是 $0$ 和 $1$，减去 $1$ 后上下文是 $1/(1+e^{-1})$。与 $X_1=(0,1)$ 相加后为 $0.5000\ 1.7311$。

样例2

输入

3 1 1 2
1
2
3
2
-1
3
1

输出

4.0000
5.0540
9.0074

说明

$W_q,W_k,W_v,W_o$ 分别是 $2,-1,3,1$，因此 $Q=(2,4,6)$，$K=(-1,-2,-3)$，$V=(3,6,9)$。$w=2$。

位置 0 只看到自己，分数 $2\times(-1)=-2$，上下文 $3$，与 $1$ 相加得 $4.0000$。

位置 1 看到 0 和 1，分数为 $-4,-8$。减去 $-4$ 后两项是 $1$ 与 $e^{-4}$，上下文约为 $3.0539586$，与 $2$ 相加后保留 4 位得 $5.0540$。

位置 2 与位置 0 的下标差为 $2$，不满足 $i-j<w$，看不到位置 0，只看到 1 和 2。分数为 $-12,-18$，上下文约为 $6.0074179$，与 $3$ 相加后为 $9.0074$。