Problem Description

给定长度为 $n$ 的排列 $a$，删除 $a_i$ 的代价是 $b_i$。

现在希望删除一些 $a_i$，使得删完后 $a$ 的 LIS（最长上升子序列）长度 $\le k$，最小化被删除元素的代价和。

对 $1 \le k \le n$ 分别求出答案。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le5$），表示测试数据组数。

对于每组数据，第一行一个整数 $n$（$1 \le n \le 500$）。

第二行 $n$ 个整数 $a_1 \sim a_n$（$1 \le a_i \le n$，$a_i$ 互不相同）。

第三行 $n$ 个整数 $b_1 \sim b_n$（$1 \le b_i \le 10^6$）。

Output

对于每组数据，输出一行 $n$ 个整数，第 $i$ 个整数表示 $k=i$ 时的最小代价和。

4
5
3 1 4 2 5 
6 7 10 2 4 
6
2 1 5 6 4 3 
8 7 9 7 5 10 
6
1 3 2 5 6 4 
2 10 2 10 8 2 
5
1 2 3 4 5
5 4 3 2 1

16 4 0 0 0 
22 7 0 0 0 0 
22 10 2 0 0 0 
10 6 3 1 0