问题描述

两年以前，小 A 在省选 day1 场上遇到了 《人员调度》 此题，并精准识别出是 LOJ 黄金矿工的弱化版，可惜小 A 由于懒惰，没有去做该题，只能遗憾离场。

......

小 A 现在是一家公司的老板，该公司共有 $n$ 个员工，以及 $n$ 个岗位。第 $i$ 个员工的能力值为 $a_i$，第 $i$ 个岗位的要求值为 $b_i$，第 $i$ 个员工就职第 $j$ 个岗位对公司产生的基础收益为 $a_i+b_j+(a_i\oplus b_j)$。其中 $\oplus$ 表示二进制下的异或运算。

同时小 A 发现特定的员工就职特定的岗位会产生额外的效益。小 A 会给出 $m$ 条信息，每条信息形如 $(x,y,w)$，即第 $x$ 个员工就职第 $y$ 个岗位会产生 $w$ 的额外收益。

小 A 给出一个参数 $K$，他想要知道，对于 $1\le k\le K$，若 恰好有 $k$ 个员工进行就职，产生的总收益（基础收益+额外收益）最大和为多少？

输入格式

第一行三个整数 $n,m,K$，分别表示员工数/岗位数以及信息的条数，所给的参数。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

第三行包含 $n$ 个整数，第 $i$ 个整数表示 $b_i$。

接下来 $m$ 行每行包含 $3$ 个整数 $x,y,w$，含义如题所示。

输出格式

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

输入样例

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

输出样例

14 28 42 56 58

数据范围

对于 $100\%$ 的数据，$1\leq n\le 10^5$，$0\le m\le 5\times 10^5$，$1\le K\le \min(300,n)$，$0\le a_i,b_i< 2^{12}$，$0\le w\le 10^5$。

保证不存在两条信息其 $x,y$ 完全相同。