问题描述

Softmax($\frac{Q\times K^{T}}{\sqrt{d}}$) $\times V$ 是 Transformer 中注意力模块的核心算式，其中 $Q,K,V$ 均为 $n\times d$ 的矩阵，$K^{T}$ 表示 $K$ 的转置，$\times$ 表示矩阵乘法。为简化计算，题目将 Softmax 用一维向量 $W$（长度为 $n$）替代，得到简化的表达式：

这里点乘 $W\cdot (Q\times K^{T})$ 表示按行标量缩放：若 $M=Q\times K^{T}$，记 $W(i)$ 为向量 $W$ 的第 $i$ 个元素，则把 $M$ 的第 $i$ 行的每个元素都乘以 $W(i)$，得到新的 $n\times n$ 矩阵，再与 $V$ 相乘，结果为一个 $n\times d$ 矩阵。

现给出矩阵 $Q,K,V$ 和向量 $W$，请计算上述简化表达式的结果矩阵并输出。

输入格式

• 第一行包含两个正整数 $n$ 和 $d$，表示矩阵的维度（行数与列数）；

• 接着依次输入矩阵 $Q$、$K$、$V$。每个矩阵按行给出，共 $n$ 行，每行包含 $d$ 个用空格分隔的整数；第 $i$ 行第 $j$ 个数对应矩阵第 $i$ 行第 $j$ 列的元素；

• 最后一行包含 $n$ 个整数，表示向量 $W$ 的 $n$ 个元素（$W(1),W(2),\dots,W(n)$）。

• $1\le n\le 10^4$，$1\le d\le 20$；

• 矩阵与向量中的元素均为整数，且绝对值不超过 $1000$。

输出格式

输出共 $n$ 行，每行包含 $d$ 个用空格分隔的整数，表示计算结果矩阵的第 $1$ 行到第 $n$ 行。

样例输入

3 2
1 2
3 4
5 6
10 10
-20 -20
30 30
6 5
4 3
2 1
4 0 -5

样例输出

480 240
0 0
-2200 -1100