C. Crystal Mining
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Maggie discovers a large magical crystal deep within the cave. The crystal has a regular hexagonal shape, which is seen as a symbol of balance. In this world, there are $$$999$$$ types of magic particles. When these particles are arranged in a hexagonal pattern, a crystal is formed. However, if a crystal contains more than one type of particle, it is considered impure and may explode if someone attempts to release its power.

Maggie decides to extract a pure crystal, where all the magic particles are of the same type. For each potential center of the new crystal, help Maggie determine the side length of the largest pure crystal that can be extracted.

Side length: 1.Side length: 2.Not a crystal.
Input

The first line of the input contains a single integer $$$N$$$ — the side length of the crystal.

The following $$$2N - 1$$$ lines contain the description of the crystal. Each line contains multiple integers $$$a_{r,c}$$$ — the type of the magic particle at the corresponding position.

  • $$$1\leq N\leq 999$$$
  • $$$1\leq a_{r, c}\leq 999$$$
Output

For each position $$$(r, c)$$$ as the center, output the side length of the largest pure crystal.

Arrange the output in the same format as the given input, and do not output any leading and trailing spaces.

Examples
Input
2
1 1
1 1 1
1 1
Output
1 1
1 2 1
1 1
Input
3
2 1 2
2 1 2 1
2 1 1 1 1
1 1 1 1
1 1 1
Output
1 1 1
1 1 1 1
1 1 1 1 1
1 2 2 1
1 1 1
Input
5
2 8 1 6 2
8 8 8 1 4 1
8 8 8 8 4 9 1
8 8 8 8 8 2 2 3
8 7 7 8 8 8 2 2 999
7 7 7 8 8 8 2 2
7 7 8 8 8 2 2
8 8 8 8 2 2
8 8 8 2 2
Output
1 1 1 1 1
1 1 1 1 1 1
1 2 2 1 1 1 1
1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1
1 2 1 1 2 1 1 1
1 1 1 2 1 1 1
1 1 2 1 1 1
1 1 1 1 1