## 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.

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.

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

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
```