/*
 *  Program k řešení úlohy 27-3-1 -- Plocha k přistání
 *
 *  Používáme algoritmus popsaný ve vzorovém řešení, založený na DFS.
 *
 *  Na okraj poznamenejme, že kód by nebylo potřeba převádět na strom.
 *  Následující funkce by mohla běžet přímo při načítání vstupu,
 *  neboť kód na vstupu je přesným popisem průchodu stromem do hloubky.
 *  Museli bychom ovšem počítat řády čtverců opačně (čím menší čtverec,
 *  tím vyšší řád), protože předem neznáme hloubku stromu. Proto raději
 *  volíme postup sice pracnější, ale průhlednější.
 *
 *  Předpokládáme, že plocha obrázku se vejde do uint64_t.
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>

/*** Kvadrantový strom ***/

struct tree_node {
  int color;					// Barva: 0=bílá, 1=černá, -1=vícebarevný
  struct tree_node *sons[4];			// Synové vrcholu
};

// Přečteme kód ze vstupu a vybudujeme jeho strom
struct tree_node *build_tree(void)
{
  struct tree_node *t = malloc(sizeof(*t));
  int c = getchar();
  if (c == '0' || c == '1')
    t->color = c - '0';
  else
    {
      t->color = -1;
      for (int i=0; i<4; i++)
	t->sons[i] = build_tree();
      if (getchar() != ')')
	abort();
    }
  return t;
}

// Výpočet hloubky stromu
int tree_depth(struct tree_node *t)
{
  if (t->color >= 0)
    return 0;
  else
    {
      int d = 0;
      for (int i=0; i<4; i++)
	{
	  int sd = tree_depth(t->sons[i]);
	  if (sd > d)
	    d = sd;
	}
      return d + 1;
    }
}

// Ladící výpis stromu
void debug_tree(struct tree_node *t, int indent)
{
  if (t->color >= 0)
    printf("%-20p%*s%d\n", t, indent, "", t->color);
  else
    {
      printf("%-20p%*s(\n", t, indent, "");
      for (int i=0; i<4; i++)
	debug_tree(t->sons[i], indent + 4);
      printf("%-20p%*s)\n", t, indent, "");
    }
}

/*** Čtverce a jejich hranice ***/

// Pro každou hranici čtverce si pamatujeme seznam intervalů.
// Situaci značně zjednoduší, že seznam nikdy není prázdný.
struct list {
  struct interval *first, *last;		// První a poslední interval v seznamu
};

struct interval {
  struct interval *next;			// Další interval v seznamu
  int order;					// Řád intervalu
  struct vertex *vertex;			// Vrchol grafu
};

struct square {
  struct list l, r, u, d;			// Levá, pravá, horní a dolní hranice
};

/*** Graf ***/

// Vrchol grafu
struct vertex {
  struct edge *first_edge;			// Začátek seznamu hran
  int order;					// Řád čtverce
  int color;					// Barva čtverce
  int seen;					// Už jsme tu při prohledávání grafu byli
  struct tree_node *tree_node;			// Odkaz na vrchol stromu (pomáhá při debugování)
};

// Hrana grafu
struct edge {
  struct edge *next;				// Další v pořadí
  struct vertex *dest;				// Cílový vrchol
};

#define MAXV 10000
int numv;					// Počet vrcholů
struct vertex vertices[MAXV];			// Vrcholy

/*** Pomocné funkce ***/

// Vytvoření triviálního seznamu s jedním intervalem
void triv_list(struct list *l, struct vertex *v)
{
  struct interval *i = malloc(sizeof(*i));
  i->next = NULL;
  i->order = v->order;
  i->vertex = v;
  l->first = l->last = i;
}

// Vytvoření seznamu slepením dvou seznamů
void concat_lists(struct list *dest, struct list *a, struct list *b)
{
  dest->first = a->first;
  a->last->next = b->first;
  dest->last = b->last;
}

// Přidání hrany do grafu
void add_edge(struct vertex *u, struct vertex *v)
{
  struct edge *e = malloc(sizeof(*e));
  e->dest = v;
  e->next = u->first_edge;
  u->first_edge = e;
}

