P2410 [SDOI2009] Optimal Image

Xiao E found a magical picture at his friend Xiao W’s home and became very interested in it.

This picture can be regarded as a black-and-white image with $n \times m$ pixels. For convenience, we use $0$ for white pixels and $1$ for black pixels. Xiao E believed the picture hid some secrets, so he recorded the number of black pixels in each row and each column to study later. One day, Xiao W accidentally got the picture wet, and the original image became hard to recognize. Anxious, he asked Xiao E to help restore it. Based on the wet picture, they could not determine the exact image, but they could estimate the probability $p_{i, j}\%$ that each pixel was originally black. Then, the occurrence probability of a complete image can be defined as: $$\prod\limits_{i = 1}^n \prod\limits_{j = 1}^{m} p_{i, j}\% \times [s_{i, j} = 1]$$ Here $s_{i, j}$ denotes whether the pixel in the restored image is white ($0$) or black ($1$), and $[s_{i, j} = 1]$ means the value of this expression is $1$ if $s_{i, j} = 1$, and $0$ otherwise. In other words, the occurrence probability of a complete image equals the product of the probabilities of all its black pixels. Clearly, the set of black pixels in the image cannot include any pixel with probability $0$. However, Xiao E could not solve this either. So they turned to Xiao F, a programmer — that is, you. Please, based on the above information, tell them which image is the most likely original image.

The first line contains two integers $n, m$, denoting the size of the image. Lines $2$ to $(n + 1)$ each contain $m$ integers. In the $(i + 1)$-th line, the $j$-th integer $p_{i, j}$ denotes the probability that the pixel in row $i$, column $j$ is black. The next line contains $n$ integers. The $i$-th integer $a_i$ denotes the number of black pixels in row $i$. The next line contains $m$ integers. The $i$-th integer $b_i$ denotes the number of black pixels in column $i$.

This problem uses a Special Judge. Output $n$ lines, each containing a string of length $m$ consisting only of characters `0` and `1`, representing your answer. The input guarantees that at least one valid image exists. If there are multiple optimal images, output any one of them.

#### Explanation of Sample Input/Output 1 There are two possible images: ```plain 01 10 ``` ```plain 10 01 ``` The occurrence probability of the former is $0.1×0.2=0.02$, and that of the latter is $0.9×0.8=0.72$, so the latter is the optimal image. --- #### Constraints - For $20\%$ of the testdata, $n, m \leq 5$. - For $100\%$ of the testdata, $1 \leq n, m \leq 100$, $0 \leq p_{i, j} \leq 100$, $0 \leq a_i \leq m$, $0 \leq b_i \leq n$. --- Thanks to @[test12345](https://www.luogu.com.cn/user/23118) for providing the spj. Translated by ChatGPT 5