Assume you are given an array of integers, array of integers from the interval and an integer .

We are doing a Warshall-Turing-Fourier transformation (this doesn't really exist) on array in the following way:

```
sum = 0
for i = 1 to N
index = min{ ID[i], ID[i+1] }
sum = sum + A[index]
rotate array A to the right by R places
change the signs of all elements in A
for i = 1 to N
index = max{ ID[i], ID[i+1] }
index = index + 1
sum = sum + A[index]
rotate array A to the right by R places
```

You are given the array and constant , but you are not familiar with the array . What is the
largest possible value of variable `sum`

after execution of the above algorithm?

#### Input

The first line of input contains the integers and from the task.

The second line of input contains the elements of array , respectively from to . These are integers from the interval .

#### Output

The first line of output must contain the maximal value of `sum`

.

The second line of output must contain the array of integers from the interval for which the algorithm outputs the maximal sum. If there are multiple such arrays, output any.

If only the first line is correct (regardless of whether the second is printed), you will get of points for the corresponding test case.

#### Scoring

In test cases worth of total points, it will hold .

In test cases worth of total points, it will hold .

#### Sample Input 1

```
5 3
1 -1 1 -1 1
```

#### Sample Output 1

```
10
1 1 1 2 2 3
```

#### Sample Input 2

```
6 5
2 5 4 1 3 5
```

#### Sample Output 2

```
16
3 2 1 1 5 4 1
```

## Comments

The judge gives 100% AC for only printing out the first number, which according to the problem statement should only give me 50%.

Also when I printed out rest of the answer (which I was supposed to do for 100% AC), it gave me WA.

This comment is hidden due to too much negative feedback. Click here to view it.