const int edges[107] = {
	0, /* 1-based */
	/*   1 */ 17,
	/*   2 */ 16,
	/*   3 */ 0,
	/*   4 */ 1,
	/*   5 */ 16,
	/*   6 */ 0,
	/*   7 */ 0,
	/*   8 */ 0,
	/*   9 */ 1,
	/*  10 */ 16,
	/*  11 */ 0,
	/*  12 */ 0,
	/*  13 */ 0,
	/*  14 */ 0,
	/*  15 */ 0,
	/*  16 */ 1,
	/*  17 */ 16,
	/*  18 */ 0,
	/*  19 */ 0,
	/*  20 */ 0,
	/*  21 */ 0,
	/*  22 */ 0,
	/*  23 */ 0,
	/*  24 */ 0,
	/*  25 */ 1,
	/*  26 */ 16,
	/*  27 */ 0,
	/*  28 */ 0,
	/*  29 */ 0,
	/*  30 */ 0,
	/*  31 */ 0,
	/*  32 */ 0,
	/*  33 */ 0,
	/*  34 */ 0,
	/*  35 */ 0,
	/*  36 */ 1,
	/*  37 */ 24,
	/*  38 */ 0,
	/*  39 */ 0,
	/*  40 */ 0,
	/*  41 */ 0,
	/*  42 */ 0,
	/*  43 */ 0,
	/*  44 */ 0,
	/*  45 */ 0,
	/*  46 */ 0,
	/*  47 */ 0,
	/*  48 */ 0,
	/*  49 */ 3,
	/*  50 */ 8,
	/*  51 */ 0,
	/*  52 */ 0,
	/*  53 */ 0,
	/*  54 */ 0,
	/*  55 */ 0,
	/*  56 */ 0,
	/*  57 */ 0,
	/*  58 */ 0,
	/*  59 */ 0,
	/*  60 */ 0,
	/*  61 */ 2,
	/*  62 */ 8,
	/*  63 */ 0,
	/*  64 */ 0,
	/*  65 */ 0,
	/*  66 */ 0,
	/*  67 */ 0,
	/*  68 */ 0,
	/*  69 */ 0,
	/*  70 */ 0,
	/*  71 */ 0,
	/*  72 */ 2,
	/*  73 */ 8,
	/*  74 */ 0,
	/*  75 */ 0,
	/*  76 */ 0,
	/*  77 */ 0,
	/*  78 */ 0,
	/*  79 */ 0,
	/*  80 */ 0,
	/*  81 */ 0,
	/*  82 */ 2,
	/*  83 */ 8,
	/*  84 */ 0,
	/*  85 */ 0,
	/*  86 */ 0,
	/*  87 */ 0,
	/*  88 */ 0,
	/*  89 */ 0,
	/*  90 */ 0,
	/*  91 */ 2,
	/*  92 */ 8,
	/*  93 */ 0,
	/*  94 */ 0,
	/*  95 */ 0,
	/*  96 */ 0,
	/*  97 */ 0,
	/*  98 */ 0,
	/*  99 */ 2,
	/* 100 */ 12,
	/* 101 */ 4,
	/* 102 */ 4,
	/* 103 */ 4,
	/* 104 */ 4,
	/* 105 */ 4,
	/* 106 */ 6,
};
const int rowsize[] = {1, 3, 5, 7, 9, 11, 13, 12, 11, 10, 9, 8, 7, 0};
const int edge_cells[] = {1, 2, 4, 5, 9, 10, 16, 17, 25, 26, 36, 37, 49, 50, 61, 62, 72, 73, 82, 83, 91, 92, 99, 100, 101, 102, 103, 104, 105, 106, 0};
const int corner_cells[] = {1, 37, 49, 100, 106, 0};
const int neighs[107][6] = {
	{}, /* 1-based */
	/*   1 */ {  2,  3,  4},
	/*   2 */ {  1,  3,  5,  6},
	/*   3 */ {  1,  2,  4,  6,  7,  8},
	/*   4 */ {  1,  3,  8,  9},
	/*   5 */ {  2,  6, 10, 11},
	/*   6 */ {  2,  3,  5,  7, 11, 12},
	/*   7 */ {  3,  6,  8, 12, 13, 14},
	/*   8 */ {  3,  4,  7,  9, 14, 15},
	/*   9 */ {  4,  8, 15, 16},
	/*  10 */ {  5, 11, 17, 18},
	/*  11 */ {  5,  6, 10, 12, 18, 19},
	/*  12 */ {  6,  7, 11, 13, 19, 20},
	/*  13 */ {  7, 12, 14, 20, 21, 22},
	/*  14 */ {  7,  8, 13, 15, 22, 23},
	/*  15 */ {  8,  9, 14, 16, 23, 24},
	/*  16 */ {  9, 15, 24, 25},
	/*  17 */ { 10, 18, 26, 27},
	/*  18 */ { 10, 11, 17, 19, 27, 28},
	/*  19 */ { 11, 12, 18, 20, 28, 29},
	/*  20 */ { 12, 13, 19, 21, 29, 30},
	/*  21 */ { 13, 20, 22, 30, 31, 32},
	/*  22 */ { 13, 14, 21, 23, 32, 33},
	/*  23 */ { 14, 15, 22, 24, 33, 34},
	/*  24 */ { 15, 16, 23, 25, 34, 35},
	/*  25 */ { 16, 24, 35, 36},
	/*  26 */ { 17, 27, 37, 38},
	/*  27 */ { 17, 18, 26, 28, 38, 39},
	/*  28 */ { 18, 19, 27, 29, 39, 40},
	/*  29 */ { 19, 20, 28, 30, 40, 41},
	/*  30 */ { 20, 21, 29, 31, 41, 42},
	/*  31 */ { 21, 30, 32, 42, 43, 44},
	/*  32 */ { 21, 22, 31, 33, 44, 45},
	/*  33 */ { 22, 23, 32, 34, 45, 46},
	/*  34 */ { 23, 24, 33, 35, 46, 47},
	/*  35 */ { 24, 25, 34, 36, 47, 48},
	/*  36 */ { 25, 35, 48, 49},
	/*  37 */ { 26, 38, 50},
	/*  38 */ { 26, 27, 37, 39, 50, 51},
	/*  39 */ { 27, 28, 38, 40, 51, 52},
	/*  40 */ { 28, 29, 39, 41, 52, 53},
	/*  41 */ { 29, 30, 40, 42, 53, 54},
	/*  42 */ { 30, 31, 41, 43, 54, 55},
	/*  43 */ { 31, 42, 44, 55, 56},
	/*  44 */ { 31, 32, 43, 45, 56, 57},
	/*  45 */ { 32, 33, 44, 46, 57, 58},
	/*  46 */ { 33, 34, 45, 47, 58, 59},
	/*  47 */ { 34, 35, 46, 48, 59, 60},
	/*  48 */ { 35, 36, 47, 49, 60, 61},
	/*  49 */ { 36, 48, 61},
	/*  50 */ { 37, 38, 51, 62},
	/*  51 */ { 38, 39, 50, 52, 62, 63},
	/*  52 */ { 39, 40, 51, 53, 63, 64},
	/*  53 */ { 40, 41, 52, 54, 64, 65},
	/*  54 */ { 41, 42, 53, 55, 65, 66},
	/*  55 */ { 42, 43, 54, 56, 66, 67},
	/*  56 */ { 43, 44, 55, 57, 67, 68},
	/*  57 */ { 44, 45, 56, 58, 68, 69},
	/*  58 */ { 45, 46, 57, 59, 69, 70},
	/*  59 */ { 46, 47, 58, 60, 70, 71},
	/*  60 */ { 47, 48, 59, 61, 71, 72},
	/*  61 */ { 48, 49, 60, 72},
	/*  62 */ { 50, 51, 63, 73},
	/*  63 */ { 51, 52, 62, 64, 73, 74},
	/*  64 */ { 52, 53, 63, 65, 74, 75},
	/*  65 */ { 53, 54, 64, 66, 75, 76},
	/*  66 */ { 54, 55, 65, 67, 76, 77},
	/*  67 */ { 55, 56, 66, 68, 77, 78},
	/*  68 */ { 56, 57, 67, 69, 78, 79},
	/*  69 */ { 57, 58, 68, 70, 79, 80},
	/*  70 */ { 58, 59, 69, 71, 80, 81},
	/*  71 */ { 59, 60, 70, 72, 81, 82},
	/*  72 */ { 60, 61, 71, 82},
	/*  73 */ { 62, 63, 74, 83},
	/*  74 */ { 63, 64, 73, 75, 83, 84},
	/*  75 */ { 64, 65, 74, 76, 84, 85},
	/*  76 */ { 65, 66, 75, 77, 85, 86},
	/*  77 */ { 66, 67, 76, 78, 86, 87},
	/*  78 */ { 67, 68, 77, 79, 87, 88},
	/*  79 */ { 68, 69, 78, 80, 88, 89},
	/*  80 */ { 69, 70, 79, 81, 89, 90},
	/*  81 */ { 70, 71, 80, 82, 90, 91},
	/*  82 */ { 71, 72, 81, 91},
	/*  83 */ { 73, 74, 84, 92},
	/*  84 */ { 74, 75, 83, 85, 92, 93},
	/*  85 */ { 75, 76, 84, 86, 93, 94},
	/*  86 */ { 76, 77, 85, 87, 94, 95},
	/*  87 */ { 77, 78, 86, 88, 95, 96},
	/*  88 */ { 78, 79, 87, 89, 96, 97},
	/*  89 */ { 79, 80, 88, 90, 97, 98},
	/*  90 */ { 80, 81, 89, 91, 98, 99},
	/*  91 */ { 81, 82, 90, 99},
	/*  92 */ { 83, 84, 93,100},
	/*  93 */ { 84, 85, 92, 94,100,101},
	/*  94 */ { 85, 86, 93, 95,101,102},
	/*  95 */ { 86, 87, 94, 96,102,103},
	/*  96 */ { 87, 88, 95, 97,103,104},
	/*  97 */ { 88, 89, 96, 98,104,105},
	/*  98 */ { 89, 90, 97, 99,105,106},
	/*  99 */ { 90, 91, 98,106},
	/* 100 */ { 92, 93,101},
	/* 101 */ { 93, 94,100,102},
	/* 102 */ { 94, 95,101,103},
	/* 103 */ { 95, 96,102,104},
	/* 104 */ { 96, 97,103,105},
	/* 105 */ { 97, 98,104,106},
	/* 106 */ { 98, 99,105},
};
const int common_neighs[107][6][3] = {
	{}, /* 1-based */
	/*   1 */ {{  6,  2,  3}, {  8,  3,  4}},
	/*   2 */ {{  4,  1,  3}, {  7,  3,  6}, { 11,  5,  6}},
	/*   3 */ {{  5,  2,  6}, {  9,  8,  4}, { 12,  6,  7}, { 14,  8,  7}},
	/*   4 */ {{  2,  1,  3}, {  7,  8,  3}, { 15,  8,  9}},
	/*   5 */ {{  3,  2,  6}, { 12, 11,  6}, { 18, 10, 11}},
	/*   6 */ {{  1,  2,  3}, {  8,  3,  7}, { 10, 11,  5}, { 13, 12,  7}, { 19, 11, 12}},
	/*   7 */ {{  2,  3,  6}, {  4,  8,  3}, { 11, 12,  6}, { 15,  8, 14}, { 20, 12, 13}, { 22, 13, 14}},
	/*   8 */ {{  1,  3,  4}, {  6,  3,  7}, { 13, 14,  7}, { 16,  9, 15}, { 23, 14, 15}},
	/*   9 */ {{  3,  8,  4}, { 14,  8, 15}, { 24, 16, 15}},
	/*  10 */ {{  6, 11,  5}, { 19, 18, 11}, { 27, 17, 18}},
	/*  11 */ {{  2,  5,  6}, {  7, 12,  6}, { 17, 18, 10}, { 20, 19, 12}, { 28, 18, 19}},
	/*  12 */ {{  3,  6,  7}, {  5, 11,  6}, { 14, 13,  7}, { 18, 19, 11}, { 21, 20, 13}, { 29, 19, 20}},
	/*  13 */ {{  6, 12,  7}, {  8, 14,  7}, { 19, 20, 12}, { 23, 22, 14}, { 30, 20, 21}, { 32, 21, 22}},
	/*  14 */ {{  3,  8,  7}, {  9,  8, 15}, { 12, 13,  7}, { 21, 13, 22}, { 24, 23, 15}, { 33, 22, 23}},
	/*  15 */ {{  4,  8,  9}, {  7,  8, 14}, { 22, 14, 23}, { 25, 24, 16}, { 34, 24, 23}},
	/*  16 */ {{  8,  9, 15}, { 23, 24, 15}, { 35, 24, 25}},
	/*  17 */ {{ 11, 18, 10}, { 28, 18, 27}, { 38, 26, 27}},
	/*  18 */ {{  5, 10, 11}, { 12, 19, 11}, { 26, 17, 27}, { 29, 19, 28}, { 39, 27, 28}},
	/*  19 */ {{  6, 11, 12}, { 10, 18, 11}, { 13, 20, 12}, { 27, 18, 28}, { 30, 20, 29}, { 40, 28, 29}},
	/*  20 */ {{  7, 12, 13}, { 11, 19, 12}, { 22, 13, 21}, { 28, 19, 29}, { 31, 21, 30}, { 41, 29, 30}},
	/*  21 */ {{ 12, 20, 13}, { 14, 13, 22}, { 29, 20, 30}, { 33, 32, 22}, { 42, 30, 31}, { 44, 32, 31}},
	/*  22 */ {{  7, 13, 14}, { 15, 14, 23}, { 20, 13, 21}, { 31, 32, 21}, { 34, 33, 23}, { 45, 32, 33}},
	/*  23 */ {{  8, 14, 15}, { 13, 22, 14}, { 16, 24, 15}, { 32, 33, 22}, { 35, 24, 34}, { 46, 33, 34}},
	/*  24 */ {{  9, 16, 15}, { 14, 23, 15}, { 33, 34, 23}, { 36, 25, 35}, { 47, 34, 35}},
	/*  25 */ {{ 15, 24, 16}, { 34, 24, 35}, { 48, 35, 36}},
	/*  26 */ {{ 18, 17, 27}, { 39, 27, 38}, { 50, 37, 38}},
	/*  27 */ {{ 10, 17, 18}, { 19, 18, 28}, { 37, 26, 38}, { 40, 28, 39}, { 51, 38, 39}},
	/*  28 */ {{ 11, 18, 19}, { 17, 18, 27}, { 20, 19, 29}, { 38, 27, 39}, { 41, 40, 29}, { 52, 40, 39}},
	/*  29 */ {{ 12, 19, 20}, { 18, 19, 28}, { 21, 20, 30}, { 39, 40, 28}, { 42, 41, 30}, { 53, 40, 41}},
	/*  30 */ {{ 13, 20, 21}, { 19, 20, 29}, { 32, 21, 31}, { 40, 41, 29}, { 43, 42, 31}, { 54, 41, 42}},
	/*  31 */ {{ 20, 21, 30}, { 22, 32, 21}, { 41, 42, 30}, { 45, 32, 44}, { 55, 42, 43}, { 56, 43, 44}},
	/*  32 */ {{ 13, 21, 22}, { 23, 33, 22}, { 30, 21, 31}, { 43, 44, 31}, { 46, 33, 45}, { 57, 44, 45}},
	/*  33 */ {{ 14, 22, 23}, { 21, 32, 22}, { 24, 34, 23}, { 44, 32, 45}, { 47, 34, 46}, { 58, 45, 46}},
	/*  34 */ {{ 15, 24, 23}, { 22, 33, 23}, { 25, 24, 35}, { 45, 33, 46}, { 48, 35, 47}, { 59, 46, 47}},
	/*  35 */ {{ 16, 24, 25}, { 23, 24, 34}, { 46, 34, 47}, { 49, 48, 36}, { 60, 48, 47}},
	/*  36 */ {{ 24, 25, 35}, { 47, 48, 35}, { 61, 48, 49}},
	/*  37 */ {{ 27, 26, 38}, { 51, 50, 38}},
	/*  38 */ {{ 17, 26, 27}, { 28, 27, 39}, { 52, 51, 39}, { 62, 50, 51}},
	/*  39 */ {{ 18, 27, 28}, { 26, 27, 38}, { 29, 40, 28}, { 50, 51, 38}, { 53, 40, 52}, { 63, 51, 52}},
	/*  40 */ {{ 19, 28, 29}, { 27, 28, 39}, { 30, 41, 29}, { 51, 52, 39}, { 54, 41, 53}, { 64, 52, 53}},
	/*  41 */ {{ 20, 29, 30}, { 28, 40, 29}, { 31, 42, 30}, { 52, 40, 53}, { 55, 42, 54}, { 65, 53, 54}},
	/*  42 */ {{ 21, 30, 31}, { 29, 41, 30}, { 44, 43, 31}, { 53, 41, 54}, { 56, 43, 55}, { 66, 54, 55}},
	/*  43 */ {{ 30, 42, 31}, { 32, 44, 31}, { 54, 42, 55}, { 57, 56, 44}, { 67, 56, 55}},
	/*  44 */ {{ 21, 32, 31}, { 33, 32, 45}, { 42, 43, 31}, { 55, 56, 43}, { 58, 57, 45}, { 68, 56, 57}},
	/*  45 */ {{ 22, 32, 33}, { 31, 32, 44}, { 34, 33, 46}, { 56, 57, 44}, { 59, 58, 46}, { 69, 57, 58}},
	/*  46 */ {{ 23, 33, 34}, { 32, 33, 45}, { 35, 34, 47}, { 57, 58, 45}, { 60, 59, 47}, { 70, 58, 59}},
	/*  47 */ {{ 24, 34, 35}, { 33, 34, 46}, { 36, 48, 35}, { 58, 59, 46}, { 61, 48, 60}, { 71, 59, 60}},
	/*  48 */ {{ 25, 35, 36}, { 34, 35, 47}, { 59, 60, 47}, { 72, 60, 61}},
	/*  49 */ {{ 35, 48, 36}, { 60, 48, 61}},
	/*  50 */ {{ 26, 37, 38}, { 39, 51, 38}, { 63, 51, 62}},
	/*  51 */ {{ 27, 38, 39}, { 37, 50, 38}, { 40, 52, 39}, { 64, 52, 63}, { 73, 62, 63}},
	/*  52 */ {{ 28, 40, 39}, { 38, 51, 39}, { 41, 40, 53}, { 62, 51, 63}, { 65, 64, 53}, { 74, 64, 63}},
	/*  53 */ {{ 29, 40, 41}, { 39, 40, 52}, { 42, 41, 54}, { 63, 64, 52}, { 66, 65, 54}, { 75, 64, 65}},
	/*  54 */ {{ 30, 41, 42}, { 40, 41, 53}, { 43, 42, 55}, { 64, 65, 53}, { 67, 66, 55}, { 76, 65, 66}},
	/*  55 */ {{ 31, 42, 43}, { 41, 42, 54}, { 44, 56, 43}, { 65, 66, 54}, { 68, 56, 67}, { 77, 66, 67}},
	/*  56 */ {{ 31, 43, 44}, { 42, 43, 55}, { 45, 57, 44}, { 66, 67, 55}, { 69, 57, 68}, { 78, 67, 68}},
	/*  57 */ {{ 32, 44, 45}, { 43, 56, 44}, { 46, 58, 45}, { 67, 56, 68}, { 70, 58, 69}, { 79, 68, 69}},
	/*  58 */ {{ 33, 45, 46}, { 44, 57, 45}, { 47, 59, 46}, { 68, 57, 69}, { 71, 59, 70}, { 80, 69, 70}},
	/*  59 */ {{ 34, 46, 47}, { 45, 58, 46}, { 48, 60, 47}, { 69, 58, 70}, { 72, 60, 71}, { 81, 70, 71}},
	/*  60 */ {{ 35, 48, 47}, { 46, 59, 47}, { 49, 48, 61}, { 70, 59, 71}, { 82, 72, 71}},
	/*  61 */ {{ 36, 48, 49}, { 47, 48, 60}, { 71, 72, 60}},
	/*  62 */ {{ 38, 50, 51}, { 52, 51, 63}, { 74, 73, 63}},
	/*  63 */ {{ 39, 51, 52}, { 50, 51, 62}, { 53, 64, 52}, { 75, 64, 74}, { 83, 73, 74}},
	/*  64 */ {{ 40, 52, 53}, { 51, 52, 63}, { 54, 65, 53}, { 73, 74, 63}, { 76, 65, 75}, { 84, 74, 75}},
	/*  65 */ {{ 41, 53, 54}, { 52, 64, 53}, { 55, 66, 54}, { 74, 64, 75}, { 77, 66, 76}, { 85, 75, 76}},
	/*  66 */ {{ 42, 54, 55}, { 53, 65, 54}, { 56, 67, 55}, { 75, 65, 76}, { 78, 67, 77}, { 86, 76, 77}},
	/*  67 */ {{ 43, 56, 55}, { 54, 66, 55}, { 57, 56, 68}, { 76, 66, 77}, { 79, 68, 78}, { 87, 77, 78}},
	/*  68 */ {{ 44, 56, 57}, { 55, 56, 67}, { 58, 57, 69}, { 77, 67, 78}, { 80, 69, 79}, { 88, 78, 79}},
	/*  69 */ {{ 45, 57, 58}, { 56, 57, 68}, { 59, 58, 70}, { 78, 68, 79}, { 81, 80, 70}, { 89, 80, 79}},
	/*  70 */ {{ 46, 58, 59}, { 57, 58, 69}, { 60, 59, 71}, { 79, 80, 69}, { 82, 81, 71}, { 90, 80, 81}},
	/*  71 */ {{ 47, 59, 60}, { 58, 59, 70}, { 61, 72, 60}, { 80, 81, 70}, { 91, 81, 82}},
	/*  72 */ {{ 48, 60, 61}, { 59, 60, 71}, { 81, 82, 71}},
	/*  73 */ {{ 51, 62, 63}, { 64, 74, 63}, { 84, 74, 83}},
	/*  74 */ {{ 52, 64, 63}, { 62, 73, 63}, { 65, 64, 75}, { 85, 75, 84}, { 92, 83, 84}},
	/*  75 */ {{ 53, 64, 65}, { 63, 64, 74}, { 66, 65, 76}, { 83, 74, 84}, { 86, 76, 85}, { 93, 84, 85}},
	/*  76 */ {{ 54, 65, 66}, { 64, 65, 75}, { 67, 66, 77}, { 84, 75, 85}, { 87, 77, 86}, { 94, 85, 86}},
	/*  77 */ {{ 55, 66, 67}, { 65, 66, 76}, { 68, 67, 78}, { 85, 76, 86}, { 88, 78, 87}, { 95, 86, 87}},
	/*  78 */ {{ 56, 67, 68}, { 66, 67, 77}, { 69, 68, 79}, { 86, 77, 87}, { 89, 88, 79}, { 96, 88, 87}},
	/*  79 */ {{ 57, 68, 69}, { 67, 68, 78}, { 70, 80, 69}, { 87, 88, 78}, { 90, 80, 89}, { 97, 88, 89}},
	/*  80 */ {{ 58, 69, 70}, { 68, 69, 79}, { 71, 81, 70}, { 88, 89, 79}, { 91, 81, 90}, { 98, 89, 90}},
	/*  81 */ {{ 59, 70, 71}, { 69, 80, 70}, { 72, 82, 71}, { 89, 80, 90}, { 99, 90, 91}},
	/*  82 */ {{ 60, 72, 71}, { 70, 81, 71}, { 90, 81, 91}},
	/*  83 */ {{ 63, 73, 74}, { 75, 74, 84}, { 93, 84, 92}},
	/*  84 */ {{ 64, 74, 75}, { 73, 74, 83}, { 76, 75, 85}, { 94, 85, 93}, {100, 92, 93}},
	/*  85 */ {{ 65, 75, 76}, { 74, 75, 84}, { 77, 76, 86}, { 92, 84, 93}, { 95, 94, 86}, {101, 93, 94}},
	/*  86 */ {{ 66, 76, 77}, { 75, 76, 85}, { 78, 77, 87}, { 93, 85, 94}, { 96, 95, 87}, {102, 94, 95}},
	/*  87 */ {{ 67, 77, 78}, { 76, 77, 86}, { 79, 88, 78}, { 94, 86, 95}, { 97, 96, 88}, {103, 96, 95}},
	/*  88 */ {{ 68, 78, 79}, { 77, 78, 87}, { 80, 89, 79}, { 95, 96, 87}, { 98, 97, 89}, {104, 96, 97}},
	/*  89 */ {{ 69, 80, 79}, { 78, 88, 79}, { 81, 80, 90}, { 96, 88, 97}, { 99, 98, 90}, {105, 97, 98}},
	/*  90 */ {{ 70, 80, 81}, { 79, 80, 89}, { 82, 81, 91}, { 97, 89, 98}, {106, 98, 99}},
	/*  91 */ {{ 71, 81, 82}, { 80, 81, 90}, { 98, 90, 99}},
	/*  92 */ {{ 74, 83, 84}, { 85, 84, 93}, {101,100, 93}},
	/*  93 */ {{ 75, 84, 85}, { 83, 84, 92}, { 86, 85, 94}, {102,101, 94}},
	/*  94 */ {{ 76, 85, 86}, { 84, 85, 93}, { 87, 86, 95}, {100,101, 93}, {103,102, 95}},
	/*  95 */ {{ 77, 86, 87}, { 85, 94, 86}, { 88, 96, 87}, {101,102, 94}, {104, 96,103}},
	/*  96 */ {{ 78, 88, 87}, { 86, 95, 87}, { 89, 88, 97}, {102,103, 95}, {105,104, 97}},
	/*  97 */ {{ 79, 88, 89}, { 87, 96, 88}, { 90, 89, 98}, {103,104, 96}, {106,105, 98}},
	/*  98 */ {{ 80, 89, 90}, { 88, 97, 89}, { 91, 90, 99}, {104,105, 97}},
	/*  99 */ {{ 81, 90, 91}, { 89, 98, 90}, {105,106, 98}},
	/* 100 */ {{ 84, 92, 93}, { 94,101, 93}},
	/* 101 */ {{ 85, 93, 94}, { 92,100, 93}, { 95,102, 94}},
	/* 102 */ {{ 86, 94, 95}, { 93,101, 94}, { 96,103, 95}},
	/* 103 */ {{ 87, 96, 95}, { 94,102, 95}, { 97,104, 96}},
	/* 104 */ {{ 88, 96, 97}, { 95, 96,103}, { 98,105, 97}},
	/* 105 */ {{ 89, 97, 98}, { 96,104, 97}, { 99,106, 98}},
	/* 106 */ {{ 90, 98, 99}, { 97,105, 98}},
};
const int edge_neighs[107][3] = {
	{}, /* 1-based */
	/*   1 */ {},
	/*   2 */ {},
	/*   3 */ {  1,  2,  4},
	/*   4 */ {},
	/*   5 */ {},
	/*   6 */ {  2,  5},
	/*   7 */ {},
	/*   8 */ {  4,  9},
	/*   9 */ {},
	/*  10 */ {},
	/*  11 */ {  5, 10},
	/*  12 */ {},
	/*  13 */ {},
	/*  14 */ {},
	/*  15 */ {  9, 16},
	/*  16 */ {},
	/*  17 */ {},
	/*  18 */ { 10, 17},
	/*  19 */ {},
	/*  20 */ {},
	/*  21 */ {},
	/*  22 */ {},
	/*  23 */ {},
	/*  24 */ { 16, 25},
	/*  25 */ {},
	/*  26 */ {},
	/*  27 */ { 17, 26},
	/*  28 */ {},
	/*  29 */ {},
	/*  30 */ {},
	/*  31 */ {},
	/*  32 */ {},
	/*  33 */ {},
	/*  34 */ {},
	/*  35 */ { 36, 25},
	/*  36 */ {},
	/*  37 */ {},
	/*  38 */ { 37, 50, 26},
	/*  39 */ {},
	/*  40 */ {},
	/*  41 */ {},
	/*  42 */ {},
	/*  43 */ {},
	/*  44 */ {},
	/*  45 */ {},
	/*  46 */ {},
	/*  47 */ {},
	/*  48 */ { 36, 49, 61},
	/*  49 */ {},
	/*  50 */ {},
	/*  51 */ { 50, 62},
	/*  52 */ {},
	/*  53 */ {},
	/*  54 */ {},
	/*  55 */ {},
	/*  56 */ {},
	/*  57 */ {},
	/*  58 */ {},
	/*  59 */ {},
	/*  60 */ { 72, 61},
	/*  61 */ {},
	/*  62 */ {},
	/*  63 */ { 73, 62},
	/*  64 */ {},
	/*  65 */ {},
	/*  66 */ {},
	/*  67 */ {},
	/*  68 */ {},
	/*  69 */ {},
	/*  70 */ {},
	/*  71 */ { 72, 82},
	/*  72 */ {},
	/*  73 */ {},
	/*  74 */ { 73, 83},
	/*  75 */ {},
	/*  76 */ {},
	/*  77 */ {},
	/*  78 */ {},
	/*  79 */ {},
	/*  80 */ {},
	/*  81 */ { 82, 91},
	/*  82 */ {},
	/*  83 */ {},
	/*  84 */ { 83, 92},
	/*  85 */ {},
	/*  86 */ {},
	/*  87 */ {},
	/*  88 */ {},
	/*  89 */ {},
	/*  90 */ { 99, 91},
	/*  91 */ {},
	/*  92 */ {},
	/*  93 */ {100,101, 92},
	/*  94 */ {101,102},
	/*  95 */ {102,103},
	/*  96 */ {103,104},
	/*  97 */ {104,105},
	/*  98 */ { 99,105,106},
	/*  99 */ {},
	/* 100 */ {},
	/* 101 */ {},
	/* 102 */ {},
	/* 103 */ {},
	/* 104 */ {},
	/* 105 */ {},
	/* 106 */ {},
};
const int edge2corner[] = {
	/*  0 */  0, /* 0 -> 0 */
	/*  1 */  0, /* TOPRIGHT -> 0 */
	/*  2 */  0, /* BOTTOMRIGHT -> 0 */
	/*  3 */  0, /* TOPRIGHT|BOTTOMRIGHT -> 0 */
	/*  4 */  0, /* BOTTOM -> 0 */
	/*  5 */  0, /* TOPRIGHT|BOTTOM -> 0 */
	/*  6 */  0, /* BOTTOMRIGHT|BOTTOM -> 0 */
	/*  7 */  6, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM -> MIDRIGHT|BOTTOMRIGHT */
	/*  8 */  0, /* BOTTOMLEFT -> 0 */
	/*  9 */  0, /* TOPRIGHT|BOTTOMLEFT -> 0 */
	/* 10 */  0, /* BOTTOMRIGHT|BOTTOMLEFT -> 0 */
	/* 11 */  2, /* TOPRIGHT|BOTTOMRIGHT|BOTTOMLEFT -> MIDRIGHT */
	/* 12 */  0, /* BOTTOM|BOTTOMLEFT -> 0 */
	/* 13 */  8, /* TOPRIGHT|BOTTOM|BOTTOMLEFT -> BOTTOMLEFT */
	/* 14 */ 12, /* BOTTOMRIGHT|BOTTOM|BOTTOMLEFT -> BOTTOMRIGHT|BOTTOMLEFT */
	/* 15 */ 14, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM|BOTTOMLEFT -> MIDRIGHT|BOTTOMRIGHT|BOTTOMLEFT */
	/* 16 */  0, /* TOPLEFT -> 0 */
	/* 17 */  0, /* TOPRIGHT|TOPLEFT -> 0 */
	/* 18 */  0, /* BOTTOMRIGHT|TOPLEFT -> 0 */
	/* 19 */  3, /* TOPRIGHT|BOTTOMRIGHT|TOPLEFT -> TOP|MIDRIGHT */
	/* 20 */  0, /* BOTTOM|TOPLEFT -> 0 */
	/* 21 */  1, /* TOPRIGHT|BOTTOM|TOPLEFT -> TOP */
	/* 22 */  4, /* BOTTOMRIGHT|BOTTOM|TOPLEFT -> BOTTOMRIGHT */
	/* 23 */  7, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM|TOPLEFT -> TOP|MIDRIGHT|BOTTOMRIGHT */
	/* 24 */  0, /* BOTTOMLEFT|TOPLEFT -> 0 */
	/* 25 */ 17, /* TOPRIGHT|BOTTOMLEFT|TOPLEFT -> TOP|MIDLEFT */
	/* 26 */ 16, /* BOTTOMRIGHT|BOTTOMLEFT|TOPLEFT -> MIDLEFT */
	/* 27 */ 19, /* TOPRIGHT|BOTTOMRIGHT|BOTTOMLEFT|TOPLEFT -> TOP|MIDRIGHT|MIDLEFT */
	/* 28 */ 24, /* BOTTOM|BOTTOMLEFT|TOPLEFT -> BOTTOMLEFT|MIDLEFT */
	/* 29 */ 25, /* TOPRIGHT|BOTTOM|BOTTOMLEFT|TOPLEFT -> TOP|BOTTOMLEFT|MIDLEFT */
	/* 30 */ 28, /* BOTTOMRIGHT|BOTTOM|BOTTOMLEFT|TOPLEFT -> BOTTOMRIGHT|BOTTOMLEFT|MIDLEFT */
	/* 31 */ 31, /* TOPRIGHT|BOTTOMRIGHT|BOTTOM|BOTTOMLEFT|TOPLEFT -> TOP|MIDRIGHT|BOTTOMRIGHT|BOTTOMLEFT|MIDLEFT */
};
const int bits[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5};
#define enough_corners(i) (0xfee8e880 & (1 << (i)))
#define E_TOPRIGHT            1
#define E_BOTTOMRIGHT         2
#define E_BOTTOM              4
#define E_BOTTOMLEFT          8
#define E_TOPLEFT            16
#define C_TOP                 1
#define C_MIDRIGHT            2
#define C_BOTTOMRIGHT         4
#define C_BOTTOMLEFT          8
#define C_MIDLEFT            16
/* Apologies for my "French". :> */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <time.h>


