题目描述

茶叶国决定举办一次品茶大会。$n$ 名品茶师将品尝 $n$ 种茶叶。品茶师和茶叶的编号都是 $1\sim n$。

第 $i$ 种茶叶初始时被冲泡成 $a_i$ 毫升的茶水。 第 $j$ 位品茶师一次能喝 $b_j$ 毫升茶。

接下来是品茶的过程：

第一步：第 $i$ 名品茶师将品尝第 $i$ 种茶，他将会喝 $\min{(a_i,b_i)}$ 毫升的茶水，然后 $a_i$ 也会减少该数字。

第二步：第 $i$ 名品茶师将品尝第 $i-1$ 种茶，他将会喝 $\min{(a_{i-1},b_i)}$ 毫升的茶水，然后 $a_{i-1}$ 也会减少该数字。在此时，第 $1$ 位品茶师将不会喝茶。

第三步：第 $i$ 名品茶师将品尝第 $i-2$ 种茶，他将会喝 $\min{(a_{i-2},b_i)}$ 毫升的茶水，然后 $a_{i-2}$ 也会减少该数字。在此时，第 $1$ 位与第 $2$ 位品茶师将不会喝茶。

重复此步骤，直到第 $n$ 位品茶师不会喝茶。

以 $n=3,a=[10,20,15],b=[9,8,6]$ 为例：

第一步：第 $1$ 位品茶师喝了 $9$ 毫升，第 $2$ 位品茶师喝了 $8$ 毫升，第 $3$ 位品茶师喝了 $6$ 毫升。茶水还剩余 $[1,12,9]$，三位品茶师总计喝了 $[9,8,6]$。

第二步：第 $1$ 位品茶师喝了 $0$ 毫升，因为已经不能喝了。第 $2$ 位品茶师喝了 $1$ 毫升，第 $3$ 位品茶师喝了 $6$ 毫升。茶水还剩余 $[0,6,9]$，三位品茶师总计喝了 $[9,9,12]$。

第三步：第 $1$ 位品茶师喝了 $0$ 毫升。第 $2$ 位品茶师喝了 $0$ 毫升，第 $3$ 位品茶师喝了 $0$ 毫升。茶水还剩余 $[0,6,9]$，三位品茶师总计喝了 $[9,9,12]$。

你的任务是输出每位品茶师喝的总量。

输入格式

第一行输入一个正整数 $t$，表示测试用例组数。$(1\le t\le 10^4)$

每组测试用例包含三行：

第一行输入一个正整数 $n$，表示品茶师的数量与茶叶的种类。$(1\le n\le 2\times 10^5)$

第二行输入 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示第 $i$ 种茶叶的初始毫升数。$(1\le a_i\le 10^9)$

第三行输入 $n$ 个正整数 $b_1,b_2,\cdots,b_n$，表示第 $i$ 位品茶师一次能喝的量。$(1\le b_i\le 10^9)$

保证所有样例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每组测试用例，输出一行 $n$ 个正整数，表示每位品茶师喝的总量。

样例输入

4
3
10 20 15
9 8 6
1
5
7
4
13 8 5 4
3 4 2 1
3
1000000000 1000000000 1000000000
1 1 1000000000

样例输出

9 9 12 
5 
3 8 6 4 
1 2 2999999997