Lexicographically Smallest Binary Matrix

You are given two sequences of non‐negative integers: \(r_1, r_2, \dots, r_n\) and \(c_1, c_2, \dots, c_m\), which represent the number of ones required in each row and each column respectively for an \(n\times m\) binary (0/1) matrix.

Your task is to construct an \(n \times m\) binary matrix such that:

• The \(i\)th row contains exactly \(r_i\) ones.
• The \(j\)th column contains exactly \(c_j\) ones.
• Among all matrices satisfying the above, the one you output must be the lexicographically smallest. The lexicographical order is defined row by row: compare the first rows of two matrices; if they are identical, compare the second rows; and so on. In comparing two rows, treat them as sequences of characters where 0 is considered less than 1.

It is guaranteed that a solution exists for the given input.

Note: All formulas are represented in LaTeX format.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 500)\), representing the number of rows and columns.

The second line contains \(n\) integers: \(r_1, r_2, \dots, r_n\), where \(0 \le r_i \le m\).

The third line contains \(m\) integers: \(c_1, c_2, \dots, c_m\), where \(0 \le c_j \le n\).

It is guaranteed that \(\sum_{i=1}^{n} r_i = \sum_{j=1}^{m} c_j\) and that a solution exists.

outputFormat

Output the lexicographically smallest \(n \times m\) binary matrix. Each of the next \(n\) lines should contain a string of length \(m\) consisting of characters 0 and 1 (with no spaces) representing a row of the matrix.

sample

3 3
1 1 1
1 1 1

001
010
100