时间限制： 5.0 秒

空间限制： 512 MB

题目背景

$\mathrm{Softmax}(\frac{\mathbf{Q}\times \mathbf{K}^T}{\sqrt d})\times \mathbf{V}$ 是 Transformer 中注意力模块的核心计算模式，其中 $\mathbf{Q}$、$\mathbf{K}$ 和 $\mathbf{V}$ 均是 $n$ 行 $d$ 列的矩阵，$\mathbf{K}^T$ 表示矩阵 $\mathbf{K}$ 的转置，$\times$ 表示矩阵乘法。

题目描述

为了方便计算，顿顿同学将 $\mathrm{Softmax}$ 简化为了点乘一个大小为 $n$ 的一维向量 $\mathbf{W}$：

$$(\mathbf{W}\cdot \mathbf{Q}\times \mathbf{K}^T)\times \mathbf{V} $$

点乘即对应位相乘，记 $\mathbf{W}^{(i)}$ 位向量 $\mathbf{W}$ 的第 $i$ 个元素，即将 $\mathbf{Q}\times \mathbf{K}^T$ 第 $i$ 行中的每个元素都与 $\mathbf{W}^{(i)}$ 相乘。

现给出矩阵 $\mathbf{Q},\mathbf{K},\mathbf{V}$ 和向量 $\mathbf{W}$，试计算顿顿按简化的算式计算的结果。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 $n$ 和 $d$，表示矩阵的大小。

接下来依次输入矩阵 $\mathbf{Q},\mathbf{K},\mathbf{V}$。每个矩阵输入 $n$ 行，每行包含空格分隔的 $d$ 个整数，其中第 $i$ 行的第 $j$ 个数对应矩阵第 $i$ 行第 $j$ 列的元素。

最后一行输入 $n$ 个整数，表示向量 $\mathbf{W}$。

输出格式

输出到标准输出。

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

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

子任务

$70\%$ 的测试数据满足：$n\le 100,d\le 10$；输入矩阵、向量中的元素均为整数，且绝对值均不超过 $30$。

全部的测试数据满足：$n\le 10^4,d\le 20$；输入矩阵、向量中的元素均为整数，且绝对值均不超过 $1000$。

提示

请谨慎评估矩阵乘法运算后的数值范围，并使用适当数据类型存储矩阵中的整数。