题目背景

期末周的临近，波奇酱为了举办“期末周冰红茶品鉴会”买了一箱冰红茶...

题目描述

波奇酱买来了 $n$ 种冰红茶，同时也邀请了 $n$ 位同学一起参加冰红茶品鉴大会。

冰红茶从 $1$ 到 $n$ 编号，第 $i$ 种冰红茶每喝 $1$ 毫升可以获得 $v_i$ 点快乐值，初始有 $a_i$ 毫升。

同学们也从 $1$ 到 $n$ 编号，第 $i$ 位同学在每一轮品鉴中最多可以饮用 $b_i$ 毫升的冰红茶。

品鉴大会将持续进行 $n$ 轮。在第 $x$ 轮中，第 $y$ 位同学将尝试饮用编号为 $y+1-x$ 的冰红茶（即本轮该同学目标饮用的冰红茶编号为 $y+1-x$ ，若 $y+1-x \leq 0$ 本轮第 $y$ 位同学不会饮用任何冰红茶）。

具体规则如下：

• 如果该同学本轮的目标冰红茶还剩余容量 $> 0$，他会尽量饮用至多 $b_y$ 毫升（即：$\min(b_y, a_t)$，其中 $t = y+1-x$）。
• 实际饮用的毫升数会从对应的冰红茶中扣除。
• 每喝 $1$ 毫升，该同学获得对应冰红茶的 $v_t$ 点快乐值。
• 若冰红茶已被喝完（容量为 $0$），该轮该同学不会获得任何快乐值。

请你帮助波奇酱计算出 $n$ 轮品鉴大会结束后，每位同学所获得的总快乐值。

输入格式

第一行包含一个整数 $t (1 \leq t \leq 2 \times 10^5)$ ，表示有 $t$ 组测试数据。

对于每组测试数据，第一行包含一个整数 $n (1 \leq n \leq 2 \times 10^5)$ ，表示有 $n$ 种冰红茶，$n$ 位同学。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 种冰红茶的快乐值 $v_i (1 \leq v_i \leq 2 \times 10^5)$ 。

第三行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 种冰红茶的容量 $a_i(1 \leq a_i \leq 2 \times 10^5)$ 。

第四行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 位同学一轮中最多能喝 $b_i (1 \leq b_i \leq 2 \times 10^5)$ 毫升。

保证对于一个测试点的所有 $n$ 的总和不超过 $2 \times 10^5$ 。

输出格式

每组测试数据输出一行，包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 位同学在 $n$ 轮品鉴后的最终快乐值。

输入输出样例 #1

输入 #1

1
3
1 2 3
2 3 4
1 2 3

输出 #1

1 5 11