410189: GYM103969 I Ice Cream Orders
Description
Rectangletown is preparing for the biggest heat wave of the year, in the best way possible: free ice cream for everyone!
Rectangletown can be represented as an $$$n$$$ by $$$m$$$ grid of houses, each of which is allowed to order some amount of ice cream. To simplify the ordering, production, and delivery process, the following rules were put in place:
- A house in row $$$i$$$ can pick $$$a_i$$$ different flavors of their choosing.
- A house in column $$$j$$$ will receive $$$b_j$$$ buckets of each flavor they selected.
All you have to work with are some of the orders that have already been sent in by some of the houses. Can you use these orders to recover $$$a_1, \ldots a_n$$$ and $$$b_1, \ldots, b_m$$$ uniquely?
InputThe first line of input will contain two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 1000$$$, representing the number of rows and columns of Rectangletown, respectively.
Then, $$$n$$$ lines follow, where the $$$i$$$th row contains $$$m$$$ orders: $$$x_{i,1}, \ldots, x_{i,m}$$$. Each order $$$x_{i,j}$$$ will either be the character '?', denoting an unknown order, or an integer ($$$1 \leq x_{i,j} \leq 10^9$$$), denoting the number of ice cream buckets the house at row $$$i$$$ and column $$$j$$$ ordered.
OutputIf there exists a unique sequence of values $$$a_1, \ldots, a_n$$$ and $$$b_1, \ldots, b_m$$$ that are consistent with the orders, output "YES" on its own line, followed by $$$a_1, \ldots, a_n$$$ on the second line, and $$$b_1, \ldots, b_m$$$ on the third.
Otherwise, output "NO".
ExamplesInput2 2 ? 2 2 ?Output
NOInput
3 3 2 ? 3 ? 1 ? 4 ? ?Output
YES 1 1 2 2 1 3