import java.io.IOException;
import java.nio.file.Paths;
import java.util.*;
class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int SIZE = 50;
static ArrayList<HashSet<Integer>> naapurit = new ArrayList<>(SIZE*SIZE +1);
static Random rng = new Random();
private static final ArrayList<Integer> empty=new ArrayList<>();
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(Paths.get("input.txt"));
for (int i = 0; i < SIZE*SIZE+1; i++) {
naapurit.add(new HashSet<>());
}
while (scanner.hasNextLine()) {
String line = scanner.nextLine();
String[] parts = line.split(" ");
int last = -1;
for (String part : parts) {
int ipart = Integer.parseInt(part);
if (last != -1) {
naapurit.get(last).add(ipart);
naapurit.get(ipart).add(last);
}
last = ipart;
}
}
for (int i = 0; i < naapurit.size(); i++) {
HashSet<Integer> integers = naapurit.get(i);
if (integers.isEmpty()) {
empty.add(i);
}
}
solve();
}
static int tryOne(int number, int x, int y) {
boolean b1 = insideBounds(x, y);
if (!b1) {
return -1;
}
boolean b = canBePlacedBasicRules(number, x, y);
boolean b2 = canBePlaced(number, x, y);
if (b && b2) one(number, x, y);
if (!b2 && b) {
return -3;
}
if (b) {
return 0;
}
return -2;
}
static ArrayList<Integer> order = new ArrayList<>();
static void one(int number, int x, int y) {
HashSet<Integer> set = naapurit.get(number);
if (set.isEmpty()) {
return;
}
added.put(number, new Pair(x,y));
order.add(number);
ruudukko[y][x] = number;
if (added.size() >= SIZE*SIZE-empty.size()) {
throw new IllegalArgumentException("OH MY GOD!!!");
}
for (Integer integer : set) {
int b = tryOne(integer,x+1,y);
int b2 = tryOne(integer,x-1,y);
int b3 = tryOne(integer,x,y+1);
int b4 = tryOne(integer,x,y-1);
if ((b<0 && b2 <0 && b3<0 && b4 < 0) && (b == -3 | b2 ==-3 | b3==-3 | b4==-3)) {
int index = order.indexOf(number);
//System.out.println("Removing "+index+" "+order.size()+" "+number+" "+integer);
for (int i = order.size()-1; i >= index; i = order.size()-1) {
int num = order.get(i);
Pair pair = added.get(num);
added.remove(num);
ruudukko[pair.y][pair.x] = 0;
order.remove(order.size()-1);
}
return;
}
}
if (!naapuritPaikallaan(number,x,y)) {
int index = order.indexOf(number);
for (int i = order.size()-1; i >= index; i = order.size()-1) {
int num = order.get(i);
Pair pair = added.get(num);
added.remove(num);
ruudukko[pair.y][pair.x] = 0;
order.remove(order.size()-1);
}
}
}
static boolean naapuritPaikallaan(int number,int x,int y) {
Set<Integer> naap = naapurit.get(number);
ArrayList<Integer> ruudut = new ArrayList<>();
ruudut.add(getRuutu(x+1,y));
ruudut.add(getRuutu(x-1,y));
ruudut.add(getRuutu(x,y+1));
ruudut.add(getRuutu(x,y-1));
for (Integer integer : naap) {
if (!ruudut.contains(integer)) {
return false;
}
}
return true;
}
static int getRuutu(int x, int y) {
if (!insideBounds(x,y)) {
return 0;
}
return ruudukko[x][y];
}
static boolean insideBounds(int x, int y) {
return !(x > SIZE - 1 | x < 0 | y > SIZE - 1 | y < 0);
}
static boolean canBePlacedBasicRules(int number, int x, int y) {
return !added.containsKey(number) && ruudukko[y][x] == 0;
}
static boolean canBePlaced(int number, int x, int y) {
for (Integer integer : added.keySet()) {
if (naapurit.get(integer).contains(number) && added.containsKey(integer)) {
if (!isNear(added.get(integer),x,y)) {
return false;
}
}
}
return mahdollistaLaittaaKaikkiNaapurit(naapurit.get(number),x,y);
}
static int test(int x, int y,Set<Integer> set) {
if (!insideBounds(x,y)) {
return 0;
}
int r = ruudukko[y][x];
if (r== 0) {
return 1;
}
if (set.contains(r)) {
return 1;
}
return 0;
}
static boolean mahdollistaLaittaaKaikkiNaapurit(Set<Integer> set, int x,int y) {
int tila = 0;
tila += test(x+1,y,set);
tila += test(x-1,y,set);
tila += test(x,y+1,set);
tila += test(x,y-1,set);
return tila >= set.size();
}
static void print(int[][] ar) {
for (int[] ints : ar) {
for (int anInt : ints) {
System.out.println(anInt+" ");
}
System.out.print("\n");
}
}
static boolean isNear(Pair pair,int x,int y) {
boolean xsame = (pair.x == x+1 | pair.x == x-1) && y==pair.y;
boolean ysame = (pair.y == y+1 | pair.y == y-1) && x==pair.x;
return xsame ^ ysame;
}
static int[][] ruudukko = new int[SIZE][SIZE];
static HashMap<Integer, Pair> added = new HashMap<>();
private static void solve() {
int l = 10000;
while (l > 0) {
l--;
try {
one(rng.nextInt(SIZE*SIZE-1)+1,rng.nextInt(SIZE),rng.nextInt(SIZE));
} catch (IllegalArgumentException e) {
int i = 0;
for (int[] ints : ruudukko) {
for (int j = 0; j < ints.length; j++) {
if (ints[j] == 0) {
ints[j] = empty.get(i);
i++;
}
}
}
print(ruudukko);
break;
}
}
}
}