// Propojení dvou hranic
void connect(struct list *a, struct list *b)
{
  while (a->first)
    {
      // Odpojíme větší z počátečních intervalů (případně prohodíme seznamy)
      if (a->first->order < b->first->order)
	{
	  struct list *c = a;
	  a = b;
	  b = c;
	}
      struct interval *ai = a->first;
      a->first = ai->next;

      // Z druhého seznamu odpojujeme intervaly, které se překrývají s ai
      uint64_t rest = (uint64_t) 1 << ai->order;
      while (rest)
	{
	  struct interval *bi = b->first;
	  b->first = bi->next;
	  add_edge(ai->vertex, bi->vertex);
	  add_edge(bi->vertex, ai->vertex);
	  rest -= (uint64_t) 1 << bi->order;
	}
    }
}

// Ladicí výpis hranic čtverce

void debug_list(struct list *l)
{
  for (struct interval *i = l->first; i; i = i->next)
    printf("[%d %d] ", i->vertex - vertices, i->order);
  puts("");
}

void debug_square(struct tree_node *t, struct square *s, int order)
{
  printf("Square %p (tree node %p, order %d)\n", s, t, order);
  printf("\tL = "); debug_list(&s->l);
  printf("\tR = "); debug_list(&s->r);
  printf("\tU = "); debug_list(&s->u);
  printf("\tD = "); debug_list(&s->d);
}

// Ladicí výpis grafu

void debug_graph(void)
{
  for (int i=0; i<numv; i++)
    {
      struct vertex *v = &vertices[i];
      printf("Vertex %d (order %d, color %d, tree node %p)\n\t->", i, v->order, v->color, v->tree_node);
      for (struct edge *e = v->first_edge; e; e = e->next)
	printf(" %d", e->dest - vertices);
      puts("");
    }
}

/*** Budování grafu průchodem kvadrantového stromu do hloubky ***/

struct square *build_graph(int order, struct tree_node *t)
{
  struct square *s = malloc(sizeof(*s));
  if (t->color >= 0)
    {
      // Jednobarevný čtverec: založíme vrchol grafu
      struct vertex *v = &vertices[numv++];
      v->order = order;
      v->color = t->color;
      v->tree_node = t;

      // Všechny 4 hranice budou triviální
      triv_list(&s->l, v);
      triv_list(&s->r, v);
      triv_list(&s->u, v);
      triv_list(&s->d, v);
    }
  else
    {
      // Vícebarevný čtverec: rekurze na kvadranty
      struct square *q[4];
      for (int i=0; i<4; i++)
	q[i] = build_graph(order-1, t->sons[i]);

      // Vnější hranice slepíme
      concat_lists(&s->l, &q[0]->l, &q[2]->l);
      concat_lists(&s->r, &q[1]->r, &q[3]->r);
      concat_lists(&s->u, &q[0]->u, &q[1]->u);
      concat_lists(&s->d, &q[2]->d, &q[3]->d);

      // Vnitřní hranice propojíme
      connect(&q[0]->r, &q[1]->l);
      connect(&q[2]->r, &q[3]->l);
      connect(&q[0]->d, &q[2]->u);
      connect(&q[1]->d, &q[3]->u);
    }

  debug_square(t, s, order);
  return s;
}

/*** Průchod grafem do hloubky s hledáním největší bílé komponenty ***/

uint64_t component_size(struct vertex *v)
{
  if (v->seen || v->color)
    return 0;
  v->seen = 1;

  uint64_t comp = (uint64_t) 1 << (2*v->order);
  for (struct edge *e = v->first_edge; e; e = e->next)
    comp += component_size(e->dest);
  return comp;
}

uint64_t max_component(void)
{
  uint64_t max = 0;
  for (int i=0; i<numv; i++)
    {
      uint64_t comp = component_size(&vertices[i]);
      if (comp > max)
	max = comp;
    }
  return max;
}

int main(void)
{
  struct tree_node *tree = build_tree();
  debug_tree(tree, 0);

  int depth = tree_depth(tree);
  printf("Tree depth: %d\n\n", depth);

  build_graph(depth, tree);
  debug_graph();

  uint64_t max = max_component();
  printf("%" PRIu64 "\n", max);
  return 0;
}