Shell Sort Cost Computation

In this problem, you are asked to simulate the process of Shell Sort and compute its total cost. Shell Sort can be seen as an optimization of insertion sort. In every round of insertion sort, when inserting the element (a_i) (at position (i)) into the already sorted part, suppose it is inserted at position (b_i) (both positions are 1-indexed), then the cost for that insertion is defined as (\lvert i - b_i \rvert + 1). The total cost is the sum of the costs incurred in all insertion rounds.

Shell Sort works by performing several rounds of insertion sort on subarrays defined by a gap (d). For a given gap (d), the array is divided into (d) groups as follows:

• Elements with indices: 1, 1 + d, 1 + 2d, ...
• Elements with indices: 2, 2 + d, 2 + 2d, ...
• (\vdots)
• Elements with indices: d, 2d, 3d, ...

In the final round, the gap is always set to 1, which is a standard insertion sort over the entire array. Although several rounds of insertion sort are performed, the accumulated cost might be much lower than performing a single run of insertion sort over the whole array.

Your task is to implement this Shell Sort process given an array and a sequence of gap values. For each insertion, you must add the cost (\lvert i - j \rvert + 1) (where (i) is the original 1-indexed position and (j) is the 1-indexed position where the element is finally inserted in that round). After processing all rounds, output the total cost as well as the sorted array.

inputFormat

The input consists of four parts:

1. The first line contains an integer (n) representing the number of elements in the array.
2. The second line contains (n) integers separated by spaces, representing the array elements.
3. The third line contains an integer (k) representing the number of gap rounds.
4. The fourth line contains (k) integers separated by spaces, representing the gap sequence. Note that the last gap must be 1.

outputFormat

The output consists of two lines:

1. The first line is a single integer representing the total cost of performing the Shell Sort. For every insertion operation, the cost is computed as (\lvert i - j \rvert + 1), where (i) is the original 1-indexed position of the element and (j) is its final 1-indexed position in that insertion round.
2. The second line contains the sorted array (in ascending order) with elements separated by a single space.

sample

5
5 4 3 2 1
2
3 1

14
1 2 3 4 5