题目描述

输入一个数组 $a$，包含有 $n$ 个元素 $a_1, a_2, \cdots, a_n$。对这个数组进行 $m$ 次变换，每次变换会将数组 $a$ 中的每个元素 $a_i$ 转换为 $a_i \cdot \text{bitCount}(a_i)$。其中 $\text{bitCount}(x)$ 表示数字 $x$ 的二进制表示中 $1$ 出现的次数，例如 $\text{bitCount}(3) = 2$，因为 $3$ 的二进制表示为 $11$，其中 $1$ 出现了两次。

请输出变换之后的数组内容。

输入格式

输入的第一行包含一个正整数 $n$，表示数组 $a$ 中的元素个数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，相邻整数之间使用一个空格分隔。

第三行包含一个整数 $m$，表示变换次数。

输出格式

输出一行，包含 $n$ 个整数，相邻整数之间使用一个空格分隔，表示变换之后得到的数组 $a$。

2
5 7
2

20 63

提示

样例说明

• $5 = (101)_2$，$7 = (111)_2$，第一次变化后 $a = [10, 21]$。
• $10 = (1010)_2$，$21 = (10101)_2$，第二次变换后 $a = [20, 63]$。

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq n \leq 10$；
• 对于 $60\%$ 的评测用例，$1 \leq n \leq 100$；
• 对于所有评测用例，$1 \leq n \leq 10^3$，$0 \leq m \leq 5$，$0 \leq a_i \leq 1000$。