题目描述

给定一个 $1$ 到 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$，以及一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。

对于集合 $S\subseteq\{1,2,\ldots,N\}$，若它满足以下条件，则称 $S$ 为好集合：

• 对任意满足 $x<y$ 且 $x,y\in S$ 的整数 $x,y$，令 $z$ 为区间 $P_x,P_{x+1},\ldots,P_y$ 中最小值所在的唯一位置，即$$P_z=\min(P_x,P_{x+1},\ldots,P_y),$$ 则必须有 $z\in S$。

定义集合 $S$ 的代价为

对于每个 $K=1,2,\ldots,N$，求大小恰好为 $K$ 的好集合的最小代价。

共有 $T$ 组测试数据，请分别求解。

限制条件

• $1\le T\le 5000$
• $1\le N\le 5000$
• $1\le A_i\le 10^9$
• $P$ 是 $1$ 到 $N$ 的排列。
• 所有测试数据中 $N$ 的总和不超过 $5000$。
• 所有输入均为整数。

输入

T
case_1
case_2
...
case_T

每组测试数据的格式如下：

N
P_1 P_2 ... P_N
A_1 A_2 ... A_N

输出

对每组测试数据输出一行，共 $N$ 个整数。第 $K$ 个整数表示大小恰好为 $K$ 的好集合的最小代价。

样例输入 1

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

1 6 11 15
27 57 95 140 213 298
207907746 493431232 833061816 1192122901 1537883577 1896944662 2584619964 3365015576 4209049096 5062871597

对于第一组测试数据：

• $K=1$ 时，可以取 $S=\{1\}$；
• $K=2$ 时，可以取 $S=\{3,4\}$；
• $K=3$ 时，可以取 $S=\{1,2,3\}$；
• $K=4$ 时，只能取全部位置。