Background

The testdata on Luogu is for non-official communication only and is not official testdata. Official judging link: https://www.cspro.org/。

Problem Description

$\text{Softmax}(\frac{Q \times K^T}{\sqrt{d}}) \times V$ is the core expression of the attention module in Transformers, where $Q$, $K$, and $V$ are all matrices with $n$ rows and $d$ columns, $K^T$ denotes the transpose of matrix $K$, and $\times$ denotes matrix multiplication.

To make computation easier, student Dundun simplifies Softmax into an element-wise multiplication by a one-dimensional vector $W$ of length $n$:

Element-wise multiplication here means multiplying corresponding positions. Let $W^{(i)}$ be the $i$-th element of vector $W$. That is, every element in the $i$-th row of $(Q \times K^T)$ is multiplied by $W^{(i)}$.

Given matrices $Q$, $K$, and $V$, and vector $W$, compute the result produced by Dundun using the simplified formula.

Input Format

Read input from standard input.

The first line contains two positive integers $n$ and $d$ separated by spaces, representing the size of the matrices.

Then matrices $Q$, $K$, and $V$ are given in order. Each matrix is given in $n$ lines, and each line contains $d$ integers separated by spaces. The $j$-th number in the $i$-th line corresponds to the element in row $i$ and column $j$ of the matrix.

The last line contains $n$ integers, representing vector $W$.

Output Format

Write output to standard output.

Output $n$ lines in total, each containing $d$ integers separated by spaces, representing the computed result.

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

Hint

Subtasks

$70\%$ of the testdata satisfies: $n \le 100$ and $d \le 10$; all elements in the input matrices and vectors are integers, and their absolute values do not exceed $30$.

All testdata satisfies: $n \le 10^4$ and $d \le 20$; all elements in the input matrices and vectors are integers, and their absolute values do not exceed $1000$.

Hint

Please carefully estimate the value range after matrix multiplication, and use an appropriate data type to store the integers in the matrices.

Translated by ChatGPT 5