#define MAX_DEPTH_START 3
int max_depth = MAX_DEPTH_START;
int verbose = 0;

#define EDGE_BITS 24

int first_moves[][40] = {{43, 0}, {55, 44, 0}, {43, 55, 44, 0}, {42, 44, 0}, {42, 43, 44, 0}, {31, 56, 0}, {31, 43, 56, 0}, {0}};
//int first_moves[][40] = {{37, 51, 64, 76, 87, 97, 106, 0}, {0}};
int start_paths[][2] = {{93, 48}, {38, 48}, {3, 98}, {3, 93}, {0}, /* END */ {85, 47}, {7, 89}, {39, 47}, {39, 89}, {0}};
int *first_move, *start_path;

void log_options(char *tag)
{
	/*
	FILE *fp = fopen("../options.log", "a");
	fprintf(fp, "first_move %d %d %d %d start_path %d %d %s\n", first_move[0], first_move[1], first_move[2], first_move[3], start_path[0], start_path[1], tag ? tag : "");
	fclose(fp);
	*/
}

void pick_options()
{
	int i;
	
	for (i = 0; first_moves[i][0]; ++i)
		if (random() < (RAND_MAX / (i + 1)))
			first_move = first_moves[i];
	
	for (i = 0; start_paths[i][0]; ++i)
		if (random() < (RAND_MAX / (i + 1)))
			start_path = start_paths[i];
	
	log_options(NULL);
}

