## 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 0Output:

2 0 2 1

### Example 2

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

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 8Output:

25003 0 1 2 4 6 9 3 5 7 8