L 先生拥有一家拥有 $n$ 名员工和 $n$ 个职位的公司。第 $i$ 名员工的能力值为 $a_i$，第 $j$ 个职位的需求值为 $b_j$。当第 $i$ 名员工被分配到第 $j$ 个职位时，产生的基础利润为：$a_i + b_j + (a_i \oplus b_j)$，其中 $\oplus$ 表示二进制下的异或运算。

此外，L 先生发现特定的员工-职位分配会产生额外利润。他提供了 $m$ 条信息，每条信息的形式为 $(x, y, w)$，表示将第 $x$ 名员工分配到第 $y$ 个职位会产生 $w$ 的额外利润。

给定参数 $K$，L 先生希望确定对于每个 $1 \le k \le K$，当恰好有 $k$ 名员工被分配到职位时，所能获得的最大总利润（基础利润 + 额外利润）。

注意：两名员工不能被分配到同一个职位。

输入格式

第一行包含三个整数 $n, m, K$ ($1 \le n \le 10^5, 0 \le m \le 5 \times 10^5, 1 \le K \le \min(300, n)$)，分别表示员工/职位的数量、信息条数以及给定的参数。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$ ($0 \le a_i < 2^{12}$)。

第三行包含 $n$ 个整数，其中第 $i$ 个整数表示 $b_i$ ($0 \le b_i < 2^{12}$)。

接下来的 $m$ 行，每行包含三个整数 $x, y$ 和 $w$ ($1 \le x \le n, 1 \le y \le n, 0 \le w \le 10^5$)。

保证没有两条信息具有相同的 $x$ 和 $y$ 值。

输出格式

输出一行，包含 $K$ 个整数，其中第 $i$ 个整数表示 $k = i$ 时的答案。

样例

样例输入 1

5 0 5
1 2 3 4 5
5 4 3 2 1

样例输出 1

14 28 42 56 58