Restoring the Hidden Original Image

The original image is an n×m black-and-white picture, where each pixel is either white (denoted by 0) or black (denoted by 1). Prior to an unfortunate accident where the image got wet, the number of black pixels in every row and every column was carefully recorded. After the accident, it is hard to distinguish the original picture. However, for each pixel at position \((i,j)\) one can estimate the probability (in percent) that the original pixel was black, denoted by \(p_{i,j}\%\).

The probability that a fully restored image \(s\) (where \(s_{i,j}\in\{0,1\}\)) was the original is defined as follows:

[ \prod_{i=1}^n \prod_{j=1}^m \Bigl(\left(\frac{p_{i,j}}{100}\right)^{[s_{i,j}=1]}\Bigr), ]

where \([s_{i,j}=1]\) is an indicator function which equals 1 if \(s_{i,j}=1\) (i.e. the pixel is black) and 0 otherwise. In other words, the overall probability is the product of the probabilities for every pixel that is marked as black. Note that pixels with \(p_{i,j}=0\) cannot be chosen to be black.

You are given:

• Two integers \(n\) and \(m\) representing the dimensions of the image.
• An array of \(n\) integers where the \(i\)th integer represents the number of black pixels in the \(i\)th row.
• An array of \(m\) integers where the \(j\)th integer represents the number of black pixels in the \(j\)th column.
• An \(n \times m\) matrix of integers where the \((i, j)\)th entry is \(p_{i,j}\), the probability (in percent) that the \((i, j)\) pixel was originally black.

Your task is to restore the image by assigning a value 0 or 1 to each pixel such that:

• The number of black pixels in each row and column matches the given counts.
• No pixel with \(p_{i,j} = 0\) is marked black.
• The probability \(\prod_{i,j \;:\; s_{i,j}=1} \frac{p_{i,j}}{100}\) is maximized. Equivalently, if you take logarithms, you need to maximize \(\sum_{i,j\;:\; s_{i,j}=1} \ln\Bigl(\frac{p_{i,j}}{100}\Bigr)\).

If there are multiple answers, output any one of them. It is guaranteed that at least one solution exists.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (the number of rows and columns respectively).

The second line contains \(n\) integers: the \(i\)th integer is the number of black pixels required in row \(i\).

The third line contains \(m\) integers: the \(j\)th integer is the number of black pixels required in column \(j\).

Then follow \(n\) lines, each containing \(m\) integers. The \(j\)th integer in the \(i\)th line is \(p_{i,j}\) (an integer between 0 and 100 inclusive), the probability (in percent) that the pixel \((i,j)\) was originally black.

outputFormat

Output \(n\) lines. The \(i\)th line should contain a string of \(m\) characters (each either '0' or '1') representing the restored image: '1' indicates black and '0' indicates white.

sample

2 2
1 1
1 1
80 50
50 90

10
01

</p>