AT_ndpc2026_f.Set

You are given a permutation $P = (P_1, P_2, \dots, P_N)$ of $(1, 2, \dots, N)$ and an integer array $A_1, A_2, \dots, A_N$ of length $N$.

A subset $S$ of the set $\lbrace 1,2,\dots,N \rbrace$ is called a good set if it satisfies the following condition:

• For every pair of integers $(x, y)$ such that $x < y$ and $x, y \in S$, the following holds:
  • Let $z$ be the integer such that $P_z = \min(P_x, P_{x+1}, \dots, P_y)$. (Such a $z$ is uniquely determined.) Then, it must hold that $z \in S$.

The cost of a good set $S$ is defined as $\displaystyle \sum_{i \in S} A_i$.

For each $K = 1, 2, \dots, N$, find the minimum possible cost among all good sets of size $K$.

You are given $T$ test cases. Solve each of them.

给你一个 $(1, 2, \dots, N)$ 的排列 $P = (P_1, P_2, \dots, P_N)$ 和一个长度为 $N$ 的整数数组 $A_1, A_2, \dots, A_N$。

集合 $\lbrace 1,2,\dots,N \rbrace$ 的子集 $S$ 被称为好集合，当且仅当它满足以下条件：

• 对于任意满足 $x < y$ 且 $x, y \in S$ 的整数对 $(x, y)$，以下成立：
  • 设 $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$ 组测试数据。请分别求解每组数据。

The input is given from standard input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$
$P_1$ $P_2$ $\dots$ $P_N$
$A_1$ $A_2$ $\dots$ $A_N$

输入从标准输入中按以下格式给出：

$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$

Print $T$ lines. For the $i$-th line, output the answer for the $i$-th test case.
For each test case, output the answers for $K = 1,2,\dots,N$ in one line, separated by spaces.

输出 $T$ 行。对于第 $i$ 行，输出第 $i$ 个测试用例的答案。
对于每个测试用例，在一行内输出 $K = 1,2,\dots,N$ 对应的答案，各答案之间用空格分隔。

Sample 1 Explanation:
In the first test case:

• For $K=1$, $S=\lbrace 1 \rbrace$ is optimal,
• For $K=2$, $S=\lbrace 3,4 \rbrace$ is optimal,
• For $K=3$, $S=\lbrace 1,2,3 \rbrace$ is optimal,
• For $K=4$, $S=\lbrace 1,2,3,4 \rbrace$ is optimal.

Constraints

• $1 \leq T \leq 5000$
• $1 \leq N \leq 5000$
• $1 \leq A_i \leq 10^9$
• $(P_1, P_2, \dots, P_N)$ is a permutation of $(1,2,\dots,N)$
• The sum of $N$ over all test cases is at most $5000$
• All input values are integers

样例 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$；
• 所有输入值均为整数。