Background

I originally planned to use this problem for an open contest, but it turned out to be similar to an existing one.

The statement is written by me and is different from the original problem.

This problem is roughly the same as P4050, with some small differences, and the Constraints have been changed.

Xiao A likes playing mahjong.

Problem Description

Xiao A found a strange set of mahjong tiles: there is only one suit with numbered tiles $1,2,\cdots,n$, and there are infinitely many copies of each tile.

Define a "pair" as two identical tiles (e.g. $2,2$, $7,7$), a "triplet" as three identical tiles (e.g. $1,1,1$, $4,4,4$), and a "sequence" as three tiles with consecutive numbers (e.g. $1,2,3$, $9,10,11$; note that $1$ and $n$ are not consecutive). A "sequence" and a "triplet" are collectively called a "meld".

If you can split your hand into several groups of "pairs" (they may be identical), or into several groups of "melds" (they may be identical) plus one group of "pair", then you can "win".

If adding some tile to a hand makes it possible to "win", then this hand is said to be "waiting for" that tile.

Now Xiao A randomly draws $k$ tiles. He wants to know which tiles he is "waiting for".

Input Format

The first line contains two positive integers $n,k$, representing the tile range and the number of tiles in Xiao A's hand.

The next line contains $k$ integers $a_1,a_2,\cdots,a_k$ describing Xiao A's hand, where each number represents one tile. They are not guaranteed to be in increasing order.

Output Format

The first line contains one positive integer $t$, the number of different tiles that Xiao A is "waiting for".

The next line contains $t$ positive integers, indicating which tiles Xiao A is "waiting for". Please output them in increasing order.

9 13
1 1 1 2 3 4 5 6 7 8 9 9 9

9
1 2 3 4 5 6 7 8 9

9 13
1 1 1 1 3 3 3 3 5 5 5 5 7

1
7

Hint

Sample Explanation

Explanation for Sample 1: this hand type is called Junsei Chuuren Poutou. Warning: may shorten your lifespan
One possible decomposition:

1 111|123|456|789|99
2 111|345|678|999|22
3 123|345|678|999|11
4 111|234|456|789|99
5 111|234|678|999|55
6 123|456|678|999|11
7 111|234|567|789|99
8 111|234|567|999|88
9 123|456|789|999|11

Explanation for Sample 2: obviously, this set is missing one tile $7$, and then it can be split into $1,1;1,1;3,3;3,3;5,5;5,5;7,7$, i.e. a total of $7$ groups of "pairs", and thus it wins.

Constraints

This problem uses bundled testdata.

• $\text{Subtask\;1(5\;pts)}$：$k=1$。
• $\text{Subtask\;2(5\;pts)}$：$n=1$。
• $\text{Subtask\;3(10\;pts)}$：$n=9$。
• $\text{Subtask\;4(15\;pts)}$：$k\le 100$。
• $\text{Subtask\;5(15\;pts)}$：$n\le 100$。
• $\text{Subtask\;6(50\;pts)}$：No special restrictions.

For all testdata, $1\le n\le 5\times10^3$, $1\le k\le 10^5$, $1\le a_i\le n$, and $k\equiv 1\pmod 6$.

Translated by ChatGPT 5