Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation

• # Fill the grid

Given a grid, you are asked to fill it with L-shaped trominos except for a single cell (r, c). That one cell needs to be empty.
An L-shaped tromino is a figure obtained by removing a single cell from a square.
In case it’s not possible to fill the grid, the program should print Impossible.

#### Input

The first line of the input contains a single integer n (1 ≤ n ≤ 9).
The second line contains the coordinates of the empty cell (r, c) (1 ≤ r, c ≤ ) where r is the row of the empty cell and c is the column.

#### Output

The program should print rows that contain numbers separated by a space. Each number should represent a single L-shaped tromino. The removed cell should be marked with a 0. The trominos should be indexed from 1 to . In case there are many solutions, the program can output any of those.

#### Examples

 Input Output 2 1 1 0 1 3 3 1 1 4 3 2 4 4 5 2 2 5 5

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 10 MB