Tehtäväsi on kehittää menetelmä binääripuiden numerointiin. Sinulle annetaan 9-solmuisen binääripuun kuvaus ja sinun tulee antaa sille tunnusnumero väliltä 1 \ldots k.

Tunnusnumero tulee antaa niin, että se yksilöi puun rakenteen. Jos kahden puun rakenne on sama, niillä tulee olla sama tunnusnumero, ja muuten niillä tulee olla eri tunnusnumero.

Huomaa, että puun rakenteeseen vaikuttaa, kummalla puolella solmun lapsi on. Esimerkiksi seuraavien puiden rakenne ei ole sama:

  o    o
 /      \
o        o

Syöte

Syötteenä on 18 lukua, jotka kuvaavat binääripuun solmut 1,2,\ldots,9. Binääripuun juurisolmu on solmu 1.

Jokaisesta solmusta ilmoitetaan sen vasemman ja oikean lapsen tunnus. Jos lapsi puuttuu, niin sen tilalla on luku 0.

Tuloste

Ohjelmasi tulee tulostaa binääripuun tunnusnumero.

Arvostelu

Toisin kuin yleensä, jokaisessa testitapauksessa ohjelmasi suoritetaan useita kertoja (enintään 100 kertaa) eri syötteillä. Tämän jälkeen arvostelija kokoaa yhteen kaikki ohjelman tuottamat tunnusnumerot ja tarkastaa, että ne ovat keskenään yhteensopivat.

Esimerkki

Syöte:

2 3 0 0 0 4 5 6 7 0 8 0 0 9 0 0 0 0

Tuloste:

352

Tämä vastaa seuraavaa binääripuuta:

  o
 / \
o   o
     \
      o
     / \
    o   o
   /   /
  o   o
   \
    o

Huomaa, että solmujen tunnuksilla ei ole merkitystä, vaan vain puun rakenne vaikuttaa numerointiin.

Osatehtävä 1 (14 pistettä)

• 1 \le k \le 10^9

Osatehtävä 2 (15 pistettä)

• 1 \le k \le 10^6

Osatehtävä 3 (71 pistettä)

• 1 \le k \le 5000