#define LOG(log...) fprintf(stderr, log)

typedef enum {
	ST_1LINE = 0,
	ST_HALFLINE,
	ST_HALFLINE_DONE,
	ST_EXTRALINE,
	ST_FILLIN,
	ST_FAILED,
} stage_t;

struct plans {
	int todo[107];
	int todolen;
	stage_t stage;
};

struct game {
	/* Bits 0 and 1 are player white and black.
	   Bits EDGE_BITS+ are edges touched indirectly by this field. */
	int b[107];
	
	/* 1-based arrray, bitfields showing which corners are owned by
	   each player. enough_corners() tells whether a player has won. */
	int player_corners[3];
	
	int turn;
	int cur, me;
	
	struct plans *plans;
};

struct game *new_game(void)
{
	struct game *g = calloc(sizeof(struct game), 1);
	int i;
	
	memset(g, 0, sizeof(struct game));
	g->cur = g->turn = 1;
	g->b[0] = -1;
	for (i = 1; i <= 106; ++i)
		g->b[i] = edges[i] << EDGE_BITS;
	
	g->plans = calloc(sizeof(struct plans), 1);
	
	return g;
}

void print_board(struct game *g)
{
	int i, j, nl;
	const int *rs = rowsize;
	
	if (!verbose)
		return;
	
	nl = 0;
	for (i = 1; i < 107; ++i) {
		if (nl == 0) {
			LOG("%3d  ", i);
			for (j = 0; j < (13 - *rs); j++)
				LOG(" ");
			nl = *(rs++);
		}
		LOG("%2d", g->b[i] & 3);
		if (--nl == 0)
			LOG("\n");
	}
}

