#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct list_s
{
  long val;
  struct list_s *next;
} list_t;

list_t * addelement (list_t * prev, long val)
{
  list_t * el = (list_t *) malloc (sizeof (list_t));
  el->val = val;
  el->next = NULL;
  if (prev)
    prev->next = el;
  return el;
}

list_t * populatedeck (char *line)
{
  list_t *prev = NULL;
  list_t *head = NULL;
  size_t i;
  char * dup = (char *) malloc (strlen(line) + 1);
  strcpy(dup, line);
  char *tok = strtok (dup, " ");
  while (tok)
    {
      prev = addelement (prev, strtol (tok, NULL, 0));
      if (!head)
	head = prev;
      tok = strtok (NULL, " ");
    }
  return head;
}

void freelist (list_t * head)
{
  list_t *current = head;
  list_t *next = NULL;
  while (current)
    {
      next = current->next;
      free (current);
      current = next;
    }

}

list_t * findtail (list_t * head)
{
  list_t *current = head;
  while (current && current->next) current = current->next;
  return current;
}

list_t * addtwo(list_t * l, list_t * r) {
  if (!l) return r;
  (findtail(l)->next) = r;
  return l;
}

int warmove (list_t ** player1, list_t ** player2)
{
  if (!(*player1) && !(*player2)) return -1;
  if (!(*player1)) return 2;
  if (!(*player2)) return 1;

  list_t *whead1 = *player1;
  list_t *whead2 = *player2;

  list_t *current1 = whead1;
  list_t *current2 = whead2;

  int i;
  for (i = 0; i < 3; i++) {
    if (!(current1->next) || !(current2->next)) break;
    current1 = current1->next;
    current2 = current2->next;
  }

  (*player1) = current1->next;
  (*player2) = current2->next;
  
  current1->next = NULL;
  current2->next = NULL;


  int winner;
  if (current1->val > current2->val) {winner = 1; }
  else if (current1->val < current2->val) { winner = 2; }
  else {
    winner = warmove (player1, player2);
    if (winner == -1) return -1;
  }
  
  if (winner == 1) *player1 = addtwo(*player1, addtwo(whead1, whead2));
  if (winner == 2) *player2 = addtwo(*player2, addtwo(whead2, whead1));
  

  return winner;
}

int normalmove (list_t ** player1, list_t ** player2)
{

  list_t *card1 = *player1;
  (*player1) = (*player1)->next;
  card1->next = NULL;

  list_t *card2 = *player2;
  (*player2) = (*player2)->next;
  card2->next = NULL;

  int winner;
  if (card1->val > card2->val) { winner = 1; }
  else if (card1->val < card2->val) { winner = 2; }
  else {
    winner = warmove (player1, player2);
    if (winner == -1) return 1;
  }


  if ( winner == 1 ) {
    *player1 = addtwo(*player1, addtwo(card1, card2));
  }
  if ( winner == 2 ) {
    *player2 = addtwo(*player2, addtwo(card2, card1));
  }
}

void game (char *player1, char *player2)
{

  list_t *deck1 = populatedeck (player1);
  list_t *deck2 = populatedeck (player2);

  while (1) {
    int checktie = normalmove (&deck1, &deck2);
    if (checktie == 1) { printf ("0\n"); break; }
    if (!deck1) { printf ("2\n"); break; }
    if (!deck2) { printf ("1\n"); break; }
  }

  freelist (deck1);
  freelist (deck2);
}

int main (int argv, char *argc[])
{
  char *chal[] =
  { "5 1 13 10 11 3 2 10 4 12 5 11 10 5 7 6 6 11 9 6 3 13 6 1 8 1",
    "9 12 8 3 11 10 1 4 2 4 7 9 13 8 2 13 7 4 2 8 9 12 3 12 7 5",
    "3 11 6 12 2 13 5 7 10 3 10 4 12 11 1 13 12 2 1 7 10 6 12 5 8 1",
    "9 10 7 9 5 2 6 1 11 11 7 9 3 4 8 3 4 8 8 4 6 9 13 2 13 5",
    "1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13",
    "1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13"
  };

  size_t i;
  for (i = 0; i < 3; i++) game(chal[2 * i], chal[2 * i + 1]);
}