Lösungen#

Den Code des Modells kann man grob in 6 Teile untergliedern:

  1. Import von zusätzlichen Modulen

  2. Definition wichtiger Parameter der Simulation

  3. Erstellen der Population

  4. Starten der Simulation mittels For-Loop durch die Zeit

  5. Grafische Darstellung der Simulation

  6. Handeln der Agenten

Ich gebe diesmal einen großen Teil des Codes, nämlich die Schritte 1 - 5, vor. Deine Aufgabe ist es zunächst den von mir vorgegebenen Code so gut es geht nachzuvollziehen. Im nächsten Schritt sollst du das Handeln der Agenten, die vier Handlungsregeln der Agenten, als sechsten Schritt der Simulation zum Code hinzuzufügen.

Aufgabe 1#

Im Folgenden beschreibe ich die einzelnen Schritte des Codes jeweils kurz.

  • Versuche den Code so gut es geht nachzuvollziehen!

Schritt 1 - Import von zusätzlichen Modulen#

Zu Beginn eines jeden Python-Programmes müssen die zusätzlichen Module, die wir benötigen, importiert werden. In diesem Fall wird das Modul random aus der Standard-Bibliothek importiert. Wir brauchen das Modul random später, um das zufällige Trödeln der Agenten einzubauen.

Schritt 2 - Definition wichtiger Parameter der Simulation#

An dieser Stelle werden wichtige Parameter unserer unserer Simulation definiert. Wir können hier als Parameter all diejenigen Werte verstehen, die das allgemeine “Verhalten” unserer Simulation beeinflussen. Ich schreibe übrigens die Variablennamen der Parameter alle bewusst groß, da es in der Informatik eine Konvention gibt, Variablen, deren Werte sich im gesamten Verlauf des Programmes nicht verändert, groß zu schreiben. Eine solche Variable nennt man auch Konstante.

  • TICKS: Dies ist die Anzahl der simulierten Zeitschritte. In jedem Zeitschritt “wiederholt” sich der gesamte Ablauf der eigentlichen Simulation einmal.

  • MAX_SPEED: Dies ist Höchstgeschwindigkeit der Agenten. Die Geschwindigkeit ist definiert als Anzahl der “Zellen” bzw. Straßenabschnitte sich ein Agent pro Zeitschritt nach vorne bewegt.

  • DAWDLING_PROB: Gibt die Wahrscheinlichkeit pro Zeitschritt an, zu trödeln d.h. die Geschwindigkeit ohne Grund um eine Einheit zu reduzieren.

  • N_AGENTS: Anzahl der Agenten in der Population.

  • INITIAL_DISTANCE: Die Agenten werden am Anfang mit gleichmäßigem Abstand zueinander auf der Straße verteilt. Diese Variable gibt die anfängliche Distanz von Agent zu Agent an.

  • STREET_LEN: Die Länge der Straße bzw. die Anzahl an Straßenabschnitten (Zellen) der Straße, welche von den Agenten befahren werden können. Diese ergibt sich aus der Anzahl der Agenten und deren anfängliche Distanz zueinander.

Schritt 3 - Erstellen der Population#

Wie so oft wird zunächst eine leere Liste population erstellt, welche dann in einem For-Loop nach und nach mit Agenten befüllt wird.

Die Eigenschaften der Agenten repräsentieren wir diesmal als ein Dictionary. Das vereinfacht uns vieles. Z.B. können wir die einzelnen Eigenchaften der Agenten benennen und dann auch mit Namen auf diese zugreifen. Genau wie Listen sind Dictionaries gehören Dictionaries zu den veränderbaren Datentypen. Dadurch können wir sehr einfach die Eigenschaften der Agenten (z.B. innerhalb von For-Loops) verändern.

In einem ersten For-Loop erstelle ich jeden Agenten zunächst mit vier Eigenschaften und hänge diese an die Liste population.

  • "id": Ist eine Zahl zur eindeutigen Identifikation der Agenten. Diese brauchen wir in diesmal noch nicht unbedingt, dennoch kann eine solche ID hilfreich beim Test des Modells/Codes sein. Da ich als ID einfach den Wert der Schleifenvariable i einsetze, entspricht die "id" in diesem Fall auch der Position des Agenten innerhalb der Liste population (ACHTUNG: Nicht mit der Position auf der Straße verwechseln!). Diese Eigenschaft der "id" können wir tatsächlich doch auch schon diesmal gebrauchen.

  • "position": Ist die aktuelle Position des Agenten auf der Straße. Am Anfang ergibt sich die Position auf der Straße aus der Position in der Liste population multipliziert mit der anfänglichen Distanz von Agent zu Agent.

  • "speed": Ist die aktuelle Geschwindigkeit des Agenten definiert als Straßenabschnitte, die sich ein Agent pro Zeitabschnitt nach vorne bewegt. Ich setze diese hier anfänglich auf die maximal fahrbare Geschwindigkeit.

  • "space_ahead": Das ist die Anzahl der freien d.h. befahrbaren Straßenabschnitte vor dem Agenten bis der nächste Agent auf der Straße kommt. Die Anzahl der freien Straßenabschnitte vor einem Agent ist immer um 1 kleiner als die Distanz zum vorausfahrenden Agenten. Am Anfang ergibt sich der Freiraum vorm Agenten daher als INITIAL_DISTANCE - 1.

Nachdem nun die Population erstellt wurde, füge ich nochmal zwei Eigenschaften zu jedem Agenten hinzufügen: den jeweils vorausfahrenden Agenten und den jeweils hinterherfahrenden Agenten. Da in unserer Simulation nicht überholt werden kann, sind dies immer die selben zwei Agenten. Um später die Interaktion zwischen den Agenten bzw. die Reaktionen der Agenten aufeinander zu modellieren, ist es praktisch, wenn sich alle Agenten merken, wer vor oder hinter dem Agenten fährt. Tatsächlich speichern wir dabei nicht eine Kopie der jeweiligen voraus- oder nachfahrenden Agenten selbst ein, sondern nur Verweise bzw. Zeiger auf die jeweiligen Agenten-Objekte. Das ist sehr praktisch, weil wir so über einen Agenten immer auch auf den jeweils voraus- oder hinterherfahrenden Agenten zugreifen können und diesen verändern können (da die Agenten als veränderbare Dictionaries repräsentiert sind)! Auf jeden Agenten wird nun also einmal in der Liste population, aber auch einmal innerhalb eines anderen Agenten als vorausfahrender Agent und einmal innerhalb eines anderen Agenten als nachfahrender Agent verwiesen.

Die voraus- und nachfahrenden Agenten werden unter "agent_ahead" und "agent_behind" als Eigenschaft eines jeden Agenten eingespeichert. Versuche mal nachzuvollziehen, wie die beiden Agenten jeweils gefunden werden. Wenn dir das nicht 100% klar ist, ist das aber nicht so schlimm. Merken solltest du dir v.a., dass sich unter dem Dictionary-Key "agent_ahead" der vorausfahrende und unter dem Dictionary-Key "agent_behind" jeweils der hinterherfahrende Agent befindet.

Schritt 4 - Das Starten der Simulation mittels For-Loop durch die Zeit#

Nach der obigen Initialisierungsphase wird nun die eigentliche Simulation gestartet. Mittels For-Loop wird jeder nun nachfolgende, eingerückte Code für jeden zu simulierenden Zeitschritt wiederholt. In jedem Zeitschritt wird die grafische Darstellung aktualisiert und ausgegeben sowie jeder Agent zum handeln gebracht.

Schritt 5 - Die grafische Darstellung der Simulation#

