Blood Pressure Game
题号：NC202120
时间限制：C/C++/Rust/Pascal 15秒，其他语言30秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

1Gugulu, a JBer, who was an ACMer one year ago, comes to Shanghai University taking part in the International Collegiate Programming Contest again. However, every time when Gugulu came to Shanghai University, he always got an Iron Medal and would consider this competition JB-like. To release his pain, Gugulu would go to the Shanghai Disneyland Park to have fun in taking the Roller Coaster. Gugulu loves the feeling with high-level blood pressure so much which makes him feel as a happy flappy bird who forgets all the Wrong Answers and Time Limit Exceededs etc.

We can regard the path of the Roller Coaster as a list of turning points with different heights which can be represented as an array of size , and Gugulu's final blood pressure after the game of the Roller Coaster is counted as the sum of all absolute values of the differences between the pairs of adjacent array numbers, i.e. .

Gugulu always got Iron Medals and is always getting Iron Medals, which makes him keep taking the Roller Coaster over and over again. However, as playing more games, his threshold on the value of blood pressure which can make himself happy is keeping increasing. As a result, the Roller Coaster of Shanghai Disneyland Park can hardly meet Gugulu's need anymore.

Therefore, Gugulu decides to add a set of m extra turning points in any order into this path, however, to consider about the reality on the distance of the original path, he can add at most one turning point into any original position between any two original elements in the array (and at most one in the head, at most one in the tail). Gugulu wants to make his blood pressure as high as possible, and he wants to know how much his blood can reach at most when he has added nextra Roller Coaster turning points into the path.

You, another JBer, are sure that Gugulu is clever enough to get the highest blood pressure as he can. It is very important for you to calculate the exact numbers to make an appointment with a proper cardiologist in advance to save Gugulu's life. You must solve this problem! Gugulu's blood pressure is becoming out of the control!

输入描述:

The first line of the input gives the number of test cases,  ().  test cases follow.
For each test case, the first line contains two integers,  () and  () 
Then, in second line, there are  integers  , denoting the  original Roller Coaster turning points. Then, in the third line, there are  integers  , denoting the  addition Roller Coaster turning points to be added. 
As it is an exciting Roller Coaster, it is guaranteed that all  integers in the two arrays are pairwise different.
There are at most  test cases whose  is more than .

输出描述:

For each test case, output three lines. The first line contains "Case #x:", where  is the test case number (starting from ). In the second line, there should be  integers which represent how much Gugulu's blood pressure could reach if he has added {1, 2, 3, …, m} extra Roller Coaster turning points into the path. In the third line, there should be  integers which represent the heights of the final Roller Coaster path if he has added all  extra  turning points. If there are several solutions, output any of them.
示例1

输入

复制 
6
2 3
5 11
10 3 1
4 1
1 2 3 4
5
4 2
1 2 3 4
5 6
4 5
1 2 3 4
5 6 7 8 9
4 4
10 50 3 6
1 9 23 5
4 2
10 50 3 6
9 23

输出

复制 
Case #1:
16 22 27 
10 5 1 11 3 
Case #2:
9 
1 5 2 3 4 
Case #3:
11 15 
1 6 2 5 3 4 
Case #4:
17 27 33 38 39 
5 1 9 2 8 3 7 4 6 
Case #5:
124 142 147 150 
5 10 1 50 3 23 6 9 
Case #6:
124 127 
10 50 3 23 6 9