409409: GYM103503 C Plates

C. Platestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Following the unfortunate passing of ET Glob's grandma, our friendly extraterrestrial has inherited $$$n$$$ plates. Each plate is coloured with one of $$$k$$$ colours $$$1,2, \ldots, k$$$. He has also inherited his grandma's cupboard, which conveniently has a capacity of exactly $$$n$$$ plates.

ET Glob's little brother wanted to help with storing the plates, so he randomly and untidily piled some of them in the cupboard. When ET Glob realized that his brother had ruined his feng shui, he decided to store the rest of the plates himself. ET Glob knows the current configuration of the cupboard, which can represented as an array $$$a$$$ of $$$n$$$ integers. If $$$a_i$$$ is equal to $$$0$$$, then the $$$i$$$-th slot in the cupboard is empty. Otherwise, $$$a_i$$$ is equal to the colour of the plate in the $$$i$$$-th slot.

To restore his feng shui, ET Glob would like to store his plates in a tidy fashion. In his opinion, the final configuration of the plates is tidy if and only if the number of plates which have a different colour than the plate to their left is minimized.

Additionally, across all such final configurations, ET Glob would like to choose one which requires moving the least plates from the initial configuration. Let $$$a$$$ be the array denoting the initial configuration of the cupboard and $$$b$$$ be the array denoting the final configuration of the cupboard. The number of plates that have to be moved to get from $$$a$$$ to $$$b$$$ is equal to the number of positions $$$i$$$, $$$1 \le i \le n$$$, where $$$a_i \neq 0$$$ and $$$a_i \neq b_i$$$.

To help Glob, you will have to find the minimum amount of plates from the initial configuration which have to be moved, and one possible final configuration which requires moving the minimum amount of plates. If there are multiple possible final configurations, you may print any.

Input

• The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 20$$$) — the number of plates, and the number of colours, respectively.
• The second line of input contains $$$n$$$ integers $$$a_i$$$ ($$$0 \le a_i \le k$$$) — the initial configuration of the cupboard.
• The third line of input contains $$$k$$$ integers $$$p_i$$$, the number of plates of each colour ($$$0 \le p_i \le n$$$, $$$\Sigma p_i = n$$$).

It is guaranteed that for every colour $$$c \in [1,k]$$$, the number of plates of colour $$$c$$$ initially in the cupboard does not exceed $$$p_c$$$.Output

On the first line of output print one integer $$$x$$$ — the minimum number of positions $$$i$$$ ($$$1 \le i \le n$$$) in which $$$a_i \neq 0$$$ and $$$a_i \neq b_i$$$. On the second line of output print $$$n$$$ space separated integers — one possible optimal final configuration. If there are multiple possible final configurations, you may print any.

Scoring

• Subtask 1 (13 points): $$$1 \le n,k \le 10$$$;
• Subtask 2 (11 points): $$$1 \le k \le 5$$$;
• Subtask 3 (18 points): $$$1 \le k \le 10$$$;
• Subtask 4 (27 points): $$$1 \le n \le 100$$$;
• Subtask 5 (31 points): No further constraints.

ExamplesInput

8 3
0 1 0 1 3 2 0 0
3 2 3

Output

2
1 1 1 3 3 3 2 2 

Input

5 4
1 4 0 0 0
2 0 1 2

Output

1
1 1 3 4 4 

Note

In the first sample, $$$[1,1,1,3,3,3,2,2]$$$ is one possible final configuration which differs from the original configuration in exactly $$$2$$$ positions, namely $$$i_1=4$$$ and $$$i_2=6$$$. It can be proven that there are no final configurations which differ by less then $$$2$$$ elements.