An dieser Stelle wird die sehr simple grafische Darstellung des Modells erstellt. Diese ist vom Prinzip her genau gleich wie die grafische Darstellung in den Übungsaufgaben des letzten Kapitels. Diesmal werden leere Straßenabschnitte allerdings als "." und Agenten als Zahl, die die aktuelle Geschwindigkeit anzeigt, dargestellt.

Schritt 6 - Das Handeln der Agenten#

In diesem Schritt Handeln die Agenten. Hier ist es dann gleich deine Aufgabe, die noch fehlende Umsetzung der vier Handlungsregeln der Agenten zu programmieren. Einen Teil, welcher nicht direkt in den 4 Handlungsregeln besprochen wird, habe ich aber auch hier bereits vorgegeben. In diesem von mir bereits vorgegebenen Teil geht es darum, dass nachdem die Agenten entsprechend der 4 Handlungsregeln gehandelt haben, nochmal alle Agenten durchgegangen werden, um ihre “Sicht” auf die Straße zu aktualisieren. Da die Agenten gefahren sind, hat sich evtl. der Abstand zum vorausfahrenden (und zum nachfahrenden Agenten) verändert. Diese Information müssen wir natürlich den Agenten mitteilen, damit sie im nächsten Zeitschritt ein richtiges Abbild der Straße im Kopf haben.

Aufgabe 2#

Der gesamte Code ist, so wie er unten zu sehen ist, vollkommen funktionsfähig. Du kannst den Code kopieren und komplett ausführen. Achte dabei, dass alle Einrückungen des Codes exakt so bleiben! Du solltest nach der Ausführung des Codes in der Konsole sehen, dass die Simulation entsprechend der simulierten Zeitschritte ausgeführt wurde, aber die Agenten sich nicht nach vorne bewegen. Um das zu ändern, sollst du nun an die entsprechenden Stellen die vier Handlungsregeln einbauen.

  • Um die vier Handlungsregeln für jeden Agenten umzusetzen, musst du jeden Agenten nacheinander durchgehen. Starte einen entsprechenden For-Loop. Denk daran, dass die Agenten als Dictionaries veränderbare Agenten sind und daher direkt über die Agenten in der Liste population loopen kannst (und nichts mit range() machen musst). Die folgenden Handlungsschritte werden dann innerhalb dieses For-Loops für jeden Agenten umgesetzt.

  • Acceleration: Die erste Handlungsregel besagt, dass alle Agenten, die nicht die maximale Geschwindigkeit aufweisen, ihre Geschwindigkeit um 1 erhöhen. Überprüfe, ob der Agent langsamer als die zulässige Geschwindigkeit fährt. Wenn ja, dann erhöhe dessen Geschwindigkeit um 1.

  • Slowing down: Die zweite Handlungsregel besagt, dass der Agent überprüft, ob er mit der aktuell gefahrenen Geschwindigkeit nicht möglicherweise zu schnell ist und er mit dieser Geschwindigkeit gegen das vorausfahrende Auto stoßen könnte. Falls also ein anderes Auto in diesem Zeitschritt bei dieser Geschwindigkeit im Weg sein könnte, dann bremst der Agent ab und fährt genau hinter das vor ihm fahrende Auto. Überprüfe, ob die Geschwindigkeit des Agenten zu hoch ist, der Agent also gegen das vorausfahrende Fahrzeug stoßen würde. Falls das so ist, dann stelle die Geschwindigkeit des Agenten genau so ein, dass der Agent genau hinter den vorausfahrenden Agenten fährt.

  • Randomization: Die dritte Handlungsregel modelliert das willkürliche Abbremsen von Menschen, weil sie z.B. hinter dem Steuer schlafen oder auf das Handy schauen. Sie besagt, dass ein Agent, insofern dieser eine Geschwindigkeit > 0 aufweist, mit einer gewissen Wahrscheinlichkeit die Geschwindigkeit zufällig um den Wert 1 verringert. Setze diese Verhaltensregel um. Die Wahrscheinlichkeit für das zufällige Abbremsen ist durch die Variable DAWDLING_PROB festgelegt. Einen Zufallswert zwischen 0 und 1 kannst du dir mit der Funktion random() aus dem Modul random erstellen.

  • Car motion: Die letzte Handlungsregel beschreibt nun das eigentliche Fahren der Agenten. Die neue Position des Agenten ergibt sich aus der aktuellen Position plus der aktuellen Geschwindigkeit. Aber Achtung: Genau wie in den Übungsaufgaben des vorherigen Kapitels haben wir auch hier wieder das Problem, dass die Agenten irgendwann auf eine Position fahren wollen, die es auf der Straße gar nicht gibt. Wir müssen also auch hier wieder sicher stellen, dass die Position der Agenten immer wieder ab einer gewissen Grenze genullt wird und wir somit rechts herausfahrende Agenten wieder links auf die Straße setzen. Wir brauchen also den Modulo, um die möglichen Positionen automatisch zu begrenzen (Prinzipiell könntest du das Problem nun auch mit einem If-Statement lösen, das macht es aber eigentlich nur umständlicher).

### Schritt 1: Import von zusätzlichen Modulen ###
import random 


### Schritt 2: Definition wichtiger Parameter der Simulation ###

TICKS = 10
MAX_SPEED = 5 
DAWDLING_PROB = 0.1 
N_AGENTS = 20 
INITIAL_DISTANCE = 5 
STREET_LEN = N_AGENTS * INITIAL_DISTANCE


### Schritt 3: Das Erstellen der Population ###

# Leere Liste, die gleich mit Agenten befüllt wird
population = []

# für jeden zu erstellenden Agenten
for i in range(N_AGENTS):
    
    # Agent als Dictionary erstellen
    agent = {
        "id": i,
        "position": i * INITIAL_DISTANCE,
        "speed": MAX_SPEED,
        "space_ahead": INITIAL_DISTANCE - 1,
    }
    
    # Agent an die Populationsliste hängen
    population.append(agent)

    
# Population nochmal überarbeiten - jeweils vorausfahrende und nachfahrende Agenten einspeichern
# für jeden Agenten in Population
for agent in population:
    # den vorausfahrenden Agenten merken/als Eigenschaft einspeichern
    agent.update({"agent_ahead": population[(agent["id"]+1)%len(population)]})
    
    # den nachfahrenden Agenten merken/als Eigenschaft einspeichern
    agent.update({"agent_behind": population[(agent["id"]-1)%len(population)]})
                 

        
### Schritt 4: Das Starten der Simulation mittels For-Loop durch die Zeit ###

# für jeden Zeitschritt
for tick in range(TICKS):
    
    ### Schritt 5: Die grafische Darstellung der Simulation ###
    
    # "leere" Straße als String von Punkten erstellen
    street_as_list = []
    for i in range(STREET_LEN):
        street_as_list.append(".")
        
    # für jeden Agenten
    for agent in population:
        # Agenten auf entsprechender Position auf Straße einfügen
        # Agent wird in diesem Fall als dessen Geschwindigkeit repräsentiert
        street_as_list[agent["position"]] = str(agent["speed"])
    
    # Repräsentation der Straße in einen String umwandeln
    street_as_string = "".join(street_as_list)
    
    # grafische Darstellung in Konsole anzeigen
    print(street_as_string)
    
    
    ### Schritt 6: das Handeln der Agenten ###
    
    # für jeden Agenten (die vier Handlungsschritte umsetzen)
    
        # 1. Acceleration
        
        
        # 2. Slowing down
        
        
        # 3. Randomization
        
            
        # 4. Car motion
        
    
    
    
    # für jeden Agenten (ihre Sicht auf die Straße aktualisieren)
    for agent in population:
        # neue Anzahl der freien Zellen vor Agent berechnen und einspeichern
        agent["space_ahead"] -= agent["speed"]
        # neue Anzahl der freien Zellen vor dem jeweils NACHFAHRENDEN Agent berechnen und DIESEM einspeichern
        agent["agent_behind"]["space_ahead"] += agent["speed"] 