void print_raw(int board[107])
{
	int i, j, nl;
	const int *rs = rowsize;
	
	if (!verbose)
		return;
	
	nl = 0;
	for (i = 1; i < 107; ++i) {
		if (nl == 0) {
			LOG("%3d  ", i);
			for (j = 0; j < (13 - *rs); j++)
				LOG("  ");
			nl = *(rs++);
		}
		LOG("%4d", board[i] & 0xffff);
		if (--nl == 0)
			LOG("\n");
	}
}

int find_path_count_steps(struct game *g, int src, int dst,
                            int result[107], int step, int map[107])
{
	int i, n, best = 9999;
	
	/* Getting to a cell we already own is free, if it's empty it counts as a step/turn. */
	if (!(g->b[src] & 3))
		++step;
	else if (!(g->b[src] & g->cur))
		return best;
	
	/* If we got here before with same/less effort, abort. */
	if (step >= map[src])
		return best;
	
	/* Found a new best route to this point. */
	map[src] = step;
	
	/* Are we at our destination yet? */
	if (src == dst) {
		/* Found a new best route if we got this far. */
		if (!(g->b[src] & 3))
			result[step-1] = src;
		return step;
	}
	
	for (i = 0; i < 6 && (n = neighs[src][i]); ++i) {
		if (!(g->b[n] & (3 ^ g->cur))) {
			int ret = find_path_count_steps(g, n, dst, result, step, map);
			if (ret < best) {
				best = ret;
				result[step-1] = src;
			}
		}
	}
	
	return best;
}

