Description

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.

Input Format

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$.

Output Format

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.

2 2
90 10
20 80
1 1
1 1

10
01

Hint

Explanation of Sample Input/Output 1

There are two possible images:

01
10

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

ing the spj.

Translated by ChatGPT 5