Baltic Olympiad in Informatics: 2001 Day 1, Problem 3

Mathematician Andris likes different puzzles and one of his favourites is a covered box of mirrors. If we look at the horizontal cross-section of such a box, we can see that its basement contains ~n \times m~ square cells (~n~ rows and ~m~ columns). In each cell, there can be placed a mirror which is oriented diagonally from the lower left corner to the upper right corner. Both sides of the mirror reflect light. At the box edges opposite to each cell row or column there is a gap through which you can light a beam into the box or the beam can come out of the box. Through each gap, you can light the beam in only one direction — perpendicular to the edge containing the gap. Therefore, a beam reflecting from the mirror changes its direction by ~90^\circ~. When the beam goes through empty cells, its direction doesn't change. Gaps are numbered consecutively from ~1~ to ~2 \times (n+m)~, around the box, counter-clockwise, starting from the gap on the left side of the upper left cell and going downwards.

Since the arrangement of mirrors in the box is not visible, the only way to determine it is by lighting beams in some gaps and watching where light comes out. Write a program that determines which cells have mirrors and which cells are empty.

Input Specification

The first line of input contains two space-separated integers ~n~ and ~m~ ~(1 \le n, m \le 100)~.

Each of the following ~2 \times (n+m)~ lines contains one positive integer. The number in the ~i+1^\text{th}~ line denotes the number of the gap from which light comes out if it is shone into gap number ~i~.

Output Specification

Your program should output ~n~ lines, each of them containing ~m~ space-separated integers. The ~j^\text{th}~ number in the ~i^\text{th}~ line should be ~1~, if there is a mirror in the cell in the ~i^\text{th}~ row and ~j^\text{th}~ column of the box, or it should be ~0~ if the cell is empty.

If there are several possible solutions, your program should output anyone of them.

Sample Input

2 3
9
7
10
8
6
5
2
4
1
3

Sample Output

0 1 0
0 1 1

Sample Explanation

The diagram above shows the states of each cell and the path of light shined into gaps ~2~ or ~7~. It's easy to see that light shined in gap ~1~ will exit gap ~9~, light shone in gap ~3~ will exit gap ~10~, and so on.