5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....
5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....5....

### Schritt 1: Import von zusätzlichen Modulen ###
import random 


### Schritt 2: Definition wichtiger Parameter der Simulation ###

TICKS = 500 
MAX_SPEED = 5 
DAWDLING_PROB = 0.3
N_AGENTS = 15
INITIAL_DISTANCE = 6
STREET_LEN = N_AGENTS * INITIAL_DISTANCE


### Schritt 3: Das Erstellen der Population ###

# Leere Liste, die gleich mit Agenten befüllt wird
population = []

# für jeden zu erstellenden Agenten
for i in range(N_AGENTS):
    
    # Agent als Dictionary erstellen
    agent = {
        "id": i,
        "position": i * INITIAL_DISTANCE,
        "speed": MAX_SPEED,
        "space_ahead": INITIAL_DISTANCE - 1,
    }
    
    # Agent an die Populationsliste hängen
    population.append(agent)

    
# Population nochmal überarbeiten - jeweils vorausfahrende und nachfahrende Agenten einspeichern
# für jeden Agenten in Population
for agent in population:
    # den vorausfahrenden Agenten merken/als Eigenschaft einspeichern
    agent.update({"agent_ahead": population[(agent["id"]+1)%len(population)]})
    
    # den nachfahrenden Agenten merken/als Eigenschaft einspeichern
    agent.update({"agent_behind": population[(agent["id"]-1)%len(population)]})
                 

        
### Schritt 4: Das Starten der Simulation mittels For-Loop durch die Zeit ###

# für jeden Zeitschritt
for tick in range(TICKS):
    
    ### Schritt 5: Die grafische Darstellung der Simulation ###
    
    # "leere" Straße als Liste von Punkten erstellen
    street_as_list = []
    for i in range(STREET_LEN):
        street_as_list.append(".")
        
    # für jeden Agenten
    for agent in population:
        # Agenten auf entsprechender Position auf Straße einfügen
        # Agent wird in diesem Fall als dessen Geschwindigkeit repräsentiert
        street_as_list[agent["position"]] = str(agent["speed"])
    
    # Repräsentation der Straße in einen String umwandeln
    street_as_string = "".join(street_as_list)
    
    # grafische Darstellung in Konsole anzeigen
    print(street_as_string)
    
    
    ### Schritt 6: das Handeln der Agenten ###
    
    # für jeden Agenten (die vier Handlungsschritte umsetzen)
    for agent in population:
        # 1. Acceleration
        if agent["speed"] < MAX_SPEED:
            agent["speed"] += 1
        
        # 2. Slowing down
        if agent["speed"] > agent["space_ahead"]:
            agent["speed"] = agent["space_ahead"]
        
        # 3. Randomization
        if agent["speed"] > 0 and random.random() <= DAWDLING_PROB:
            agent["speed"] -= 1
            
        # 4. Car motion
        agent["position"] = (agent["position"] + agent["speed"]) % STREET_LEN
    
    
    
    # für jeden Agenten (die Anzahl der freien Straßenabschnitte neu berechnen)
    for agent in population:
        # neue Anzahl der freien Zellen vor Agent berechnen und einspeichern
        agent["space_ahead"] -= agent["speed"]
        # neue Anzahl der freien Zellen vor dem NACHFAHRENDEM Agent berechnen und DIESEM einspeichern
        agent["agent_behind"]["space_ahead"] += agent["speed"] 

