背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

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

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

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

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

输入格式

从标准输入读入数据。

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

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

最后一行输入 $n$ 个整数，表示向量 $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$。

提示

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