int find_path(struct game *g, int src, int dst, int result[107])
{
	int map[107] = {};
	int fuck[108];
	int ret = 0;
	
	memset(map, 0x7f, sizeof(map));
	
	/* TODO(wilmer): REmove the very very bad things done up here ([-1]) */
	ret = find_path_count_steps(g, src, dst, fuck + 1, 0, map);
	memcpy(result, fuck + 1, sizeof(int) * 107);
	//ret = find_path_count_steps(g, src, dst, result, 0, map);
	
	/*
	LOG("find_path(%d, %d) =", src, dst);
	int i;
	if (ret>100)
		LOG(" %d", ret);
	else
		for (i = 0; i < ret; ++i)
			LOG(" %d", result[i]);
	LOG("\n");
	*/
	
	return ret < 999 ? ret : 1000000;
}

int find_path_triple(struct game *g, int a, int b, int c, int result[107])
{
	int abbc[107], acbc[107];
	struct game g2[1];
	int ret = 0, best = 1000000;
	int bc;
	int i;
	
	//LOG("Finding path for %d|%d|%d\n", a, b, c);
	
	ret = find_path(g, a, b, abbc);
	if (ret >= 999)
		return best;
	
	memcpy(g2, g, sizeof(struct game));
	for (i = 0; i < ret; ++i)
		g2->b[abbc[i]] |= g2->cur;
	
	bc = find_path(g2, b, c, abbc + ret);
	if (bc >= 999)
		return best;
	
	best = ret + bc;
	/* No need to try abac, since find_path() will already try that out. */
	
	ret = find_path(g, a, c, acbc);
	/* ab and bc are reachable, so is ac, no need to check. */
	
	memcpy(g2, g, sizeof(struct game));
	for (i = 0; i < ret; ++i)
		g2->b[acbc[i]] |= g2->cur;
	
	ret += find_path(g2, b, c, acbc + ret);
	if (ret < best) {
		memcpy(result, acbc, sizeof(int) * ret);
		best = ret;
	} else {
		memcpy(result, abbc, sizeof(int) * best);
	}
	
	/*
	LOG("find_path_triple =>");
	for (i = 0; i < best; ++i)
		LOG(" %d", result[i]);
	LOG("\n");
	*/

	return best;
}

void find_safe_paths_int(struct game *g, int src, int poss[107], int depth)
{
	int i, n;
	
	if ((g->b[src] & (g->cur ^ 3)) || (poss[src] & 0x1000000))
		return;
	++poss[src];
	
	if (depth == 1) /* 1-based so initial depth == number of moves */
		return;
	
	poss[src] |= 0x1000000; /* Mark as seen, avoid cycles. */
	
	for (i = 0; i < 6 && (n = common_neighs[src][i][0]); ++i) {
		/* Opponent is (partially) on the way, this destination is unsafe. */
		if ((g->b[common_neighs[src][i][1]] | g->b[common_neighs[src][i][2]]) & (g->cur ^ 3))
			continue;
		
		find_safe_paths_int(g, n, poss, depth - 1);
	}
	
	poss[src] &= ~0x1000000;
}

