时间限制： 1.0 秒

空间限制： 512 MB

题目描述

D 学校一年级有 3 个班级，A 班、B 班和 C 班。每个班级都有 $n$ 个学生，编号为 $1, 2, \cdots, n$。班级内学生的编号都是不同的，但不同班级间的编号会重复（即：每个班级都有各自的 $1$ 号学生）。

A 班、B 班的每个学生有一个称为人气值的属性，我们记 A 班 $i$ 号学生的人气值为 $a_i$，B 班 $j$ 号学生的人气值为 $b_j$。我们会按一定规则组织 A 班和 B 班的学生，在 C 班学生的帮助下进行合作。

组织的规则由正整数参数 $p$ 决定 $(1 \le p \le 10)$，具体而言：

• 对于 $p = 1$：当且仅当 $i + j = k$ 时，A 班 $i$ 号学生与 B 班 $j$ 号学⽣会在 C 班 $k$ 号学生的帮助下进行合作；
• 对于 $p = 2$：当且仅当 $i - j = k$ 时，A 班 $i$ 号学生与 B 班 $j$ 号学生会在 C 班 $k$ 号学生的帮助下进行合作；
• 按照下表依此类推 $\cdots$

$p$	条件
$1$	$i + j = k$
$2$	$i - j = k$
$3$	$i \times j = k$
$4$	$i / j = k$ （即 $i = j \times k$）
$5$	$\lfloor i / j \rfloor = k$（即 $i$ 整除 $j$ 忽略余数结果为 $k$）
$6$	$i~\mathrm{and}~j = k$（按位与运算）
$7$	$i~\mathrm{or}~j = k$（按位或运算）
$8$	$i~\mathrm{xor}~j = k$（按位异或运算）
$9$	$\min(i, j) = k$
$10$	$\max(i, j) = k$

现在，我们要统计 C 班每个学生在合作中的作用如何。对于 C 班的每个学生，我们需要计算他得到的合作值，$k$ 号学生的合作值记为 $c_k$。学生的合作值为他参与的每次项目的合作值之和，而某个项目的合作值为参与合作的 A 班、B 班 学生的人气值乘积。

例如，对于 $p = 1$，我们希望计算 C 班 4 号学生的合作值 $c_4$，根据组织规则，C 班 4 号学生参加了 3 次合作：

• A 班 1 号学生与 B 班 3 号学生的合作（因为 $1 + 3 = 4$）；
• A 班 2 号学生与 B 班 2 号学生的合作；
• A 班 3 号学生与 B 班 1 号学生的合作。

因此，$c_4 = a_1 \cdot b_3 + a_2 \cdot b_2 + a_3 \cdot b_1$ 。

形式化地说，输入正整数 $n$ 和 $p~(1 \le p \le 10)$，并输入两个长度为 $n$ 的数组 $a_1, a_2, \cdots, a_n$ 和 $b_1, b_2, \cdots, b_n$，求一个长度为 $n$ 的数组 $c_1, c_2, \cdots, c_n$，其中

$$c_k = \sum_{1 \le i, j \le n;~\mathrm{judge}(i, j, k) ~\mathrm{is}~\mathrm{true}} a_i \cdot b_j $$

其中

$$\mathrm{judge}(i, j, k) = \begin{cases} i + j = k, & p = 1 \\ i - j = k, & p = 2 \\ i \cdot j = k, & p = 3 \\ i / j = k, & p = 4 \\ \lfloor i / j \rfloor = k, & p = 5 \\ i~\mathrm{and}~j = k, & p = 6 \\ i~\mathrm{or}~j = k, & p = 7 \\ i~\mathrm{xor}~j = k, & p = 8 \\ \min(i, j) = k, & p = 9 \\ \max(i,j) = k, & p = 10 \end{cases} $$

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n$ 和 $p$。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$。

第三行输入 $n$ 个整数 $b_1, b_2, \cdots, b_n$。

相邻整数之间用一个空格隔开。

输出格式

输出到标准输出。

输出一行，包含 $n$ 个整数 $c_1, c_2, \cdots, c_n$。

相邻整数之间用一个空格隔开。

7 1
1 2 3 4 5 6 7
2 3 4 5 6 7 8

0 2 7 16 30 50 77

7 2
1 2 3 4 5 6 7
2 3 4 5 6 7 8

139 110 82 56 33 14 0

7 3
1 2 3 4 5 6 7
2 3 4 5 6 7 8

2 7 10 19 16 36 22

7 4
1 2 3 4 5 6 7
2 3 4 5 6 7 8

168 40 24 8 10 12 14

7 5
1 2 3 4 5 6 7
2 3 4 5 6 7 8

430 83 45 8 10 12 14

7 6
1 2 3 4 5 6 7
2 3 4 5 6 7 8

88 137 64 265 112 139 56

7 7
1 2 3 4 5 6 7
2 3 4 5 6 7 8

2 6 46 20 108 154 644

7 8
1 2 3 4 5 6 7
2 3 4 5 6 7 8

163 150 145 100 95 82 77

7 9
1 2 3 4 5 6 7
2 3 4 5 6 7 8

89 141 178 194 183 139 56

7 10
1 2 3 4 5 6 7
2 3 4 5 6 7 8

2 13 39 86 160 267 413

数据范围

本题共有 50 个测试点，每个测试点 2 分。

对于所有的测试点，输入的 $a_1, a_2, \cdots, a_n$ 和 $b_1, b_2, \cdots, b_n$ 均为不大于 $10$ 的正整数。

• 对于前 10 个测试点，$n = 15$，且 $p = 1, 2, \cdots, 10$ 各一个测试点；
• 对于接下来 10 个测试点，$n = 511$，且 $p = 1, 2, \cdots, 10$ 各一个测试点；
• 对于接下来 10 个测试点，$n = 8191$，且 $p = 1, 2, \cdots, 10$ 各一个测试点；
• 对于接下来 10 个测试点，$n = 65535$，且 $p = 1, 2, \cdots, 10$ 各一个测试点；
• 对于最后 10 个测试点，$n = 262143$，且 $p = 1, 2, \cdots, 10$ 各一个测试点。