P16444 [XJTUPC 2026] Used to be

> "Who am I...?" This is a story about memory. One of the protagonists is a 01 string of length $m$. The first layer of the story is change. The story travels through $n-1$ nodes. Each time it passes a node, the protagonist is subtly affected: it may stay unchanged, or it may flip at exactly one position. These changes keep accumulating, and the final string may become completely different from the original. The second layer of the story is forgetting. Long ago, the script recorded the protagonist's initial state, as well as the state after passing each node. However, as time went by, the handwriting at some positions on the pages gradually blurred and turned into unreadable `?`. The third layer of the story is searching. Another group of protagonists—you—found this dusty record. Even though you may not be able to determine the only truth, you still hope to piece together one possible original appearance and recreate the story in your mind. > "Make her story complete." > > "I know... you will not disappoint me." **Formal statement** Given $n$ strings $S_1, S_2, \cdots, S_n$, each of length exactly $m$. Each string $S_i$ contains only characters $\texttt{0}$, $\texttt{1}$, and $\texttt{?}$. Determine whether there exists a way to replace each $\texttt{?}$ independently with $\texttt{0}$ or $\texttt{1}$ such that any two adjacent strings differ in at most one position. That is, after replacement, for any $i$ ($1\le i\le n-1$), the $i$-th string $S_i=a_1a_2\cdots a_m$ and the $(i+1)$-th string $S_{i+1}=b_1b_2\cdots b_m$ satisfy one of the following: - For all $j$ ($1\le j\le m$), $a_j=b_j$; - There exists an $x$ ($1\le x\le m$) such that $a_x\ne b_x$, and for all $j$ ($1\le j\le m$ and $x\ne j$), $a_j=b_j$. If it exists, output one such scheme. If there are multiple schemes, output any one.

**This problem contains multiple test cases**. The first line of the input contains a positive integer $T$ ($1\le T\le 10^5$), indicating the number of test cases. The following are $T$ test cases. The first line of each test case contains two positive integers $n$ and $m$ ($1 \le n\cdot m \le 10^6$), separated by a space, representing the number of strings and the length of each string. Then follow $n$ lines. The $i$-th line contains a string $S_i$ of length exactly $m$. It is guaranteed that $S_i$ contains only characters $\texttt{0}$, $\texttt{1}$, and $\texttt{?}$. It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^6$.

For each test case, if there is no valid scheme, output one line containing only the string $\tt{No}$. Otherwise, output $n+1$ lines, where: - The first line contains the string $\tt{Yes}$. - The next $n$ lines: the $i$-th of these lines contains a binary string of length $m$ containing only $\texttt{0}$ and $\texttt{1}$, representing the $i$-th string in the constructed scheme. If there are multiple valid schemes, output any one. The answer is case-insensitive. For example, $\tt{yEs}$, $\tt{Yes}$, $\tt{yes}$, and $\tt{YES}$ are all considered as $\tt{Yes}$.

Translated by ChatGPT 5