void find_safe_path_int(struct game *g, int src, int dst, int result[107], int work[107], int depth)
{
	int i, n;
	
	if ((g->b[src] & (g->cur ^ 3)) || (work[src] & 0x1000000))
		return;
	
	if (depth == 1) /* 1-based so initial depth == number of moves */
		return;
	
	if (!(g->b[src] & g->cur))
		work[src] += 1000;
	work[src] |= 0x1000000; /* Mark as seen, avoid cycles. */
	
	if (src == dst) {
		n = 0;
		/* Fragile: Count number of moves left to do. Mandatory counts
		   as 1, optional only if its counterpart is "higher". */
		for (i = 1; i < 107; ++i) {
			int w = work[i] & 0xffffff;
			if ((w >= 1000) || (w && i < w))
				++n;
		}
		if (n < result[0]) {
			LOG("Best one so far at depth %d, todo %d:\n", depth, n);
			print_raw(work);
			memcpy(result, work, sizeof(int) * 107);
			result[0] = n;
		}
	} else {
		for (i = 0; i < 6 && (n = common_neighs[src][i][0]); ++i) {
			int mid = g->b[common_neighs[src][i][1]] | g->b[common_neighs[src][i][2]];
			
			/* Opponent is (partially) in the way, this destination is unsafe. */
			if ((mid & 3) == (g->cur ^ 3))
				continue;
			
			if (work[common_neighs[src][i][1]] || work[common_neighs[src][i][2]])
				continue;
			
			if (!(mid & 3)) {
				work[common_neighs[src][i][1]] = common_neighs[src][i][2];
				work[common_neighs[src][i][2]] = common_neighs[src][i][1];
			}
			
			find_safe_path_int(g, n, dst, result, work, depth - 1);

			if (!(mid & 3)) {
				work[common_neighs[src][i][1]] = 0;
				work[common_neighs[src][i][2]] = 0;
			}
		}
	}
	
	if (!(g->b[src] & g->cur))
		work[src] -= 1000;
	work[src] &= ~0x1000000;
}

int find_safe_path(struct game *g, int src, int dst, int result[107], int depth)
{
	int work[107] = {};
	int i;
	
	result[0] = 999999;
	find_safe_path_int(g, src, dst, result, work, depth);
	
	if (result[0] > 100)
		return 999999;
	
	for (i = 1; i < 107; ++i)
		result[i] &= ~0x1000000;
	
	LOG("Safe path from %d to %d:\n", src, dst);
	print_raw(result);
	
	return result[0];
}

int find_clusters_int(struct game *g, int result[107], int pos)
{
	int i, n;
	int ret = 1;
	
	result[pos] |= 0x100; /* Seen. */
	for (i = 0; i < 6 && (n = neighs[pos][i]); ++i) {
		if (!(result[n] & 0x100) && (g->b[n] & g->b[pos] & 3)) {
			ret += find_clusters_int(g, result, n);
		}
	}
	
	return ret;
}

void find_clusters(struct game *g, int result[107])
{
	int i;
	for (i = 1; i < 107; ++i) {
		if (!(result[i] & 0x100) && (g->b[i] & 3)) {
			result[i] = find_clusters_int(g, result, i);
			LOG("Field size at %d: %d\n", i, result[i] &= 0xff);
		}
	}
}

void apply_move_update_edges(struct game *g, int pos, int new_edges)
{
	int i, n;
	
	g->b[pos] |= new_edges;
	
	for (i = 0; i < 6 && (n = neighs[pos][i]); ++i)
		if ((g->b[n] & g->cur) && (g->b[n] & new_edges) != new_edges)
			apply_move_update_edges(g, n, new_edges);
}

void apply_move(struct game *g, int move)
{
	if (move != -1) {
		int i, n, new_edges = 0;
		
		for (i = 0; i < 6 && (n = neighs[move][i]); ++i) {
			if (!(g->b[n] & g->cur))
				continue;
			
			new_edges |= g->b[n];
		}
		new_edges |= g->b[move];
		new_edges &= (0xff << EDGE_BITS);
		for (i = 0; i < 6 && (n = neighs[move][i]); ++i) {
			if (!(g->b[n] & g->cur))
				continue;
			
			if ((new_edges & g->b[n]) < new_edges)
				apply_move_update_edges(g, n, new_edges);
		}
		
		g->b[move] |= g->cur | new_edges;
		g->player_corners[g->cur] |= edge2corner[new_edges>>EDGE_BITS];
	} else {
		int i;
		
		/* Don't bother checking whether this is turn 2, referee does it. */
		for (i = 1; i < 107; ++i)
			if ((g->b[i] & 3)) {
				g->b[i] ^= 3;
				break;
			}
	}
	
	g->cur ^= 3;
	++g->turn;
}

int find_winner(struct game *g)
{
	int i;
	
	for (i = 1; i <= 2; ++i)
		if (enough_corners(g->player_corners[i])) {
			printf("Player %d has WON!\n", i);
			return i;
		}
	
	return 0;
}

int follow_game(void)
{
	struct game *g = new_game();
	int move;
	
	while(scanf("%d", &move) == 1) {
		apply_move(g, move);
		print_board(g);
		find_winner(g);
	}
	
	return 0;
}

void update_plans(struct game *g)
{
	int a, b, c, i;
	int path[107], best_path[107], path_len, best_len = 99999;
	int fields[107];
	
	if (!g->plans) {
		g->plans = calloc(sizeof(struct plans), 1);
	}
	
	if (g->plans->todolen) {
		for (i = 0; i < g->plans->todolen; ++i) {
			if (g->b[g->plans->todo[i]] & (3 ^ g->cur))
				break;
		}
		
		/* Our plan should still work. */
		if (i == g->plans->todolen && g->turn & 7)
			return;
	}
	
	if (g->turn <= 20) {
		//best_len = find_path_triple(g, 26, 100, 99, best_path);
		//best_len = find_path_triple(g, 1, 103, 82, best_path);
		//best_len = find_path_triple(g, 35, 89, 85, best_path);
		best_len = find_path(g, start_path[0], start_path[1], best_path);
		//best_len = find_path(g, 79, 105, best_path);
		
		if (best_len > 20)
		for (a = 0; edge_cells[a]; ++a) {
			for (b = a + 1; edge_cells[b]; ++b) {
				for (c = b; edge_cells[c]; ++c) {
					if ((g->b[edge_cells[a]] | g->b[edge_cells[b]] | g->b[edge_cells[c]]) & (g->cur ^ 3))
						continue;
					if (!enough_corners(g->player_corners[g->cur] |
					                   edge2corner[edges[edge_cells[a]] | edges[edge_cells[b]] | edges[edge_cells[c]]]))
						continue;
					
					if (b != c)
						path_len = find_path_triple(g, edge_cells[a], edge_cells[b], edge_cells[c], path);
					else
						path_len = find_path(g, edge_cells[a], edge_cells[b], path);
					
					if (path_len < best_len) {
						LOG("Possible PLAN: %d|%d|%d in %d moves\n", edge_cells[a], edge_cells[b], edge_cells[c], path_len);
						memcpy(best_path, path, sizeof(path));
						best_len = path_len;
					}
				}
			}
		}
	} else {
		int biggest = 0;
		
		find_clusters(g, fields);
		for (i = 2; i < 107; ++i)
			if ((g->b[i] & g->cur) && fields[i] > fields[biggest])
				biggest = i;
		
		for (i = 0; i < corner_cells[i]; ++i) {
			/* Might theoretically be disconnected.
			if (g->b[corner_cells[i]] & 3)
				continue;
			*/
			//if ((g->b[corner_cells[i]] & 
			path_len = find_path(g, biggest, corner_cells[i], path);
			if (path_len > 0 && path_len < best_len) {
				memcpy(best_path, path, sizeof(path));
				best_len = path_len;
			}
			LOG("Still interesting: %d in %d moves\n", corner_cells[i], path_len);
		}
		
		if (best_len > 5)
		for (i = 0; i < edge_cells[i]; ++i) {
			/* Might theoretically be disconnected.
			if (g->b[corner_cells[i]] & 3)
				continue;
			*/
			if (bits[edges[edge_cells[i]]] > 1) /* Skip corners */
				continue;
			if (!(((g->b[edge_cells[i]] & g->b[biggest]) >> EDGE_BITS) !=
			      (g->b[edge_cells[i]] >> EDGE_BITS)))
				continue;
			path_len = find_path(g, biggest, edge_cells[i], path);
			if (path_len > 0 && path_len < best_len) {
				memcpy(best_path, path, sizeof(path));
				best_len = path_len;
			}
			LOG("Still interesting: %d in %d moves\n", edge_cells[i], path_len);
		}
	}

	if (best_len > 1000) {
		LOG("Stuck :-(\n");
		return;
	}
	
	memcpy(g->plans->todo, best_path, sizeof(best_path));
	g->plans->todolen = best_len;
	
	LOG("NEW PLAN:");
	for (i = 0; i < best_len; ++i)
		LOG(" %d", best_path[i]);
	LOG("\n");
}

