Star Showdown

Interview

Time limit2sMemory limit128 MB

Summary

Given row and column game counts, build the 0/1 matrix with those degrees that is lexicographically smallest row by row, or print -1 if none exists.

Level: Medium7 of 10
Topics: Greedy, Graph, Implementation, Math
Solved: No attempts yet

Problem

The best StarCraft team on the west side of the city is Jimin's team, and the best on the east side is Hansu's team. The two teams decide to face off to settle who is the best in the city.

Jimin's team has $N$ players and Hansu's team has $M$ players. Each player has a fixed number of games they must play, and this number may differ from player to player.

The match table must satisfy all of the following rules.

Every game is played between one player from Jimin's team and one player from Hansu's team.
The same pairing may occur at most once.
Every player must play exactly the number of games assigned to them.
If several valid tables exist, choose the one that is smallest in lexicographic order.

The table is an $N \times M$ matrix. Rows correspond to Jimin's team and columns to Hansu's team. If cell $(i, j)$ is $1$ , then player $i$ of Jimin's team plays against player $j$ of Hansu's team; if it is $0$ , they do not play.

The lexicographic comparison of two tables is defined as follows. First find the first row $i$ in which the two matrices differ, then find the first column $j$ in that row where they differ. The table with $0$ in cell $(i, j)$ comes first.

Given the number of games each player on each team must play, write a program that prints the lexicographically smallest table.

Input

The first line contains $N$ , the number of players on Jimin's team, and $M$ , the number of players on Hansu's team. The second line lists the number of games each player on Jimin's team must play, and the third line lists the number of games each player on Hansu's team must play. $N$ and $M$ are natural numbers at most $50$ , and each game count is a natural number at most $50$ or $0$ .

Output

Print the table on $N$ lines. Each line is an $M$ -character string formed by concatenating that row's values with no separators. If no valid table exists, print $-1$ .

Examples6

Example 1
Input
```
3 3
1 2 3
3 1 2
```
Expected output
```
100
101
111
```

Example 2

Input

4 4
3 2 1 1
1 3 1 2

Expected output

Example 3
Input
```
4 4
1 2 3 4
5 6 7 8
```
Expected output
```
-1
```
Example 4
Input
```
2 3
47 47
47 40 7
```
Expected output
```
-1
```

Example 5

Input

2 9
5 5
1 1 2 1 1 1 1 1 1

Expected output

001001111
111110000

Example 6

Input

4 6
0 0 0 0
0 0 0 0 0 0

Expected output