给定一个排列 P = (P_1, P_2, \dots, P_N)（是 (1, 2, \dots, N) 的一个排列），以及一个长度为 N 的整数数组 A_1, A_2, \dots, A_N。
一个集合 S（S 是 \lbrace 1,2,\dots,N \rbrace 的一个子集）被称为**好集合**，如果满足如下条件：
- 对于任意整数对 (x, y)，满足 x < y 且 x, y \in S，有：
- 设 z 使得 P_z = \min(P_x, P_{x+1}, \dots, P_y)。（这样的 z 唯一确定。）则必须有 z \in S。
一个好集合 S 的**代价**定义为 \displaystyle \sum_{i \in S} A_i。
对于每个 K = 1, 2, \dots, N，求所有大小为 K 的好集合的最小代价。
给定 T 组测试数据。请分别求解每一组。
输入由标准输入给出，格式如下：
> T
> \mathrm{case}_1
> \mathrm{case}_2
> \vdots
> \mathrm{case}_T
每组测试数据包含：
> N
> P_1 \ P_2 \ \dots \ P_N
> A_1 \ A_2 \ \dots \ A_N
输出共 T 行。第 i 行为第 i 组测试数据的答案。
对于每组测试数据，按顺序输出 K=1,2,\dots,N 时的答案，用空格分隔。
3 4 4 1 2 3 1 8 2 4 6 5 3 2 4 6 1 73 38 30 85 27 45 10 4 10 3 7 2 6 8 9 5 1 853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085
1 6 11 15 27 57 95 140 213 298 207907746 493431232 833061816 1192122901 1537883577 1896944662 2584619964 3365015576 4209049096 5062871597
样例解释 1
对于第一组测试数据：
- 当 K=1 时，最优选 S=\lbrace 1 \rbrace；
- 当 K=2 时，最优选 S=\lbrace 3,4 \rbrace；
- 当 K=3 时，最优选 S=\lbrace 1,2,3 \rbrace；
- 当 K=4 时，最优选 S=\lbrace 1,2,3,4 \rbrace。
数据范围
- 1 \leq T \leq 5000
- 1 \leq N \leq 5000
- 1 \leq A_i \leq 10^9
- (P_1, P_2, \dots, P_N) 是 (1,2,\dots,N) 的排列
- 所有测试数据中 N 的总和不超过 5000
- 所有输入均为整数
| 时间限制 | 2 秒 |
| 内存限制 | 512 MB |