There is an grid. Let denote the cell in the -th row from the top and the -th column from the left.
Two cells are adjacent if they share a side. Equivalently, and are adjacent if and only if .
Color every cell with one of the colors . The coloring must satisfy all of the following conditions.
For every input satisfying the constraints, it can be proved that at least one such coloring exists. Find any coloring satisfying the conditions.
The input is given from Standard Input in the following format:
Print the coloring in lines. On the -th line, print space-separated integers , where is the color of cell .
The printed coloring must satisfy all conditions in the statement. If there are multiple solutions, print any of them.