D. Gooseberry
time limit per test
5 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp really loves to eat gooseberry. The gooseberry season consists of $$$n$$$ days, and during each of these days, Monocarp can go to the market and buy a batch of gooseberries.

If Monocarp goes to the market during the day $$$i$$$, the batch he buys lasts for $$$a_i$$$ days (from day $$$i$$$ until the day $$$(i+a_i-1)$$$, inclusive), and during each of these days, he gets $$$b_i$$$ units of happiness from eating it. Monocarp won't go to the market until he has finished the current batch. In other words, the first day Monocarp can choose to go to the market again after buying the $$$i$$$-th batch is the day $$$(i + a_i)$$$. Monocarp does not have to go to the market every time he is out of gooseberry. However, he won't get any units of happiness during the days he does not have any gooseberries to eat.

Monocarp estimates the amount of joy he gets from the whole season as follows:

  • first, for every segment of consecutive $$$m$$$ days, he calculates $$$S_i$$$ — the total happiness he gets during those days. In other words, for every $$$i \in [1, n-m+1]$$$, $$$S_i = h_i + h_{i+1} + \dots + h_{i+m-1}$$$, where $$$h_i$$$ is the happiness Monocarp gets during the $$$i$$$-th day;
  • then, he takes the minimum value among $$$S_1, S_2, \dots, S_{n-m+1}$$$, which is the amount of joy he gets from the whole season.

Help Monocarp find a plan of purchasing gooseberry in such a way that the joy he gets from the whole season is the maximum possible!

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le n$$$) — the number of days of the gooseberry season, and the length of each segment of days used in the calculations of joy, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$m \le a_i \le n$$$) — the number of days that the $$$i$$$-th batch of gooseberries lasts for. Note the unusual constraint.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the happiness Monocarp gets from this batch during each day.

Additional constraint on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print two integers $$$p$$$ and $$$k$$$ in the first line, where $$$p$$$ is the maximum possible amount of joy Monocarp can get from the gooseberry season, and $$$k$$$ is the number of times Monocarp visits the market to buy a batch.

In the second line, print $$$k$$$ distinct integers from $$$1$$$ to $$$n$$$ — the days when Monocarp visits the market in increasing order.

If there are multiple optimal answers, output any of them.

Example
Input
10
2 1
1 1
4 7
3 2
2 2 3
2 5 3
4 3
3 4 3 3
9 8 13 4
4 2
4 2 2 3
1 10 7 3
5 4
4 4 5 5 5
7 2 1 7 3
7 3
3 4 4 6 5 3 3
9 3 3 2 4 8 9
8 3
4 3 4 6 3 6 6 4
7 9 2 7 2 4 8 9
9 4
4 9 4 8 9 6 8 8 5
9 4 7 4 2 5 8 7 6
10 3
3 5 6 7 3 4 5 8 10 4
1 5 4 2 1 3 1 2 4 3
12 2
4 2 2 3 2 4 4 4 4 3 3 3
7 1 9 8 6 4 5 9 8 9 1 2
Output
4 2
1 2 
5 1
2
22 2
1 4
10 1
2
24 2
1 5 
8 2
1 6 
8 2
2 7 
16 2
1 7 
4 2
3 10
6 4
1 5 8 12
Note

In the first test case, Monocarp can purchase gooseberry batches on both days. He is allowed to do that because the first batch lasts $$$1$$$ day, so he can buy the second batch on day $$$2$$$. Then $$$h = [4, 7]$$$. Since $$$m = 1$$$, $$$S_i$$$ is equal to $$$h_i$$$. Thus, the minimum in $$$S$$$ is $$$4$$$.

In the second test case, Monocarp can purchase a gooseberry batch on day $$$2$$$. $$$h = [0, 5, 5]$$$. Then $$$S_1 = h_1 + h_2 = 5$$$, $$$S_2 = h_2 + h_3 = 10$$$.

In the third test case, Monocarp can purchase gooseberry batches on days $$$1$$$ and $$$4$$$. $$$h = [9, 9, 9, 4]$$$. $$$S_1 = 27$$$, $$$S_2 = 22$$$. Note that Monocarp can't purchase batches on days $$$1$$$ and $$$3$$$, for example. The batch from day $$$1$$$ lasts until day $$$3$$$, so day $$$4$$$ is the earliest he can purchase another batch.