Consider an n×n chessboard whose top-left corner is colored white. But Alice likes darkness, so she wants you to cover those white cells for her. The only tool you have are black L-shaped tiles each of which covers 3 unit cells.
Formally, each tile covers 3 unit cells satisfying the following:
No two tiles should overlap (cover the same cell) or go outside the board. Since these tiles cost a lot, you have to cover all the white cells using the minimum number tiles.
Input Format
Output Format
In case of n=1, there's a single cell which is white. Since one tile needs 3 empty cells, there's no way to cover this cell.
In case of n=4, one possible covering (represented by the sample output) is the following: