Building Binomial Heaps

For any permutation π on set SET(Z) = {0, 1, 2, ..., Z−1}, Z > 0, let us denote by VAL(π) the sequence π(0), π(1), ..., π(Z−1).
Let
SEQP(Z) = π0, π1, π2, ..., πZ!−1
be a sequence of all permutations of the set SET(Z) and let SEQP(Z) be ordered in such way that VAL(πk) is lexicographically smaller than VAL(πk+1) for each k = 0, 1, ..., Z!−2.
For any permutation π of set SET(Z) we define the rank of permutation π to be the index of permutation π in the sequence SEQP(Z), supposing the indices of permutations in SEQP(Z) start from 0. We denote the rank of permutation π by symbol RANK(π). Because there are exactly Z! permutations of SET(Z) the rank of any permutation of this set is at least 0 and at most Z!−1.
For example, rank of permutation (0, 1, 2, 3, ..., Z−4, Z−3, Z−1, Z−2) is 1, rank of permutation (Z−1, Z−2, ..., 5, 4, 3, 2, 0, 1) is Z!−2, rank of permutation (1, 0, 2, 3, 4, ..., Z−3, Z−2, Z−1) is (Z−1)!.

Let π be a permutation of set SET(M) = {0, 1, ..., M−1} , M > 0. Let N be a positive integer divisible by M.
On the set SET(N) = {0, 1, ..., N−1} we define an extended permutation EP(π, N) as follows
EP(π,N)(i) = (i div M)×M + π(i mod M), i = 0, 1, ..., N−1.

Let BH be an unempty minimum (keeps track of its minimum elements) binomial heap consisting of binomial trees B(1), B(2), ..., B(k), k ≥ 1. Note that the index i of particular binomial tree B(i) in BH in this definition is not related to the order of B(i). For example, when k = 1 then the order of binomial tree B(1) might be any non-negative integer.
Let MAX(B(i)) be the maximum key value of all keys in the tree B(i), i = 1,2, ..., k.
Let ROOT(B(i)) be the value of the key in the root of tree B(i), i = 1,2, ..., k.
Define DIFF(BH) = Σ B(i) ∈ BH (MAX(B(i)) − ROOT(B(i))).
When there is an input sequence S containing N (N > 0) mutually distinct values then the binomial heap BH(S) is constructed in the following way:
At first, the heap is empty. Next, the first element of S is inserted into the heap. Then the second element of S is inserted into the heap, then the third element and so on until finally the last element of S is inserted into the heap. Each time standard binomial heap operation Insert is used.
Let us denote by BH(π, N) a binomial heap BH(VAL(EP(π, N))), where EP(π, N) is an extended permutation specified above.

The task
We are given an unempty set SETEP of extended permutations of the set SET(N) = {0, 1, ..., N−1}. We have to choose such permutation
πMAX ∈ SETEP which maximizes the value DIFF(BH(πMAX, N)).
Formally stated: Find πMAX ∈ SETEP such that
(∀π ∈ SETEP) (DIFF(BH(πMAX, N)) ≥   DIFF(BH(π, N))).

Input

The first line of input contains two positive integers N, M in this order separated by space. N specifies the size of the input sequence of which the binomial heap is built. M specifies set SET(M) = {0, 1, ..., M−1}. N is divisible by M.
It holds 0 < M ≤   100, M ≤   N ≤   2000000. The second line contains a permutation π1 of set SET(M) and the third line contains a permutation π2 of set SET(M). Permutation π1 resp. π2 is given as a sequence VAL(π1) resp. VAL(π2). All elements in the sequence are separated by space. The set SETEP is a set of all extended permutations EP(π, N) where rank of π is greater of equal to the rank of π1 and less or equal to the rank of π2. SETEP is always unempty.

Output

Output consists of two lines. The first line contains integer value DIFF(BH(πMAX,N)), where πMAX is the permutation specified above in the section "The task". The second line contains first M values of the sequence VAL(πMAX), the elements of the sequence are separated by space. When there are more possibilities to choose πMAX, output the permutation with lowest rank.

Example 1

Input: 
3 3
0 1 2
2 1 0
Output: 
2
0 2 1

Example 2

Input: 
25 5
0 2 4 1 3
0 4 2 1 3
Output: 
23
0 2 4 1 3

Example 3

Input: 
25000 10
0 1 2 4 6 5 8 9 3 7
0 1 2 4 7 3 9 6 5 8
Output: 
25003
0 1 2 4 6 9 3 5 7 8