5.....5.....5.....5.....5.....5.....5.....5.....5.....5.....5.....5.....5.....5.....5.....
.....5.....5.....5.....5.....5.....5....4......5.....5....4......5.....5....4.....4......5
...4......5.....5.....5....4......5...3.....4.......5....4....4......4.....4....4.....4...
.5.....4.......5.....5....4.....5....3....4......5.....3.....4.....5.....4.....4.....5....
5.....5.....5.......5...3......5....4....4....4.......5....4......5.....5....4.....4......
....4......5.....5....2.....4......4...3.....4.....5......4.....5.....4.....4....4.....4..
..5......5......5....4...3.......5....3....4......5.....5.....4......5.....5....4.....5...
.5.....5......5....3...2....3........4....4.....5......5.....5.....5......5....4.....5....
5....4......5.....4...3...3....3.........4.....5....4.......5....4......5.....4.....5.....
...3.....4.......5...3...3....4...3...........5....4.....5......4....4.......5....4......5
..3....4......5.....3...3...3....3...3...........3......5.....5.....4....4.......4.....5..
.4....4.....5......5...3...3...3...2.....4...........4......4......5....4....4........5...
.....4.....5....4....2...2...2....3..2.......4...........4.......5....3.....4.....5......3
..3......4.....4....4...3..2....3...2...3.........5...........5......4....4......5.....5..
3.....4.......5....4...3..2...3....3..2.....4..........5...........5.....4.....5......5...
...3......4......3....3..2...3...3..1....3.......5..........5..........4......5.....5...2.
2......4.......5.....4..2..2....3..2..2......4........5.........4...........5......5...3..
..2.........5.......5..2..2..2...1...2..2.........5........5.........5..........4.....3..2
1....3...........5...1...2..2..2...2...2...3...........5........5........4...........5.1..
..2......4..........3..2...2..2...3..2...2.....4............5........5.......4.......0...2
.2...3........5.......2...3..2...3.1...2....3......4.............5.......4.......4...0....
....3....4.........5....2...2...3.1.1.....3.....4.......5.............5.......5.....3.1...
........4.....5........4..2...2..1.1..2......3......4.......4..............5.......5.1..2.
.3...........5....4......2..2...2.1..2..2........4......4........5..............5...1.1...
.....4..........3......5..1...2..1..2..2..2...........5.....4.........5............3.1..2.
.3........5.........4....2.1....2..2..2..2..2..............5.....5.........5.......0...2..
3....4.........5........4.1..2....2..2..2..2...3................5.....5.........5...1.....
...3.....4.........4.....1..2...3..1..1..1...2....3..................5.....5......2...2...
.......4.....4..........5..2...3.1...2.1...2....3.....4...................5....4.....3...3
...4........5.....5.......2...3.1.1...1.1.....3.....4.....4...................4....4....3.
..4.....5........5.....5.....30..1..2.0..1........4......5....4..................3.....4..
.4....4......5........5.....50.1...20..1...2...........5....3......5................3.....
.....4....4......4.........50.1..2.0.1...2....3...........3.....4.......5...............4.
...5.....4.....5......5....0.1..2.1.1..2....3.....4..........3.......5.......5............
.......4......5.....5.....4.1.1.0.0...2..2.....3.......5........3.........5.......5.......
...........4.......5.....50..10.0..1...1....3......4.......4........4.........4........5..
.4..............5.......50.1.00.0...1....2......4.......5......4.........5........4.......
......5.............4...0.1.100..1....2.....3.......4........5......5........4.........5..
..5........5..........2..1.100.1...2.....3......4........5........5.....4.........5.......
.......5........5.......2.100.1.1.....3.....3........5.......4........4......5........4...
.5..........5........5...100.10...2.......4.....4........4.......4.........5......5.......
......5.........4.......300.10.1.....3.........5.....5........5.......5.........5.....4...
.5.........5.........5..000.00..1........4.........4......5.......4........5.........5....
5....4.........4.......200.10.1...2..........4..........5......5.......5........5.........
....4....4..........5..00.10.1..2....3............5..........5.....4........5........5....
5.......4.....5......1.00.0.1..2..2.....3..............5..........5.....5........5........
.....5......4......5..10.1.1.1..1...2.......4...............5..........5....4.........5...
.5.......4.......5..1.0.1.1.1..2..2....3.........5..............4..........4....4.........
......5.......5....2.1.1.1.1..2.1...2.....3...........5..............5........3......5....
5..........5.....3..10..10...2.1..2....3.....3............4...............5.......4.......
.....5..........5..20.1.00....1..2...3.....4.....4.............5...............5.......5..
..5.......5.......200.0.00.....1....3....4.....4......5.............5...............5.....
......4........5..000..10.1......2......4.....5.....5......5............4................5
....5......5.....2000..0.1..2.......3.......4......5.....5......5............5............
.........5......5000.1.0...2...3........4........5......5.....5......5............5.......
..............5.0000..10......3....4.........5.......4.......5....4......4.............5..
..5............1000.1.0.1........3......5.........5......4......3.....4......4............
......4........0000..10..1..........3........5.........5......5....3.......5......5.......
...........5...000.1.0.1..1............3..........5.........5.....4....4........5......5..
..5..........2.00.1.1.1..2..2.............3............5........4....3......5........5....
.......5......10.10..1..2..2...3..............4............4........4...3........5.......4
...4........5.0.100....2..2...3....4..............4.............5......3....4.........5...
.5......5....1.100.1.....2...3....4.....5.............4..............5.....4.....5........
......5....3..1000...2......3....4.....5.....5.............5..............5....4.....4....
5.........4.1.000.1.....3.......4....4......5.....5.............5.............4.....5.....
.....5.....10.00.1..2......3........4....4.......5.....5.............5.............5....4.
...5......50.100...2...3......3.........4....4........5.....5.............5............4..
.4......5.00.00.1....2.....4......4.........4.....5........5....4..............5..........
.....4..0.0.10.1..2.....3.......5......5........4......5......3.....4..............4......
.......2.1.10.1..2..2.......4........5......5........5......5.....4......5..............5.
...5....1.100..1..1....3.........5........5.....4.........5......5.....5......5...........
.......4.1000....2..2.....3...........5.......4.....4.........4.......5.....5......5......
.......0.000.1....1....3.....3.............5.......5.....5.........5.......5.....5......5.
...5....100.1.1.....2.....3......4..............5.......5.....5........4........5....4....
5.....3.000.0..1.......3......4.......5.............4........5....4.........5......3......
.....5.100.1.1..1.........3.......4........5.............5......3.....4..........5.....4..
.4....100.1.1..2.1............4........5........5.............5.....4.....4...........5...
4....4000..1..2.1..2..............4........4........4..............5.....5....4...........
....4000.1...2.1..2...3...............4........4........4..............4....3.....4.......
....0000...2..1.1....3...3.................5........5........5.............4....4......5..
..5.000.1....2.1..2.....3....4.................4........4.........5...........3......5....
5..100.1..2...1..2..2.......4....4..................5........5........4...........4.......
.1.000...2...3..2..2..2........3......5..................5.......4.........5...........5..
3.100.1.....3.1...2.1....3........3........5..................5.......5.........5.........
.1000..1.....1..2..1..2......4........4.........5.................4........5.........5....
5000.1..1......2..2..2...3........5.......4..........5.................5........5.........
000.1..2..2......2..2...3...3..........5......4..........4..................5........5....
00.1.1...2...3.....2...3..2.....4..........4.......5..........5..................5......3.
0.10..1....2.....4...2...2..2........5..........5......4...........5..................5.0.
.10.1...2.....3.....3...3..2...3..........5..........5......5..........4...............1.1
100...2....3......4...2...2..2.....4...........5.........4.......5..........5..........0..
00.1.....3.....4.....3...3.1....3.......5...........5........4........5..........5.....0..
0.1.1.......3......4....30...2......4........5...........5........5........5.........4..1.
.1.1..2.........4.....3.0.1.....3........5.......4............5........5........5.....1.0.
.0...2...3...........5.1.1.1........4.........5.......5............5........5.......4..1.1
1.1.....3....4........10.0...2...........5.........5......4.............5........5....2.1.
.1.1.......3......5...0.1.1.....3............4.........4.......5.............5......3.0..1
1.1.1..........4.....3.10..1........4.............5.........5......4..............5..10...
.1.1.1..............50.0.1..1............5.............5.........5......5...........20.1..
.0.0..1.............00..1..2.1................5.............5........4.......5......0.1..2
1.1.1...2...........0.1...2.1..2..................4..............5........5.......5..1.1..
.10...2....3.........1..2.0...2...3....................5..............5........5....20...2
10.1.....3....3........2.10......3...3.....................4..............4........400....
0.1.1.......3.....4....0.0.1........3....4.....................4..............4....000....
.1.1.1.........3......4.1.1..2.........3......5.....................5.............400.1...
..1.1..2...........4...1.1..2..2...........4.......5....................4.........00.1.1..
...1..2..2............3.1.1..1....3.............5.......5....................5....0.1.1.1.
2....2..2..2...........1.1..2.1.......4..............5.......5..................3.0..1.1..
..2....2..2...3........0...20...2..........5..............5.......5..............1.1..1..2
.2..2....2...3....4.....1..00......3............5.............4........5..........1.1...2.
...2..2.....3....4.....5..20.1.........4.............5............4.........5......1..2..1
.2...2...3......4.....5.1.0.1..2............5.............5............5.........5...2..2.
2..2....3....4.......5.1.1.1.1....3..............5............4.............5.......3..2..
..2...3.....4....4....1.1.1.1..2.....3...............4.............5.............5...1..1.
2....3....4.....4....4.1.1.1.1....3......4................5.............5...........3..2..
...3.....4.....5....40..1.1.1..2......4.......5................5.............5.......1...2
..3....4......5....40.1..1.1..2...3........5.......5................5............4.....2..
3.....4.....5.....40.1.1..1..2...3...3..........5......4................4.............5...
....4......5.....50.1.1..2..2...3...3....4...........5......5................5..........2.
.3.......5......500..1..2.1....3..2....3......5...........5......5...............4........
.....4.......4..00.1...2.1..2....2...3....3........5...........5......5...............5...
.5.......4.....200..1...1..2...3....3...3.....4........4............5......5..............
......5.......5000....2...2...3....4..2....3.......5........5............5......5.........
...........5..000.1......3...3....4..2...3.....4.......4.........5............5......5....
5............200.1..2.......3....4.1....3....4......5......4..........5...........4.......
.....5.......00.1.1...2........3..1..2.....3.....4.......5......5.........4............5..
..5.......5..0.1.1..2...2........2.1....3......4......5.......5......5........4...........
.......5....2.1.1..2...3...3.....0...2......4.......5.....4........5......5........5......
...........40..1.1....3...3...3...1.....3........5......4.....4.........5.....4.........5.
...5.......0.1..1..2....2....3...3..2.......4.........5......5.....5.........5.....5......
.......4....1..2..2...3....3...2..1....3........4.........4.......5.....5.........5.....5.
...5......3...2..2...3....4...3..2..2.....3..........5.........5.......5.....5.........5..
..5....4.....3.1....3....4...3.1...2...3......4...........5.........5.......5....4........
......4.....5.1..2......4..2..1.1....2.....4.......5...........5........4......3......5...
.5........4.0...2...3....1..1..1..2.....3.......5......4............5........5.....4......
.....4.....1.1....2.....4.1...2..2...3......4.......4.......5............5.......4.....4..
..5......4..1..2.....3...1..2..1....3....4.......5.......5.......5...........4........5...
4.....4....2..2..2......3.1...2.1.......4.....5......4........5.......5...........5.......
.....5...3...2..2..2.....1..2.0...2..........5.....5......5........5......4............5..
..5.....3..2...2.1...2....1..1.1....2.............5....4.......5........5.....4...........
.......5..2..2..1..2....3..1..1..2.....3.............3......5.......5.......4......5......
.........2..2..2..2...3..1..1...2...3......4............3........5......4........5......5.
...5.......2..2..2...3.1...2..2....3....4.......5..........3.........4......4.........5...
.5......5....2.1....3.1.1...1....3.....4.....5.......5.........4.........4.......5........
......5.....4.1..2..0..1..2...2......4......5.....5......4.........4..........5......4....
5..........5.1..2.1..1..1....3...3........5......5.....5......5........4..........4.......
....4.......1..2.1..2..2..2.....3....4........4.......5.....5.....4.........5..........5..
..5......5...1.0...2..2..2...3......4....4........4........5....4......5.........5........
......4.....3.1.1...1...2...3...3......3......5.......4........4.....5.....4..........5...
.5.........5.1.1..2...2....3...3....4......4......4........5.......4.....4......5.........
......5....0..1..2...3..2.....3....4.....5......5......5.......4........5....4.......5....
..........40....2...3..2...3......4....4......5......5......5.......5.......4.....5......4
...4......00.......3.1....3....4......4.....5......5......5......5.......5......4......5..
..5.....5.00.......0...2......4....4.......5....4......4.......5.....4........5.....4.....
......4.0.0.1.......1....2........4.....5.....3.....4......4........5....4.........5.....5
....5.0..1.1.1.......1......3.........4.....4.....4......5......5.......4....4..........5.
...50..1..1.1.1........2........4.........4.....4......5......5......5.....3......5.......
...0.1...20..1..2........2...........5.........5.....5......5......5......5....4......4...
.5..1..2.00....2...3........3.............5.........5.....5......5......5....3......5.....
...2..2.10.1......3....4........4..............5.........5.....5.....4.....3.....4.......5
..3.1..10.1..2........4.....5........5..............5.........5....4......5....4......5...
4..1..20.1..2..2..........4......5........5..............5........4.....5....3......5.....
..2..20.1.1...2...3............5......5........5.............4.........5...3....3........5
.2..20.10..1....2.....4.............5.....4.........5.............5.......3....4....4.....
..1.0.10.1...2.....3......4..............5.....5.........5............4......3.....4....4.
2.0..100...2...2......3........5..............5....4..........5............5.....4....3...
.1.1.00.1....2...2........4........4..............4.....5..........5...........4.....4..2.
2.10.00...2.....3...3..........5........5.............4......5..........5...........5..2..
.100.0.1.....3.....3....4...........5........5.............5......5.........4........1..1.
200.1.1.1........4.....4.....5..........4........4..............5......5.........5.....2..
00.10..1..2..........4......5....4...........5.......4...............5......5.........5.1.
00.0.1...2...3............5.....4....4............5.......5..............4.......5....0.0.
0.1.1.1.....3....4.............5....4.....5............5.......5.............4......3..1.1
.10.0...2.......4.....5............4.....5.....5............5......4.............4...1.0.0
.0.1.1.....3.........5.....5............5.....5....4.............5.....4............3.10.0
10..1..2......3...........5.....5............5....4....4.............4......5........10.1.
0.1...2..2........4............5.....5...........4....4.....5............4.......5...0.1.1
.1.1....2...3.........4............4......5..........4....4......5............5.....30..10
1.1..2.....3....4.........4............4.......5........3......5......5...........4.0.1.0.
.1..2..2......3......5.........5............5......4........4.......5......5.......1.10.0.
...2..2...3.......4.......5.........5............5......5........5.......5......5..0.0.1.1
.2...2..2.....4........5......4..........5...........4.......5........5.......5...2.10..1.
2...3..2...3.......5........5......5.........4...........4........5........5.....3.10.1...
...3..2..2....3........4.........5......5.........5..........4.........5........5.10.1..2.
2...1...2..2......4........4..........5.....4..........5..........5.........5...0.00...2..
..2..1....2..2.........5........5..........5.....5..........5.........4........3.10.1...1.
2...2..2....2...3...........5.......4...........5.....5.........4..........5....10.1..2...
..2...2..2.....3....4...........4........5...........5.....5.........5.........40.1..2..2.
.3..2...2..2.......4.....5...........5........5...........5....4..........5....0.1..2.1...
..1....3..2..2..........5.....5...........5........5.........3......5.........4.1.1..1..2.
.3..2....2.1....3............5....4...........4.........5........4......4......1.1..2..2..
..1....3.0...2.....3.............4.....5...........5.........5.......4.......5.0..1..1...2
.2..2...1.1.....3......4..............5.....5..........4..........5.......5...1.1...2..2..
...2...3.1.1.......3........5..............5.....5.........4...........5.....3.1..2...2..2
.2....3.10...2.........4.........5..............5.....5........4............5.1..2...3.1..
...2...100......3..........4.........4..............4......5.......4........0...2...3.1.1.
2.....3000..........4..........4.........4..............4.......5.......5...0......3.1.1..
...3..0000...............5..........5.........5..............5.......5.....3.1......1.1..2
..3.1.000.1..................4...........5........4...............5.......5.1.1......1.1..
...10.000...2....................4............5........5...............5..0..1..2.....1..2
..300.000.....2.......................5...........4........4.............20....2...3....2.
.300.100.1......2..........................5...........5........5........0.1......3...3...
.000.00.1..2......2.............................5..........4........4.....1..2.......3...3
.00.10.1..2...3......3...............................5..........5.......4...2...3.......30
.00.0.1.1....3...3.......4................................5..........5....2....3....4...00
.0.10.0...2.....3...3.........5................................5........3....3....3....300
1.10.10......3.....3...3..........4.................................5......3.....4....400.
0.0.100.........3....2.....4...........5.................................5....3.....3.000.
.1.100.1...........3....3.......5...........5................................4...3...1000.
..100.1..2.............4....4........5...........5..............................3..2.000.1
.2000...2..2...............4.....5.......4............5..........................1.0.000..
.000.1....2...3.................5.....5.......5...........4......................0.0.00.1.
2000...2....2.....4..................5.....5......4...........4...................1.10.1..
000.1....2....2........5.................4.....4.......5...........5..............0.00...2
00.1.1......3....3..........5................4......5.......5..........4...........10.1..0
0.1.1.1........3.....4..........4.................5......5.......5.........4.......0.1.1.0
.10.0...2..........4......5..........5.................5......5.......5.........5...10..10
100..1.....3............5......5..........5................4......4.......4........30.1.0.
00.1..1........4............4.......5..........5................5.....4.......4....0.1.1.1
00...2..2...........5...........4.......4...........5................5.....5.....3..10..10
0.1...1...2..............5...........5.......5...........5...............4......5.1.0.1.00
.1..2...2....3...............4............5......4............5...............5..10..1.100
1.1....3...3.....4................5............5......5............5............200..0.00.
.1.1.....2.....4......5................5............5.....4.............5.......00.1..100.
.0...2......3......4.......5................5...........4......5............4...00...200.1
1.1.....3.......4......4........5................5..........4.......5..........30.1..00.1.
.1.1........4........5......5.......4.................5.........4.......4......0.1..20.1.1
1.1..2..........4.........5......5.......5................4..........5.......5..1.1.0.10..
.1..2..2.............5.........5.....4........5...............4...........5....2.10..10.1.
..1...2...3...............5.........5.....5........5...............5..........4.10.1.0.1.1
.2..2....3....4...............4.........4......5........5...............5......10.1.1.1.1.
2..2..2......4.....5..............4..........5.....4.........5..............4..00..1.10...
..2.1....3.......4......5..............5..........5....4..........5...........20.1..10.1..
...1..2.....3........4.......5..............5.........4.....5.........4.......0.1..20.1..2
..3..2...3.....3..........5......4...............5.........5.....5.........5..0...20.1..2.
2..1...2.....4....3...........4......4...............4..........5....4......1..1..00..1...
..2.1.....3.....3....3.............5......5...............5.........4.....5..1...200...1..
..0..1.......3......4....4..............5......5...............5.........5..2..2.000....1.
2..1...2........3.......4.....5.............4.......5...............5......2..20.00.1.....
..2..2...2.........3........4.....4.............4........5...............5..1.0.10.1.1....
....2...3...3..........4.........5....4..............5........5............2.1.10.10...2..
3......3...3....4..........4.........4....4..............4.........5........1.10.100......
....4.....3....4.....5.........4........3......5.............4..........5....10.100.1.....
.........5....4.....5....4.........4.......3........5............4..........400.00.1..2...
............3.....4.....4.....5.........5.....3..........5............5.....00.10.1..2...3
...4............4.....4......5.....5........4.....4..........4.............500.0.1.1...2..
3......4.............5....4.......5.....5........5....4..........4.........000.0..1..2....
....4.......5...........3......5......4......5.......4.....5..........5....00.1.1..1...2..
3........5.......5..........4.......5.....4.......5.......5....4..........40.1.1..2.1.....
...3.........4........5..........5.......5.....5.......5......4....4......0.1.1.1..1.1....
.......4..........5........5..........5......4.....4........5.....4....4...1.1.1.1..1.1...
...........4...........5........5..........5.....4......5.......4....3....30.0..1..2.1..2.
2...............5...........5........5..........5....4.......5......4...3.00..1...2.1..2..
..2..................5...........5........5.........4.....5.......5....3.10.1..1...1.1...2
.2..2.....................5..........4........4.........4.....4.......4.10.1.1...2..1..2..
..1...2........................5..........5........5........4......5...100..1..2..1..1...2
.2..2...2...........................5..........5.......4.........5....300.1...2..2..2..2..
3..2...3...3.............................5..........5.......5.......3.00.1..2...2..2..2...
.1....3..2....3...............................5..........5.......5..0.00...2..2..1...2...3
...2...1....3.....4................................5..........5....2.10.1....2.1...2....30
1....2..1......3.......5................................5.........40.0.1..2...1.1....2..0.
.1.....2.1........3.........5................................5....0.1.1.1...2..1..2....20.
...2...0...2..........4..........5...............................4.1.1.1..2...2.1....3.0.1
.2....3.1.....3............5..........5...........................1.1.1..2...3.1..2..0..1.
2..2...1..2......3..............5.........4........................1.1..2..2.0...2..2.1...
.1...2...2...3.......4..............4..........5....................1..2.1..10....1..1..2.
...2....3...3....4.......4..............4...........5.................2.1..20.1.....2.1..1
1.....3....3....4....4........5..............5..........4.............0...200...2....1..2.
.1........4...3....3......5.......4...............5.........4..........1..000.....2....2.1
1..2........2....3.....4.......5.......5..............4.........4.......1.00.1.......3..1.
..2...3........3.....4......5......4.......4...............5........4....100...2.......2.1
1...2.....4........4......5......5......5.......5..............4........400.1.....3.....1.
.1.....3.......5........5.....4.......5......5.......5.............4....00.1..2......3...1
1..2......3.........5........5....4........5......5.......5...........3.0.1..2...3......3.
..2...3.......4..........5.......4....4.........5......5......4........1.1.1...2.....4..0.
....2.....4........5.........4.......4.....5........4.......5......5....1.1.1.....3....2.1
1.....2........5........5.........5.......5.....5........5.......5....3.0..1.1........4.1.
.1.......3.........4.........5.........5.......5.....5.......4.......4.1.1..1..2.......1.1
1.1..........4..........5.........5.........5......4.....4........5..0.0...2..2...3....0..
.1..2.............5..........5.........5........4.......5.....5.....20..1...1...2.....40..
...2...3...............5..........5........4.........5......4......50.1..1....2....3..0.1.
2.....3....4...............4...........5.......4..........5......5.0.1.1...2....2....2.1..
..2.......4....4................5...........5.......5.........4...1.10...2...2.....3..1.1.
2....3.......3......5................5...........5.......5.......3.10.1.....3...3....2.1..
..2.....3........4.......5................5...........5.......5...100...2......3....40..1.
2....3......4.........5.......5................5...........5.....3000......3.......400....
...3....3........5........4........5................5...........5000.1.........4...00.1...
.......4....4.........5........5........5................5......0000...2..........300...2.
.3.........4.....5.........5........5........5................5.000.1.....3.......000.....
.....4..........5....4..........5........5.......4............0.00.1.1.......3....00.1....
..........5.........4....4...........5........5.......5........10.10..1..........40.1..2..
3.............4.........4....4...........4.........5.......5...0.10.1...2........0.1..2...
...3...............5.......3......5...........5.........5.....30.00..1.....3......1..2...3
.2.....4................5......4......4...........4..........500.0.1..1........4....2..2..
3...3.......5...............4.......5......5..........4......00.1.1..2.1...........4..2...
..2.....4.......4................5.......5......5..........5.0.1.1..2.1..2...........2...3
1....3.......5.......5...............4.......4.......5......10.0..1..1.1...2............3.
..2......4........5.......5...............5......4........5.00..1..1..1..2....3..........1
.2...3........5........5.......5...............5.....4.....10.1..1...2.1....3....3........
...2.....4.........5........5.......5..............4......50.1..2..2..1.1.......4...3.....
......3.......5.........5........5.......5.............4..0.1..2..2..2.1..2........3....4.
...5......4........5.........5........5.......5..........20...2..2..2.1..2...3.........4..
..5.....5.....4.........5.........5........5.......5.....0.1...1...2.1.1....3....4........
......4......5....4..........5.........5........5.......50...2...2..10...2......4.....5...
.5.........5....3......5..........5.........5........5..0.1.....3..20.1.....3.......4.....
......5........4....4.......5.........4.........4.....1..1.1......20.1.1.......3........4.
..4.......4........4....4........5.........5.........5.1..1.1.....0.1.1..2.........4......
.......5.......5.......4.....5........5........4......1..20...2...0.0...2...3...........5.
..4........4........5......4......5........5.......4...1.0.1.....30..1.....3....4.........
......4.........5........5.....4.......5.......4.....2..1.1.1....0.1...2.......4....4.....
...........5........4........4......5.......5.......5..2.1.1..2..0...2....3........4....4.
...5...........4........4.........5......5.......5....20.0...2..2.1.....3....3.........4..
..5.....5...........5........5.........5.....4......3.00..1...1..1.1........4....4........
.......5.....5..........4.........5.........5....4...100....2..1..1..2..........4.....5...
.5.........4.....4..........4.........4.........4..2.000......2..2..2..2.............5....
......5.........5.....5..........5.........5......2.100.1.......2..2..2...3..............4
...4.......5........4......5..........5.........5.0.00.1..2......1...2..2.....4...........
........5......4.........5......5.........4.....0..10.1..2...3.....2...2...3.......5......
............4......4..........5.....4.........4.0..00..1....3....4....3..2.....4.......4..
..5..............5......5..........5....4.....0..1.0.1..1......3....3..1....3.......5.....
......4...............5......5.........4.....50...1.1.1..1.........4..2.1.......4........5
....5......5...............5......5.........50.1..0.0...2.1.........1..1.1...........5....
5........5......5...............5......5....0.1.1..10....1..2........1..1.1...............
.....5........5......5..............4......4.1.1.1.0.1.....2...3......1..1..2.............
.........4.........5......5.............4..0..1.1.10..1.......3...3....1...2...3..........
..............5........4.......5..........2.1..10.0.1...2........3....4..2...2.....4......
..................4.........5.......5.....0...20.1.1..2...2..........4..2...3...3.......5.
...5...................5.........5.......50...0.10...2..2....3........1....3...3....4.....
........5...................5.........5..00...0.0.1....2...3.....4......2....2.....4.....5
....5.......4....................5.....1.0.1...1.1..2.....3...3.......5....3....3......4..
..5......5.......5....................50.0..1...1.1...2......3....4.......4...3.....4.....
.......5......5......4................0.1.1..1...1.1.....3......3.....4......3....4......5
....5.......5......5......5............10...2.1...1.1.......3......3.......5.....4.....5..
.4.......5.......5......5......5.......00...0...2..1.1..........4.....3.........5....4....
.....4........5.......5......5......5..0.1..0.....2.1..2.............5....4.........4....4
....5.....5........5.......5......5...2.1.1..1.....1.1...2...............4.....5........4.
..4.....4.....4........4........5...2..10...2..2...0..1....2..................5.....5.....
......4......5....4.........5......3..200.....2...3.1..1.....2....................4......5
....5......5.....4....4..........5...200.1......2.0...2..2.....2......................4...
4........5.....4....3.....4.........300.1..2.....1.1...1....3.....3.......................
.....5........5....4...3.......5....000..1....3...1..2..1.......4.....4...................
..........5......3....3...3........400.1...2.....3.1...2.1...........5.....5..............
...............5.....4...3....4....00.1.1....2....1.1..0...2.............4.....4..........
....................5...3....4....40.1.1..2....2..0...2.1.....3...............5....4......
.......................3....4....40.1.1..2..2....2.1...1.1........4..............3......5.
...5......................3....3.0.10...2.1...2..0..1..0...2..........4..............4....
5.......5.....................40..10.1...1..2...2.1...20.....2.............5..............
....4........5................00..0.1..2...2...30...2.0.1.......3..............4..........
........4........4............0.1.0...2..2....300....1.1..2........3................5.....
............4.........5........10..1....2..2..000....0..1...2.........3..................5
....5............5.........5...0.1..1.....2.1.00.1....1..1.....3.........3................
.........5...........4........3.1..2.1.....10.0.1..2....2..2.......4.........4............
.............4............5...0...2.1..2...0.1.1..2...3..1....3........4..........5.......
..................5..........3.1..0...2...3.1.1..2..2...2..2......4.........5.........4...
.5.....................5.....0...20.....2..1.1..2..2...3..2...3.......4..........5........
.....4......................50...0.1......2.1.1..1....3..2...3...3.........5..........5...
.5........5.................00...0...2.....1.1..2..2...1....3...3...3..........4..........
......5........5............0.1...1.....3...1..2.1...2...2....2....3....4...........5.....
..........4.........5........1..2...2......3..20...2...2...2.....3....3......5..........4.
..4............5.........5....1....3...3.....200.....2....3...3.....3.....4.......5.......
.......5............5.......3...2.....3...3..00.1......2.....3...3......4......5......4...
4...........5............5.....3...3.....3.1.00...2.......3.....3....4.......5......5.....
....4............5...........4....3....4..10.00.....2.........4.....4....4........5.....4.
...5.....5............5..........4...3..1.00.0.1.......3..........4.....4.....5........5..
..5....4......5............5........3.1..10.1.1..2.........4...........5.....5.....5......
.....3......5......5...........4....0...200..1..2...3...........5...........5.....5.....5.
...5.....4......4.......5..........4.1..00.1...2...3...3............4...........4......5..
..5.....5.....5......5.......5......1..20.1..2....3...3....4.............5...........5....
5......5.....5.....5......5.......5...20.1..2...3....3....4.....5.............5...........
.....5......5.....5.....5.....4......30.1..2...3....4....4.....5....4.............4.......
..........5......5.....5....4.....4..0.1..2...3....4....4....4.....4.....5.............5..
..5............5......5....4.....5.1.0..1...2.....4....4...3......5.....5.....5...........
......4............4.....3......5.10.0...1.....3......4...3....4.......5.....5.....5......
...........5...........4.....4...10.1.1...1........4....2.....4....4........5.....5.....5.
...5............5...........5...300.0...2...2..........4...3......4.....5........5....4...
4.......5............5.........300.10......3..2...........3....4......4.....4.......3.....
....4........5............5....00.100........2...3............4.....5......5.....5.....3..
.4.......5........5...........40.100.1.........2....3..............5....4.......5....4....
.....4........5........5......0.100.1..2..........3....3...............4.....5.....3.....4
....5.....5........5........5.0.00.1..2...3...........4....4................5.....5...3...
........4......5........5....1.10.1..2...3....4...........4.....5................5...3...3
..3.........4......4........4.10.1..2...3....4.....5...........5....4...............3..2..
3.....4.........4......4.....10.1.1...2.....4.....5.....5.........3......5...........1....
....4......5.........5......50.1.1..2...2........5.....5.....5........4......4.........2..
3.......4.......5........4..00..1.1....3...3..........5....4......5........5......5.......
...3.........5.......5.....20.1.0...2.....3....4.........3......5......5........5.....4...
.5.....4..........5.......50.1.10......3......4.....5........4......4......4.........5....
5....4......5..........5..0.1.100..........4.......5.....5........5......5......5.........
...3.....4.......5.......20.0.000...............5.......5.....5........5......5.....4.....
.......4......5.......5..0.1.1000...................4........5.....5.......4.......5....4.
..4.........5......5...1..1.1000.1.......................5........5....4........5......4..
.4....4..........5...2...20.000.1..2.........................4.......3......5.......4.....
.....4.....5........3...30.100.1.1....3...........................5......4.......5.......5
....5.....5....4.......300.000..1.1.......4............................5......5.......5...
.5.......5....4.....5..00.100.1.0..1...........5............................5.....4.......
......5.....3......5.1.0.100.1.10...1..............4.............................5.....5..
.4.........5....4...1.10.00.1.10.1...1..................5.............................5...
4....4.........4..2.0.00.0.1.100...2...2.....................5............................
....4.....5.....1..1.10.1.1.1000......3...3.......................5.......................
........4.....4...20.00..10.000.1........3....4........................5..................
.............5..2.0.100..0.100.1..2..........4.....5.......................4..............
..............1.0..100.1..100.1.1....3...........4......5.......................5.........
..............0..1.00.1..200.10...2.....3.............5.....4........................5....
5..............1..10.1..200.10.1.....3......4..............5.....5........................
....4............20.1..200.10.1..2.......4.......5..............5.....5...................
.........5.......0.1..200.10.1..2..2.........4.......4...............5.....5..............
..............5...1..200.10.1..2..2...3..........4.......4................5.....5.........
.................3.1.000.0.1..2..2...3....4...........5.......5...............4......5....
5................0.0.00.1.1..2..2..2....3.....4............5......4................5......
.....5............10.00..1.1..1...2...3.....4......5............5......5................5.
...5......5.......00.00...1.1...2....3....4......5......5...........4.......5.............
........5......5..0.10.1...1..2....3....3......5.....4......4...........4........5........
.............5...2.10.1.1...1...2.....3....3........5.....5......5...........5........5...
.5..............30.0.1.1.1...1.....3......4....4.........5.....5......5...........5.......
......5.........0.1.1.10..1....2......3.......4.....5.........5.....5.....4...........4...
.5........4.....0..10.00....2.....3.......4........5....4..........5.....5....4...........
......5.......4.0..0.10.1......3......4........5.......4.....5..........5....4....4.......
..........4....1.1.0.0.1..2........4......4.........5.......5.....5........3.....4.....5..
.4............4.10..1.1.1....3..........5......5........4.......4.....4........4......5...
4....4........0.0.1..1.1..2......4...........5......5........5.......5.....5........5.....
....4....4....0..1..20...2...3.......4............5.....4........4........5.....5........5
...4...3.....4.1...20.1.....3....4........5...........4......5........5.......4......5....
......3....4..1.1..0.1..2......3......5.......4............5......5........5.......5.....4
....5.....4..2.1..20..1...2.......3........5......4.............5......5........5.......5.
...5.....5..20...200....2....3........4.........5......5.............5......5........5....
........5..20.1..00.1.....2.....3..........5.........5.....4..............5.....4........4
...4.....1.0.1..200...2.....2......3...........4.........4......5..............5.....5....
5.......5.1.1.1.00.1.....3.....3.......4...........4..........5.....4...............5.....
.....5...1.1.1.10.1..2.......4.....4.......4............5..........5.....5...............5
....5..2.0.0..100..1...2..........5....4.......4.............5.........4......5...........
......2.1.10..000....2....3..........3......5.......5............4..........5......5......
.......1.100..00.1.....2......4..........4.......5.......5...........4..........4.......5.
...5...0.00.1.0.1..2......3........5..........5.......5.......5...........5..........5....
5.....30.00.0..1.1....3......3..........5.........4........5.......5..........4...........
.....50.100..1.0...2......4.....3............5........4.........5.......5..........5......
.....0.1000...1.1.....3........5....4............4.........5.........5.......5..........5.
...5.0.000.1..0...2.......4........4....4.............5.........5.........5.......5.......
....1.100.1..2.1.....3.........5.......4....4..............5.........5........4........5..
.4...100.1..20...2.......4..........5......4.....5.............4..........5........5......
...2.00.1..20.1.....3.........5.........4.......5....4..............5..........5........5.
..4.10.1.1.0.1.1........4..........5........4......3......5..............5..........5.....
...10.1.10..10...2...........5..........5........5....3.......4...............5..........5
.2.0.10.00..00.....2..............5..........5.......4....4.......4................5......
.0..10.100..0.1.......3................5..........5......4....4........5................5.
2.1.0.100.1.0..1..........4.................5.........4.....3.....4........4..............
0..1.100.1.1.1...2.............5.................5.........5....4......5........5.........
.1..100.1.1.1..2....3...............5.................5........4....4......4.........5....
...2000..1.1..2...3....3.................5.................5......3......5......5........4
..3000.1..1.1...2.....4....4.................4..................5.....4.......5......5....
..000.1.1..1..2....3......4....4..................5..................5....4.......4......4
.2000.0...2.1...2.....3.......4.....5..................5................3.....4........5..
.000.1.1...1..2....3......4........5....4...................5...............4......5.....2
1000..1..2..1....3....3.......4........4....4....................5..............4.......5.
000.1...2..2..2......4....4........5.......4.....5....................5..............5...1
00.1.1....2.1....3.......4....4.........5......4......5....................5............30
0.10...2...1..2......4.......4.....5.........5......5......5...................4........00
.10.1.....3..2..2.........5.......5....4..........5......5......5..................4....00
10.1..2.....2..2...3..........4......3......5..........5......5......5.................40.
00..1....3....2..2.....4...........5....3........5.........4......4.......5............00.
0.1...2.....3..1...2.......4..........3....3.........4..........5......5......4........0.1
.1.1.....3....2..2....3........4..........4....4..........5..........5.....4......4.....10
.0...2.......4.1....3.....4........4..........4....4..........4...........5....4......4.00
10......3.....1..2......4......5........5.........4.....5..........5..........4.....5..10.
0.1.........4...2...3........5......5........5.........5....4...........5..........5..20.1
.1.1...........3...3....4.........5.....4.........5........4.....5...........5.......20.10
1.1..2...........2....3......5.........5....4..........5........5.....5..........4...0.10.
0...2..2............3.....4.......5.......3.....4...........5.......4......5.......2.0.0.1
.1...1....3............3......4.......4.......4......5..........4........5.....4....10..10
...2...2.....3.............4......4........5......4.......5.........4.........5....40.1.00
1....2...2.......4..............5......5........5......5.......5.........5........400..10.
..2.....3...3........4..............4......4.........5.....4........5........4....00.1.0.1
.2...3....2.....4.........5.............4......4.........4......5........5.......40.1.1.1.
....3....4..2........5.........5.............5.....4..........5.....4.........5..0.1.1.1.1
.2......4..2..2...........5.........5............4......5..........5.....5......2.1.1.1.1.
...2......2..2..2.............4..........5............5......5..........5.....5..1.1.1.1.1
.2....3....1...2...3...............5..........5............5.....4..........4..1.0.0..1.1.
...2......4..2....3....4...............4..........4.............5.....5.......2.1.10...1.1
.2....3.....2...3.....4.....5...............5..........5.............5.....5...10.0.1...1.
....3....3.....3....4......5.....5..............4..........4..............5...30.10...2..1
1......3.....4....3......5.....4.....4...............5..........5............300.0.1...1..
..2........4.....4....4.......5.....5....4................5.........4........00.1.1..2...2
1....3..........5....4.....5.......5....4.....5................5.........5...0.10...2..2..
..2......4..........4.....5.....5.....3......5....4.................5.......3.10.1....2.1.
2...2.........5..........5.....5....4.....4......4.....5.................5...10.1.1...0...
...3..2...........4..........4....3......5.....5......5....4................30.1.1.1..0...
.....2...3.............5.........4...3........5....4.....3......5...........0.1.1.1.1..1..
.......2.....4..............5.......3...3........3......5....4.......5......0..1.1.1..2.1.
2.........3......4..............4.....2.....4........4.....3.....4........5.0...1.1.1..1..
...3.........3........5..............5...3.......5........5....4......5...0..1...1.1.1..1.
2......4.........4.........5............3....4.......4.......3.....4.....3.1...2.0..1.1...
..2.........5.........5.........5...........4....4.......4.......4.....4..1.1...1.1.0...2.
.3..2...........4.........4..........5..........4....4........5.......5..2.1..2.0..1.1....
..1....3.............5.........5..........5.........4....4.........5...1..1..2.10...1..2..
....2......4.............4..........5..........5........4....4........3.1...20.00.....2..2
..3....3........5............4...........5.........4........4.....5....1..2.0.100.......2.
2.....4....4.........5...........4............5.........5.......4.....4..20..100.1........
..2.......4.....5.........5...........5............5.........5.......5..20.1.00.1..2......
.....3.........5.....5.........5...........5............5.........5....20.10.0.1..2...3...
4........4..........5.....5.........5...........5............5........40.10.10...2...3....
.....5........5.........4......5.........5..........4.............5...0.100.00......3....4