题目内容

在模型部署中，需要将 $n$ 个整数激活值量化为低比特整数。给定量化比特宽度 $B$ 和截断阈值 $C$，按照以下三个步骤依次处理，前一步的结果作为后一步的输入。

1. 截断：

$z_i = \min(C, \max(-C, x_i))$

2. 量化范围：

$Q = 2^{B-1} - 1$

$M = \max(|z_1|, |z_2|, \ldots, |z_n|)$

若 $M = 0$，则所有量化结果均为 $q_i = 0$，无需执行第 3 步。

3. 量化。对每个 $i$，先计算：

$r_i = z_i \cdot Q / M$

其中，除法按实数计算。然后按照以下规则，将 $r_i$ 舍入为整数 $q_i$：

• 设 $a = |r_i|$。若 $a$ 的小数部分小于 $0.5$，则直接舍去小数部分；若小数部分大于或等于 $0.5$，则将其整数部分加 $1$。最后恢复 $r_i$ 的符号，即小数部分恰好为 $0.5$ 时，向远离 $0$ 的方向舍入。当 $r_i = 0$ 时，$q_i = 0$。
• 将 $q_i$ 限制在 $[-Q, Q]$ 范围内：若 $q_i > Q$，则令 $q_i = Q$；若 $q_i < -Q$，则令 $q_i = -Q$。

输入描述

第一行包含三个整数 $n$、$B$、$C$，相邻整数之间用空格分隔。

第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$，相邻整数之间用空格分隔。

约束

• $1 \le n \le 1000$
• $2 \le B \le 8$
• $1 \le C \le 10^6$
• $|x_i| \le 10^6$

输出描述

输出一行，包含 $n$ 个整数 $q_1, q_2, \ldots, q_n$。相邻两个整数之间恰好用一个空格分隔，行末没有多余空格。

样例1

输入

4 3 5
10 -2 0 4

输出

3 -1 0 2

说明

$B = 3$，$Q = 2^{2} - 1 = 3$。

截断后得到 $z_1 = 5$，$z_2 = -2$，$z_3 = 0$，$z_4 = 4$，其中 $x_1 = 10$ 被截断为 $5$。因此 $M = 5$。

$r_1 = 5 \cdot 3 / 5 = 3$，$q_1 = 3$。

$r_2 = -2 \cdot 3 / 5 = -1.2$，绝对值的小数部分为 $0.2$，舍去小数部分后得到 $q_2 = -1$。

$r_3 = 0$，$q_3 = 0$。

$r_4 = 4 \cdot 3 / 5 = 2.4$，绝对值的小数部分为 $0.4$，舍去小数部分后得到 $q_4 = 2$。

四个量化结果均在 $[-Q, Q]$ 范围内，无需进一步调整。

样例2

输入

3 2 10
1 -1 2

输出

1 -1 1

说明

$B = 2$，$Q = 2^{1} - 1 = 1$。三个激活值均在 $[-10, 10]$ 范围内，无需截断，因此 $M = 2$。

$r_1 = 1 \cdot 1 / 2 = 0.5$，小数部分恰好为 $0.5$，向远离 $0$ 的方向舍入，得到 $q_1 = 1$。

$r_2 = -1 \cdot 1 / 2 = -0.5$，同样向远离 $0$ 的方向舍入，得到 $q_2 = -1$。

$r_3 = 2 \cdot 1 / 2 = 1$，$q_3 = 1$。

三个量化结果均在 $[-Q, Q]$ 范围内，无需进一步调整。