P9202 "GMOI R2-T2" Cat-Eared Xiao (Enhanced Version).

**The difference between this problem and the [original problem](https://www.luogu.com.cn/problem/P9199) is the constraints and the output format. In this version, $n\le 10^6$ and the value range is $10^9$. You need to output a construction.** 

Little R is a cute cat-eared girl. She likes studying the $\operatorname{mex}\text{*}$ of sequences. Now she has a sequence $a$ of length $n$. She hates the integer $k$, so she wants to modify some elements of $a$ into any **natural numbers**, such that the $\operatorname{mex}$ of every **non-empty contiguous subarray** of $a$ is not equal to $k$. Please find the minimum number of elements that need to be modified, and output one valid plan. $\text{*}$ In this problem, the $\operatorname{mex}$ of a sequence is defined as the smallest **natural number** that does not appear in the sequence. For example: - $\operatorname{mex}\{1,2,3\}=0$, because $0$ is a natural number. - $\operatorname{mex}\{0,1,3\}=2$. - $\operatorname{mex}\{0,1,2\}=3$.

The first line contains two integers $n,k$, representing the length of the sequence and the number that Little R hates. The second line contains $n$ integers. The $i$-th integer is $a_i$, representing the $i$-th element of the sequence.

The first line contains one integer, representing the minimum number of modified elements. The second line contains $n$ integers, representing the modified sequence. You need to ensure that every number in the modified sequence is within $[0,10^9]\cap\Z$.

**Explanation of the sample** One possible plan is to change $\{1,0,1,3,0\}$ into $\{1,1,1,3,2\}$, modifying $2$ elements in total. It can be proven that no better plan exists. --- **Scoring** This problem uses a special judge (Special Judge) for evaluation. For each test point, if your minimum number of steps is correct, you can get $30\%$ of the score. Based on this, if your construction is also correct, you can get full marks. Note: Even if you cannot output a construction, you still need to output $n$ integers on the second line according to the output format. --- **This problem uses bundled tests, with no subtasks.** For $100\%$ of the testdata, $1\le n\le 10^6$, $0\le k,a_i\le 10^9$. The I/O volume of this problem is large, so it is recommended to use fast I/O methods. Translated by ChatGPT 5