P1820 Mahjong - Enhanced-Enhanced Version

This problem is a strengthened version of [P4050](/problem/P4050) and [P6454](/problem/P6454). Xiao A likes playing Mahjong.

Xiao A found a strange set of Mahjong tiles: it only has number tiles $1,2,\cdots,n$, and there are infinitely many copies of each tile. A "pair" is two identical tiles (e.g., $2,2$, $7,7$). A "triplet" is three identical tiles (e.g., $1,1,1$, $4,4,4$). A "sequence" is three tiles with consecutive ranks (e.g., $1,2,3$, $9,10,11$; note that $1$ and $n$ are not adjacent). "Sequence" and "triplet" are collectively called "melds." If you can divide your hand into several "melds" (duplicates allowed) plus one "pair," then you can "complete the hand" (i.e., win). If adding a certain tile to a hand allows it to "complete the hand," then the hand is said to be "waiting for" that tile. Now Xiao A has randomly drawn $k$ tiles. He wants to know which tiles he is "waiting for."

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$ giving Xiao A's hand. Each number represents one tile in Xiao A's hand.

Output several positive integers on the first line, indicating which tiles Xiao A is "waiting for." Please output them in ascending order. If Xiao A is not "waiting for" any tile, output `QAQ`.

- Sample 1 explanation: two cases, `11/234` and `123/44`. - Sample 2 explanation: this shape is the "pure Nine Gates" (纯正九莲宝灯), so it "waits for" every number tile. Constraints - This problem uses bundled testdata. - Subtask 1 (10 pts): $1\leq k\leq 16$. - Subtask 2 (10 pts): $1\leq k\leq 400$. - Subtask 3 (30 pts): $1\leq k\leq 10^3$. - Subtask 4 (30 pts): $1\leq k\leq 3\times10^4$. - Subtask 5 (20 pts): no special constraints. For all testdata, $1\leq a_i\leq n\leq k\leq 2\times10^5$. Translated by ChatGPT 5