题目内容

在模型量化中，常需要把高精度浮点数转换为低位整数。对于实数 $r$ 与缩放因子 $s$，线性量化定义为 $q=\operatorname{round}(r/s)$，反量化则恢复为 $r=sq$。在 $n$ 比特量化下，缩放因子通常取 $s=\frac{\max(|r_{\min}|,|r_{\max}|)}{2^{n-1}-1}$。矩阵可以按行或按列分别量化，并为每一行或每一列保存一个缩放因子。

为了进一步避免缩放因子参与浮点运算，可以把缩放因子 $s$ 写成两个整数 $a,b$ 的比值：$s=\frac{a}{2^b}$。这样，两个缩放因子相乘时可以表示为

本题要求在这种全整数缩放因子表示下完成矩阵乘法。给定已经按行完成量化的矩阵 $A$，以及尚未量化的浮点矩阵 $B$。矩阵 $A$ 的大小为 $m\times k$，矩阵 $B$ 的大小为 $k\times n$。需要计算矩阵乘积 $C=A\times B$，并以全整型量化形式输出 $C$ 的每个元素。

矩阵 $A$ 的每一行已经附加了缩放因子 $s_A=\frac{a_A}{2^{b_A}}$。矩阵 $B$ 需要按列进行 8 比特量化：对第 $j$ 列，先取该列所有元素绝对值的最大值，令该列缩放因子 $s_B=\frac{\max(|B_{1,j}|,\dots,|B_{k,j}|)}{127}$，然后按量化公式得到该列整数表示，并裁剪到 [-127,127]；同时将 $s_B$ 表示为 $\frac{a_B}{2^{b_B}}$ 的形式。

对于结果矩阵 $C$ 中第 $i$ 行第 $j$ 列的元素，其量化值为 $A$ 第 $i$ 行量化整数与 $B$ 第 $j$ 列量化整数的点积。其缩放因子为两个缩放因子的乘积：

因此该元素需要输出三个整数：点积结果、$a_Aa_B$、$b_A+b_B$。点积结果不需要限制在 [-127,127] 内，缩放因子也无需约分。

约束条件：

• 矩阵 $A$ 每行给出的已量化整数以及矩阵 $B$ 量化后的整数均在 -127 到 127 之间。
• 缩放因子中，$a$ 的取值范围为 0 到 127，$b$ 的取值范围为 0 到 30。
• 矩阵 $B$ 使用 8 比特量化，量化后的整数范围为 -127 到 127。

输入描述

第一行包含三个整数 m、k、n，依次表示矩阵 $A$ 的行数、矩阵 $A$ 的列数（也是矩阵 $B$ 的行数）、矩阵 $B$ 的列数。

接下来 m 行，每行包含 k+2 个整数。前 k 个整数是矩阵 $A$ 当前行已经量化的整数；最后两个整数依次为该行缩放因子的 a 和 b。

再接下来 n 行，每行包含 k 个浮点数。这些行按矩阵 $B$ 的转置给出，其中第 i 行表示矩阵 $B$ 的第 i 列。

输出描述

输出共 m 行。每一行对应矩阵 $C$ 的一行，包含 $n$ 个结果元素。每个结果元素由三个整数依次组成：量化值、缩放因子的 a、缩放因子的 b。同一行内所有整数之间用空格分隔。

样例1

输入

2 3 2
1 2 3 1 0
10 -5 4 3 2
127.0 0.0 -127.0
0.0 127.0 64.0

输出

-254 64 6 446 64 6
762 192 8 -379 192 8

说明

矩阵 $A$ 第 1 行的缩放因子为 $1/2^0$，即 $a_A=1,b_A=0$；第 2 行的缩放因子为 $3/2^2$，即 $a_A=3,b_A=2$。

矩阵 $B$ 两列的最大绝对值均为 127，因此 $s_B=127/127=1$。将 $1$ 表示为 $a_B/2^{b_B}$ 时，四舍五入得到 $a_B=64,b_B=6$。

计算点积如下：

• 第 1 行第 1 列：$1\times127+2\times0+3\times(-127)=-254$。
• 第 1 行第 2 列：$1\times0+2\times127+3\times64=446$。
• 第 2 行第 1 列：$10\times127+(-5)\times0+4\times(-127)=762$。
• 第 2 行第 2 列：$10\times0+(-5)\times127+4\times64=-379$。

结果缩放因子：

• 第 1 行：$a_A a_B=1\times64=64$，$b_A+b_B=0+6=6$。
• 第 2 行：$a_A a_B=3\times64=192$，$b_A+b_B=2+6=8$。

因此输出如样例输出所示。

样例2

输入

1 1 1
5 1 0
0.0

输出

0 0 0

说明

矩阵 $B$ 唯一列的元素为 $[0.0]$，最大绝对值为 0，因此 $s_B=0/127=0$，量化后整数仍为 0，缩放因子表示为 $0/2^0$，即 $a_B=0,b_B=0$。

矩阵 $A$ 的唯一量化整数为 5，缩放因子为 $1/2^0$。点积为 $5\times0=0$。结果缩放因子为 $a_A a_B=1\times0=0$，$b_A+b_B=0+0=0$。

因此输出 0 0 0。

样例3

输入

1 2 1
5 -3 2 3
1.0 -2.0

输出

701 130 15

说明

矩阵 $B$ 唯一列的元素为 $[1.0,-2.0]$，最大绝对值为 2，所以 $s_B=2/127$。

量化时：

• $1.0/(2/127)=63.5$，四舍五入为 64；
• $-2.0/(2/127)=-127$，四舍五入为 -127。

缩放因子 $2/127$ 按照 $a_B/2^{b_B}$ 表示并四舍五入，得到 $a_B=65,b_B=12$。

矩阵 $A$ 的量化整数为 $[5,-3]$，缩放因子为 $2/2^3$。点积为 $5\times64+(-3)\times(-127)=701$。结果缩放因子为 $a_A a_B=2\times65=130$，$b_A+b_B=3+12=15$。

因此输出 701 130 15。