void list_moves(struct game *g, int moves[107])
{
	int i, j, n;
	
	memset(moves, 0, sizeof(int) * 107);
	
	if (1 || g->cur == g->me) {
		for (i = 0; i < g->plans->todolen; ++i)
			if (!(g->b[g->plans->todo[i]] & 3)) {
				moves[g->plans->todo[i]] = 50; //g->plans->todo[i] <= 49 ? 70 : 50;
				for (j = 0; j < 6 && (n = neighs[g->plans->todo[i]][j]); ++j) {
					if (!(g->b[n] & 3)) {
						moves[n] += 5;
						break;
					}
				}
			}
	}  {
		for (i = 1; i < 107; ++i) {
			if (!(g->b[i] & 3)) {
				for (j = 0; j < 6 && (n = neighs[i][j]); ++j) {
					if (g->b[n] & g->cur) {
						moves[i] += 1;
						break;
					}
				}
			}
		}
	}
}

int eval_move_int(struct game *g, int move, int cur)
{
	int i, n;
	int neigh_edges = 0, common_edges = 0x1f, n_neighs = 0;
	int new_corners = 0;
	int score = 0;
	
	for (i = 0; i < 6 && (n = neighs[move][i]); ++i) {
		if (g->b[n] & cur) {
			neigh_edges |= g->b[n] >> EDGE_BITS;
			common_edges &= g->b[n] >> EDGE_BITS;
			++n_neighs;
		}
	}
	common_edges &= neigh_edges; /* In case neighbours are all empty, it's still 0x1f. */
	
	new_corners = edge2corner[neigh_edges | (g->b[move] >> EDGE_BITS)];
	//LOG("%d %d %d %d %d %d %d\n", move, n_neighs, neigh_edges, common_edges, new_corners, g->player_corners[cur], enough_corners(new_corners | g->player_corners[cur]));
	if (enough_corners(new_corners | g->player_corners[cur])) { 
		/* Winning move! \o/ No need to look further. */
		return 1000000;
	}
	
	/* Slight preference for joining an existing "cluster". */
	score += n_neighs;
	
	score += 10 * bits[g->b[move] >> EDGE_BITS];
	
	/* How many edges are getting connected by this move? */
	if (neigh_edges > common_edges)
		score += 100 * bits[neigh_edges ^ common_edges];
	
	if (new_corners > g->player_corners[cur])
		score += 1000 * bits[new_corners];
	
	return score;
}

int eval_move(struct game *g, int move)
{
	int my_score = eval_move_int(g, move, g->cur);
	int their_score = eval_move_int(g, move, g->cur ^ 3);
	
//	LOG("%d %d %d %d\n", move, g->cur, my_score, their_score);
	
	/* I like to win. */
	if (my_score == 1000000) {
		return my_score;
	}
	
	/* Opponent *not* winning is nearly as important. */
	if (their_score == 1000000) { // && (g->cur == g->me) && 0) {
		return 8000;
	}
	
	return my_score + their_score;
}

int best_move(struct game *g, int depth, int *ret_eval)
{
	static int move_stack[MAX_DEPTH_START+1];
	int best_move_stack[MAX_DEPTH_START+1];
	int moves[107] = {};
	struct game g2[1];
	int move, eval, best_eval = -10000000, best = 0, next_eval;
	int opponent_wins = 0;
	int n = 0;
	
	list_moves(g, moves);
	for (move = 1; move < 107; ++move) {
		if (moves[move] == 0 || (g->b[move] & 3))
			continue;
		++n;
		if (depth == max_depth)
			memset(move_stack, 0, sizeof(move_stack));
		
		eval = moves[move] += eval_move(g, move);
		if (eval >= 8000 && eval < 10000)
			++opponent_wins;
		if (eval < 1000000 && eval > 0 && depth > 0) {
			memcpy(g2, g, sizeof(g2));
			apply_move(g2, move);
			best_move(g2, depth - 1, &next_eval);
			eval -= 0.8 * next_eval;
		}
		if (eval > best_eval) {
			memcpy(best_move_stack, move_stack, sizeof(move_stack));
			best = move;
			best_eval = eval;
		}
		if (depth == max_depth) {
			int i;
			LOG("%3d %6d because", move, eval);
			for (i = max_depth - 1; i >= 0; --i)
				LOG(" %d", move_stack[i]);
			LOG("\n");
		}
	}
	if (opponent_wins > 1) {
		/* To consider: If we can't possibly keep the opponent from
		   winning, don't even try and hope it's stupid. We might
		   eventually get to win ourselves. */
		//best_eval = 1000;
	}
	memcpy(move_stack, best_move_stack, sizeof(move_stack));
	if (ret_eval)
		*ret_eval = best ? best_eval : 0;
	move_stack[depth] = best;
//	if (g->turn >= 21)
//		LOG("Best move (out of %d) for %d at depth %d is %d (eval %d)\n", n, g->cur, depth, best, best_eval);
	return best;
}

void update_safe_todo_int(struct game *g, int src, int ihave, int todo[107], int *best, int c[2], int depth)
{
	int newtodo[107];
	int i, cell, st;

	for (i = 0; (cell = edge_cells[i]); ++i) {
		if (!enough_corners(edge2corner[ihave | edges[cell]]))
			continue;
		if (g->b[cell] & (g->cur ^ 3))
			continue;
		
		LOG("Try %d and %d\n", src, cell);
		st = find_safe_path(g, src, cell, newtodo, depth);
		if (st < *best) {
			c[0] = src;
			c[1] = cell;
			*best = st;
			memcpy(todo, newtodo, sizeof(newtodo));
		}
	}
	
	for (cell = 1; cell < 107; ++cell) {
		int n, free = 0, nedges = 0;
		
		if (!edge_neighs[cell][0])
			continue;
		if (g->b[cell] & (g->cur ^ 3))
			continue;
		
		for (i = 0; i < 3 && (n = edge_neighs[cell][i]); ++i) {
			if (!(g->b[n] & (g->cur ^ 3)))
				++free;
			nedges |= edges[n];
		}
		
		if (free < 2)
			continue;
		
		if (!enough_corners(edge2corner[ihave | nedges]))
			continue;
		
		LOG("Try %d and %d\n", src, cell);
		st = find_safe_path(g, src, cell, newtodo, depth);
		if (st < *best) {
			int j, n2;
			
			for (i = 0; i < 3 && (n = edge_neighs[cell][i]); ++i) {
				if (g->b[n] & (g->cur ^ 3))
					continue;
				for (j = i + 1; j < 3 && (n2 = edge_neighs[cell][j]); ++j) {
					if (g->b[n2] & (g->cur ^ 3))
						continue;
					if (!((g->b[n] | g->b[n2]) & g->cur)) {
						newtodo[n] = n2;
						newtodo[n2] = n;
					} else {
						newtodo[n] = 1000;
						newtodo[n2] = 1000;
					}
				}
			}
			
			*best = st;
			memcpy(todo, newtodo, sizeof(newtodo));
			print_raw(todo);
			
			c[0] = src;
			c[1] = cell;
		}
	}
}

