2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
L. Lisa's Sequences

time limit per test

5 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputLisa loves playing with the sequences of integers. When she gets a new integer sequence $$$a_i$$$ of length $$$n$$$, she starts looking for all monotone subsequences. A monotone subsequence $$$[l, r]$$$ is defined by two indices $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$) such that $$$\forall i = l, l+1, \ldots, r-1: a_i \le a_{i+1}$$$ or $$$\forall i = l, l+1, \ldots, r-1: a_i \ge a_{i+1}$$$.

Lisa considers a sequence $$$a_i$$$ to be boring if there is a monotone subsequence $$$[l, r]$$$ that is as long as her boredom threshold $$$k$$$, that is when $$$r - l + 1 = k$$$.

Lucas has a sequence $$$b_i$$$ that he wants to present to Lisa, but the sequence might be boring for Lisa. So, he wants to change some elements of his sequence $$$b_i$$$, so that Lisa does not get bored playing with it. However, Lucas is lazy and wants to change as few elements of the sequence $$$b_i$$$ as possible. Your task is to help Lucas find the required changes.

Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le k \le n \le 10^6$$$) — the length of the sequence and Lisa's boredom threshold. The second line contains $$$n$$$ integers $$$b_i$$$ ($$$1 \le b_i \le 99\,999$$$) — the original sequence that Lucas has.

Output

On the first line output an integer $$$m$$$ — the minimal number of elements in $$$b_i$$$ that needs to be changed to make the sequence not boring for Lisa. On the second line output $$$n$$$ integers $$$a_i$$$ ($$$0 \le a_i \le 100\,000$$$), so that the sequence of integers $$$a_i$$$ is not boring for Lisa and is different from the original sequence $$$b_i$$$ in exactly $$$m$$$ positions.

Examples

Input

5 3 1 2 3 4 5

Output

2 1 0 3 0 5

Input

6 3 1 1 1 1 1 1

Output

3 1 100000 0 1 0 1

Input

6 4 1 1 4 4 1 1

Output

1 1 1 4 0 1 1

Input

6 4 4 4 4 2 2 2

Output

2 4 4 0 2 0 2

Input

6 4 4 4 4 3 4 4

Output

1 4 4 100000 3 4 4

Input

8 4 2 1 1 3 3 1 1 2

Output

2 2 1 1 3 0 1 0 2

Input

10 4 1 1 1 2 2 1 1 2 2 1

Output

2 1 1 100000 2 2 100000 1 2 2 1

Input

7 5 5 4 4 3 4 4 4

Output

0 5 4 4 3 4 4 4

Input

10 10 1 1 1 1 1 1 1 1 1 1

Output

1 1 1 1 1 1 1 1 1 0 1

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2024 16:27:16 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|