Background

Xu Fu was a Taoist from the Qi region during the Qin Dynasty.

Ordered by the First Emperor of Qin, Xu Fu led three thousand boys and girls on a quest to find the legendary "Elixir of Penglai." However, he never returned.

Where did Xu Fu end up? Did he find the Elixir of Penglai? These questions are no longer relevant.

Problem Description

The passage of time can be abstracted as the time taken to sort a sequence of numbers. Different sorting strategies take different amounts of time. Here, we introduce a milestone sorting algorithm in human exploration: Shell Sort.

Shell Sort can be seen as an optimization of insertion sort. To study the efficiency of Shell Sort, we want you to implement a simple process of Shell Sort. Before that, we will standardize the specific process of insertion sort and evaluate the "cost" of an insertion sort process.

Insertion Sort

For an array \( a = [a_1, a_2, \cdots, a_n] \) of length \( n \), the idea of insertion sort is to enumerate each element from the beginning and insert it into the correct position:

As shown in the figure, this is a typical process of insertion sort. In the \( i \)-th round, we insert the element at index \( i \) before the first element in the sorted part that is greater than \( a_i \). If \( a_i \) is finally inserted into position \( b_i \), we call the cost of this round \( |a_i - b_i| + 1 \), and the total cost of the insertion sort process is the sum of the costs of each round.

Shell Sort

To reduce the cost of insertion sort, we introduce Shell Sort. Shell Sort divides the sorting process into several rounds, each round grouping elements by a certain interval and sorting each group separately. In the final round, Shell Sort performs a final insertion sort on the entire array.

The specific grouping method is to select an integer \( d \) and divide into the following groups:

• Elements with indices \( 1, 1+d, 1+2d, \cdots \);
• Elements with indices \( 2, 2+d, 2+2d, \cdots \);
• Elements with indices \( 3, 3+d, 3+2d, \cdots \);
• ...
• Elements with indices \( d, 2d, 3d, \cdots \).

Below is the process of one round of Shell Sort. We select \( d = 3 \).

Shell Sort selects \( d \) in each round, and in the last round, it selects \( d = 1 \), performing such sorting in each round, eventually obtaining a sorted array.

Although it seems that many rounds of insertion sort are performed, the sum of the costs of each round of insertion sort may be much less than the cost of a single insertion sort on the entire array (this is not obvious in the above example, see the examples in Sample 2 and 3).

In fact, Shell Sort is the first sorting algorithm discovered by humans with a worst-case complexity lower than \( \Theta(n^2) \). For example, when \( d = 2^k - 1 \), \( k = \lfloor \log_2 n \rfloor, \lfloor \log_2 n \rfloor - 1, \lfloor \log_2 n \rfloor - 2, \cdots, 1 \), the worst-case time complexity of the entire process is \( \mathcal \Theta(n^{3/2}) \).

Input Format

The first line contains two integers \( n \) and \( m \), representing the length of the array to be sorted and the number of rounds of Shell Sort, respectively.

The second line contains \( n \) integers \( a_1, a_2, \cdots, a_n \), describing the elements of the array.

The third line contains \( m \) integers \( d_1, d_2, \cdots, d_m \), describing the values of \( d \) selected in each round. It is guaranteed that \( d_m = 1 \).

Output Format

The first line should output an integer \( \mathrm{cost} \), representing the sum of the costs of insertion sort during the entire Shell Sort process.

The second line should output \( n \) integers, representing the sorted result of array \( a \).

Sample Input and Output

Sample Input #1

10 1
3 2 6 4 1 1 3 8 7 3
1

Sample Output #1

27
1 1 2 3 3 3 4 6 7 8

Sample Input #2

15 1
15 14 13 12 10 11 9 8 7 4 5 6 3 2 1
1

Sample Output #2

116
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sample Input #3

15 3
15 14 13 12 10 11 9 8 7 4 5 6 3 2 1
9 3 1

Sample Output #3

68
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Notes

Data Range and Constraints

For all data, it is guaranteed that \( 1 \le n \le 10^5 \), \( 1 \le m \le 100 \), \( \mathrm{cost} \le 5 \times 10^7 \), \( 1 \le a_i \le 10^9 \), \( 1 \le d_i \le n \), and \( d_m = 1 \).

见题面 Input 部分

见题面 Output 部分