H. Afterimages
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Korosensei has decided to hold a dance for Class E. Unfortunately, no one showed up, so he is forced to dance with himself. He has created two lines of $$$n$$$ afterimages each (where $$$n$$$ is even), the $$$i$$$'th in the first line having height $$$a_i$$$ and the $$$i$$$'th in the second line having height $$$b_i$$$. Korosensei will then have all his afterimages sing $$$k$$$ songs and dance to them.

Every time a song starts, for all $$$i$$$ from $$$1 \dots n$$$, the $$$i$$$'th afterimage in the first line will dance with the $$$i$$$'th afterimage in the second line. Every time a song ends, all the afterimages in the first line will cyclically shift to the right by $$$1$$$, and the $$$n$$$'th afterimage will go to the front of the line ($$$a_2 = a_1, a_3 = a_2 \dots a_{n} = a_{n-1}, a_1 = a_n)$$$. At the same time, all the afterimages in the second line will cyclically shift to the left by $$$1$$$, and the first afterimage will go to the back of the line ($$$b_1 = b_2, b_2 = b_3 \dots b_{n-1} = b_{n}, b_n = b_1)$$$.

Even though he can travel at Mach 20, even Korosensei has trouble dancing with someone taller (or shorter) than him. The awkwardness of a dance between two afterimages with heights $$$x$$$ and $$$y$$$ is $$$abs(x - y)$$$ where $$$abs$$$ denotes the absolute value function. For each afterimage (in both lines), determine the maximum awkwardness of any dance they are a part of. As you, the participant, cannot write at Mach 20 (but can probably add at Mach 20?), you are only required to find the total sum of awkwardness for each afterimage.

Input

The first line of input contains a single integer $$$T$$$, denoting the number of test cases $$$(1 \leq T \leq 10^4)$$$.

Each test case consists of three lines.

The first line of each test case contains two integers $$$n$$$ $$$k$$$, denoting the lengths of the lines and the number of songs the afterimages sing $$$(2 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^{18})$$$. It is guaranteed that $$$n$$$ is even.

The second line of each test case contains $$$n$$$ spaced integers $$$a_{1 \dots n}$$$, the $$$i$$$'th being $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$. In case you are curious, the units to measure height here are football fields.

The third line of each test case contains $$$n$$$ spaced integers $$$b_{1 \dots n}$$$, the $$$i$$$'th being $$$b_i$$$ $$$(1 \leq b_i \leq 10^9)$$$. The units are still football fields (consistency is important).

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$4 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1 \dots 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1 - 5$$$ satisfy $$$n, k \leq 10$$$

Tests $$$6 - 10$$$ satisfy $$$n \leq 1000, T \leq 10$$$

The remaining tests do not satisfy any additional constraints.

Output

For each test case, output a single integer $$$S$$$ on a new line, denoting the sum of the maximum awkwardness of all dances of every afterimage.

Example
Input
6
6 2
1 2 3 4 5 6
7 8 9 10 11 12
6 3
1 3 5 7 9 11
12 8 3 4 2 1
4 3
3 3 6 6
1 2 3 4
4 10
1000000000 1 1 1000000000
1 1000000000 1000000000 1
2 10
1 2
1 2
6 2
4 6 4 8 4 6
3 7 2 3 7 2
Output
88
92
26
7999999992
0
39
Note

An explanation of the first sample is as follows:

After the first song starts playing, the heights in the first line are $$$[1, 2, 3, 4, 5, 6]$$$ and the heights in the second line are $$$[7, 8, 9, 10, 11, 12]$$$.

After the second song starts playing (and the first song stops playing), the heights are $$$[6, 1, 2, 3, 4, 5]$$$ and the heights in the second line are $$$[8, 9, 10, 11, 12, 7]$$$.

The sum of maximum awkwardness for dances of afterimages in the first line are $$$abs(1 - 9) + abs(2 - 10) + abs(3 - 11) + abs(4 - 12) + abs(5 - 11) + abs(6 - 12) = 44$$$

The sum of maximum awkwardness for dances of afterimages in the second line are $$$abs(7 - 1) + abs(8 - 2) + abs(9 - 1) + abs(10 - 2) + abs(11 - 3) + abs(12 - 4) = 44$$$

Then the total sum is $$$44 + 44 = 88$$$.

—

Problem idea: yash belani

Problem Preparation: 3366

Occurrences: Novice 8