void update_safe_todo(struct game *g, int todo[107], int c[6])
{
	int best = 999999;
	int i, cell;
	static int oldtodo[107]; /* Not threaded/nested anyway so whatever. */
	
	if (g->plans->stage == ST_1LINE) {
		if (find_safe_path(g, c[0], c[1], todo, 10) < 100)
			return;
		else
			++g->plans->stage; /* Try to finish it somehow. */
	}
	
	if (g->plans->stage == ST_HALFLINE) {
		/* Initial plan (one line/link to win) fully failed now.
		   See what we can make of it. */
		int i, mid = 1;
		
		/* Find the corner in between c[0-1]. */
		for (i = 0; (cell = corner_cells[i]); ++i) {
			if ((edges[cell] & edges[c[0]]) &&
			    (edges[cell] & edges[c[1]])) {
				mid = cell;
				break;
			}
		}

		update_safe_todo_int(g, c[0], edges[c[0]], todo, &best, c + 2, 12);
		update_safe_todo_int(g, c[1], edges[c[1]], todo, &best, c + 2, 12);
		
		update_safe_todo_int(g, c[0], edges[c[0]] | (edges[c[1]] & ~edges[mid]), todo, &best, c + 2, 12);
		update_safe_todo_int(g, c[1], edges[c[1]] | (edges[c[0]] & ~edges[mid]), todo, &best, c + 2, 12);
		
		if (best < 100) {
			print_raw(todo);
			return;
		}
	}	
	
	if (g->plans->stage == ST_HALFLINE_DONE) {
		/* We've finished the mandatory todo items, yet this function
		   was called. It means we need to draw another line. Remember
		   this one because it's still unfinished. */
		
		memcpy(oldtodo, todo, sizeof(oldtodo)); /* Urgh. */
		
		++g->plans->stage;
	}
	
	if (g->plans->stage == ST_EXTRALINE) {
		int ihave = edges[c[2]] | edges[c[3]] | edges[edge_neighs[c[3]][0]]
		          | edges[edge_neighs[c[3]][1]] | edges[edge_neighs[c[3]][2]];

		update_safe_todo_int(g, c[2], ihave, todo, &best, c + 4, 12);
		
		if (best < 100) {
			LOG("MERGE %d %d %d %d %d %d\n", c[0], c[1], c[2], c[3], c[4], c[5]);
			print_raw(todo);
			print_raw(oldtodo);
			for (i = 1; i < 107; ++i)
				if (todo[i] >= 1000) {
					/* Just leave it. */	
				} else if (oldtodo[i] && !todo[i])
					todo[i] = oldtodo[i];
				else if (oldtodo[i] && todo[i]) {
					todo[todo[i]] = 0;
					todo[oldtodo[i]] = 0;
					oldtodo[todo[i]] = 0;
					oldtodo[oldtodo[i]] = 0;
					todo[i] = 1100;
				}
			
			print_raw(todo);
			return;
		}
	}
	
	g->plans->stage = ST_FAILED;
}

int play_game(char *start[])
{
	struct game *g = new_game();
	int move;
	char move_s[16];
	int i;
	
	if (start) {
		for (i = 0; start[i]; ++i) {
			sscanf(start[i], "%d", &move);
			apply_move(g, move);
		}
		g->me = g->cur;
	} else
		g->me = 2;
	
	while (1) {
		if (g->cur != g->me) {
			if (scanf("%s", move_s) != 1)
				break;
			
			if (sscanf(move_s, "%d", &move) == 1) {
			} else if (strcasecmp(move_s, "Quit") == 0) {
				break;
			} else if (strcasecmp(move_s, "Start") == 0) {
				/* I'm white! */
				g->me = 1;
				continue;
			}
			
			if (!(move == -1 || (move >= 1 && move <= 106 && !(g->b[move] & 3)))) {
				LOG("INVALID!\n");
				continue;
			}
		} else if (g->plans->stage < ST_FAILED) {
			static int c[6] = {};
			static int todo[107] = {};
			int last = move;
			int n, j;
			
			move = 0;
			
			if (g->turn == 1) {
				move = 1;
				c[0] = 1;
			} else if (g->turn == 2) {
				if (bits[edges[last]] > 1) {
					c[0] = last;
					move = -1;
				} else {
					for (i = 0; corner_cells[i]; ++i) {
						if (g->b[corner_cells[i]] & 3)
							continue;
						for (j = 0; j < 6 && (n = neighs[corner_cells[i]][j]); ++j)
							if (g->b[n] & 3)
								break;
						if (n)
							continue;
						
						move = c[0] = corner_cells[i];
						break;
					}
				}
			} else if (last == -1) {
				move = c[0] = 37;
			} else if (!c[1]) {
				for (i = 0; corner_cells[i]; ++i) {
					if (g->b[corner_cells[i]] & 3)
						continue;
					for (j = 0; j < 6 && (n = neighs[corner_cells[i]][j]); ++j)
						if (g->b[n] & 3)
							break;
					if (n)
						continue;
					if (edges[c[0]] & edges[corner_cells[i]])
						continue;
					
					move = c[1] = corner_cells[i];
					break;
				}
				
				update_safe_todo(g, todo, c);
			} else {
				if (todo[last] >= 1000) {
					/* Opponent stole a mandatory cell of our
					   planned path. Reroute. */
					LOG("Need to reroute.\n");
					update_safe_todo(g, todo, c);
				} else if (todo[last]) {
					/* Opponent chose a non-mandatory cell,
					   pick its alternative now. */
					move = todo[last];
					todo[last] = 0;
					todo[move] = 0;
				}
				
				if (move == 0) {
					for (i = 1; i < 107; ++i) {
						if (!(g->b[i] & 3) && todo[i] >= 1000) {
							/* Not very pretty code, this is meant
							   to detect whether any neighbour field
							   is owned by the opponent, continue if not. */
							for (j = 0; j < 6 && (n = neighs[i][j]); ++j)
								if (g->b[n] & (g->cur ^ 3))
									break;
							if (j == 6 || !n)
								continue;
							
							/* If the opponent has made a move
							   close to here recently, take this
							   cell now. */
							move = i;
							break;
						}
					}
				}
				
				if (move == 0) {
					for (i = 1; i < 107; ++i) {
						if (!(g->b[i] & 3) && todo[i] >= 1000 &&
						    (!move || todo[i] > todo[move]))
							move = i;
					}
				}
				
				if (move == 0 && g->plans->stage == ST_HALFLINE) {
					/* Mandatory todo's finished, but we'll need to
					   think of some more things. */
					++g->plans->stage;
					update_safe_todo(g, todo, c);
				}
				
				/* REPEAT OF THE ABOVE: We've just updated the todo so
				   rescan for mandatory items. */
				if (move == 0) {
					for (i = 1; i < 107; ++i) {
						if (!(g->b[i] & 3) && todo[i] >= 1000 &&
						    (!move || todo[i] > todo[move]))
							move = i;
					}
				}
				
				if (move == 0) {
					for (i = 1; i < 107; ++i) {
						if (!(g->b[i] & 3) && todo[i]) {
							move = i;
							todo[todo[move]] = 0;
							todo[move] = 0;
							break;
						}
					}
				}
			}
			
			if (!move) {
				move = 1;
				g->plans->stage = ST_FAILED;
			}
			
			/* Ensure that the move is valid, unless we're debugging. */
			if (!verbose || g->plans->stage == ST_FAILED)
				while ((g->b[move] & 3))
					move = (move % 106) + 1;
			
			printf("%d\n", move);
			fflush(stdout);
		} else {
			if (g->turn == 2 && edges[move] && (edges[move] & (edges[move] - 1)) > 0) {
				/* Is this a corner and can we steal it? If so, let's do that,
				   because we can. :-) */
				move = -1;
			} else
				move = 0;
			
			if (move == 0 && *first_move) {
				while (*first_move) {
					if (!(g->b[*first_move] & 3)) {
						move = *first_move;
						break;
					}
					++first_move;
				}
			}
			
			if (move == 0) {
				update_plans(g);
				move = best_move(g, max_depth, NULL);
			}
			
			/* Safeguard to ~ensure a valid move. */
			if (move != -1)
				while ((g->b[move] & 3))
					move = (move % 106) + 1;
			
			printf("%d\n", move);
			fflush(stdout);
		}
			
		LOG("%s move: %d\n", g->cur == g->me ? "My" : "Opponent", move);
		apply_move(g, move);
		print_board(g);
		
		if (find_winner(g)) {
			if (find_winner(g) == g->me)
				log_options("WIN");

			/* To avoid "Could not write to stdin" error from referree
			   at shutdown time: */
			usleep(100000);
			break;
		}
		
		LOG("CPU time so far: %f\n", ((float) clock()) / CLOCKS_PER_SEC);
		if (clock() / CLOCKS_PER_SEC >= 20) {
			LOG("Time is starting to run out, time to cut some corners.\n");
			max_depth = MAX_DEPTH_START - 1;
		}
	}
	
	return 0;
}

int main(int argc, char *argv[])
{
	char **test = NULL;
	char *s;
	
	srand(time(NULL));
	pick_options();
	
	if ((s = getenv("USER")) && strcmp(s, "wilmer") == 0)
		verbose = 1;
	
	if (argc > 1 && strcmp(argv[1], "follow") == 0) {
		return follow_game();
	}
	if (argc > 1 && strcmp(argv[1], "test") == 0) {
		test = argv + 2;
	}
	
	return play_game(test);
}