DP + Sliding Window
A. Prologue to Christmas Present 2 (Easy)
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem is a simplified version of ABC334F: Christmas Presents 2. Here, all the children are guaranteed to be on the one dimensional number line, i.e, $$$Y_i = 0$$$ and $$$S_y = 0$$$ for all points. With these restrictions, the answer would also be an integer instead of a real number.

There are $$$n$$$ children present on a number line, where the $$$i^{th}$$$ children is present at point $$$a_i$$$. Santa starts his journey at point $$$S_x$$$. He can only carry at max $$$K$$$ presents at any point of time.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, print the minimum distance travelled by Santa to deliver one present each to the first $$$i$$$ children AND return back to his starting position.

Constraints

  • $$$1 \leq T \leq 2$$$
  • $$$1 \leq N \leq 10^2$$$
  • $$$-10^9 \leq S_x, A_i \leq 10^9$$$
  • $$$1 \leq K \leq N$$$
  • All the $$$(N + 1)$$$ points are distinct.
  • Sum of $$$N$$$ over all testcases does not exceed $$$2*10^2$$$
Input
  • The first line contains a single integer, $$$T$$$, the number of testcases
  • The first line of each testcase contains 2 integers, $$$N$$$ and $$$K$$$. Here, $$$N$$$ is the total number of children and $$$K$$$ is the maximum number of presents allowed in the bag.
  • The second line of each testcase contains $$$S_x$$$, the starting position for Santa.
  • The second line of each testcase contains $$$N$$$ integers. $$$a_i$$$ represents the location of the $$$i^{th}$$$ child.
Output

For each testcase, print $$$n$$$ integers denoting the minimum cost to give presents to the first $$$i$$$ children and return back to the starting position.

Examples
Input
1
3 2
0
1 2 3
Output
2 4 8
Input
1
7 3
3
0 -3 -7 1 -5 2 8
Output
6 12 20 24 36 36 46

B. Prologue to Christmas Present 2 (Medium)
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem is a simplified version of ABC334F: Christmas Presents 2. Here, all the children are guaranteed to be on the one dimensional number line, i.e, $$$Y_i = 0$$$ and $$$S_y = 0$$$ for all points. With these restrictions, the answer would also be an integer instead of a real number.

There are $$$n$$$ children present on a number line, where the $$$i^{th}$$$ children is present at point $$$a_i$$$. Santa starts his journey at point $$$S_x$$$. He can only carry at max $$$K$$$ presents at any point of time.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, print the minimum distance travelled by Santa to deliver one present each to the first $$$i$$$ children AND return back to his starting position.

Constraints

  • $$$1 \leq T \leq 10^2$$$
  • $$$1 \leq N \leq 10^3$$$
  • $$$-10^9 \leq S_x, A_i \leq 10^9$$$
  • $$$1 \leq K \leq N$$$
  • All the $$$(N + 1)$$$ points are distinct.
  • Sum of $$$N$$$ over all testcases does not exceed $$$2*10^3$$$
Input
  • The first line contains a single integer, $$$T$$$, the number of testcases
  • The first line of each testcase contains 2 integers, $$$N$$$ and $$$K$$$. Here, $$$N$$$ is the total number of children and $$$K$$$ is the maximum number of presents allowed in the bag.
  • The second line of each testcase contains $$$S_x$$$, the starting position for Santa.
  • The second line of each testcase contains $$$N$$$ integers. $$$a_i$$$ represents the location of the $$$i^{th}$$$ child.
Output

For each testcase, print $$$n$$$ integers denoting the minimum cost to give presents to the first $$$i$$$ children and return back to the starting position.

Examples
Input
1
3 2
0
1 2 3
Output
2 4 8
Input
1
7 3
3
0 -3 -7 1 -5 2 8
Output
6 12 20 24 36 36 46

C. Prologue to Christmas Present 2 (Hard)
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem is a simplified version of ABC334F: Christmas Presents 2. Here, all the children are guaranteed to be on the one dimensional number line, i.e, $$$Y_i = 0$$$ and $$$S_y = 0$$$ for all points. With these restrictions, the answer would also be an integer instead of a real number.

There are $$$n$$$ children present on a number line, where the $$$i^{th}$$$ children is present at point $$$a_i$$$. Santa starts his journey at point $$$S_x$$$. He can only carry at max $$$K$$$ presents at any point of time.

For each $$$i$$$ from $$$1$$$ to $$$n$$$, print the minimum distance travelled by Santa to deliver one present each to the first $$$i$$$ children AND return back to his starting position.

Constraints

  • $$$1 \leq T \leq 10^4$$$
  • $$$1 \leq N \leq 10^5$$$
  • $$$-10^9 \leq S_x, A_i \leq 10^9$$$
  • $$$1 \leq K \leq N$$$
  • All the $$$(N + 1)$$$ points are distinct.
  • Sum of $$$N$$$ over all testcases does not exceed $$$2*10^5$$$
Input
  • The first line contains a single integer, $$$T$$$, the number of testcases
  • The first line of each testcase contains 2 integers, $$$N$$$ and $$$K$$$. Here, $$$N$$$ is the total number of children and $$$K$$$ is the maximum number of presents allowed in the bag.
  • The second line of each testcase contains $$$S_x$$$, the starting position for Santa.
  • The second line of each testcase contains $$$N$$$ integers. $$$a_i$$$ represents the location of the $$$i^{th}$$$ child.
Output

For each testcase, print $$$n$$$ integers denoting the minimum cost to give presents to the first $$$i$$$ children and return back to the starting position.

Examples
Input
1
3 2
0
1 2 3
Output
2 4 8
Input
1
7 3
3
0 -3 -7 1 -5 2 8
Output
6 12 20 24 36 36 46