G. Treasure Hunt in Laurasia
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

In the vast Plains of Laurasia, a clever but greedy donkey named Doru loves collecting treasures. The village market contains $$$N$$$ unique items, each with a weight and a profit value (how valuable it is to Doru).

Doru carries a bag with limited capacity. For a bag of capacity $$$c$$$, he can pick items whose total weight does not exceed $$$c$$$. Each item can be picked at most once.

Being ambitious, Doru wants to know: for every bag capacity from $$$1$$$ to $$$K$$$, what is the maximum total profit he can collect?

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two space-separated integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^6$$$, $$$1 \le K \le 5000$$$) — the number of items in the market and the maximum bag capacity.

The second line of each test case contains $$$N$$$ space-separated integers $$$w_1, w_2, \dots, w_N$$$ ($$$1 \le w_i \le 5000$$$) — the weights of the items.

The third line of each test case contains $$$N$$$ space-separated integers $$$p_1, p_2, \dots, p_N$$$ ($$$1 \le p_i \le 10^9$$$) — the profits of the items.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^6$$$, and the sum of $$$K^2$$$ over all test cases does not exceed $$$5000^2$$$.

Output

For each test case, output $$$K$$$ space-separated integers in a single line.

The $$$i$$$-th integer should be the maximum total profit obtainable using a bag of capacity $$$i$$$.

If no item can be taken, the profit is $$$0$$$.

Example
Input
2
4 9
1 1 2 5
32 21 50 60
3 3
1 2 3
5 2 3
Output
32 53 82 103 103 103 113 142 163 
5 5 7
Note

In the first test case, if the capacity of the bag is $$$3$$$, it is optimal to pick the first and the third item.