code guessing, round #85 (completed)

#!/usr/bin/env node

/**
 *
 *     @@@@@@@  @@@@@@  @@@@@@@  @@@@@@@@  @@@@@@@  @@@  @@@ @@@@@@@@  @@@@@@  @@@@@@    @@@  @@@  @@@  @@@@@@  @@@@@@@  @@@@@@@@ @@@@@@@@
 *    !@@      @@!  @@@ @@!  @@@ @@!      !@@       @@!  @@@ @@!      !@@     !@@        @@!  @@!  @@! @@!  @@@ @@!  @@@ @@!           @@!
 *    !@!      @!@  !@! @!@  !@! @!!!:!   !@! @!@!@ @!@  !@! @!!!:!    !@@!!   !@@!!     @!!  !!@  @!@ @!@!@!@! @!@!!@!  @!!!:!      @!!
 *    :!!      !!:  !!! !!:  !!! !!:      :!!   !!: !!:  !!! !!:          !:!     !:!     !:  !!:  !!  !!:  !!! !!: :!!  !!:       !!:
 *     :: :: :  : :. :  :: :  :  : :: ::   :: :: :   :.:: :  : :: ::  ::.: :  ::.: :       ::.:  :::    :   : :  :   : : : :: ::  :.::.: :
 *
 *
 *    @@@@@@@  @@@@@@@  @@@@@@@@  @@@@@@ @@@@@@@@ @@@  @@@ @@@@@@@  @@@@@@
 *    @@!  @@@ @@!  @@@ @@!      !@@     @@!      @@!@!@@@   @!!   !@@
 *    @!@@!@!  @!@!!@!  @!!!:!    !@@!!  @!!!:!   @!@@!!@!   @!!    !@@!!
 *    !!:      !!: :!!  !!:          !:! !!:      !!:  !!!   !!:       !:!
 *     :        :   : : : :: ::  ::.: :  : :: ::  ::    :     :    ::.: :
 *
 *
 *    @@@      @@@@@@@@  @@@@@@@   @@@@@@  @@@          @@@@@@ @@@  @@@  @@@@@@  @@@  @@@ @@@@@@@@    @@@@@@@   @@@@@@  @@@@@@@
 *    @@!      @@!      !@@       @@!  @@@ @@!         !@@     @@!@!@@@ @@!  @@@ @@!  !@@ @@!         @@!  @@@ @@!  @@@   @!!
 *    @!!      @!!!:!   !@! @!@!@ @!@!@!@! @!!          !@@!!  @!@@!!@! @!@!@!@! @!@@!@!  @!!!:!      @!@!@!@  @!@  !@!   @!!
 *    !!:      !!:      :!!   !!: !!:  !!! !!:             !:! !!:  !!! !!:  !!! !!: :!!  !!:         !!:  !!! !!:  !!!   !!:
 *    : ::.: : : :: ::   :: :: :   :   : : : ::.: :    ::.: :  ::    :   :   : :  :   ::: : :: ::     :: : ::   : :. :     :
 *
 */

const readline = require('readline');
let process = require("node:process");
process.stdin.setEncoding('ascii');

(async () => {
	console.log('ascii');
	let width = 0;
	let height = 0;
	{
		const rl = readline.createInterface({
			input: process.stdin
		})
		for await (const line of rl) {
			if (width == 0) {
				width = parseInt(line, 10);
				continue;
			} else {
				height = parseInt(line, 10);
				break;
			}
		}
	}

	cmd = async (s) => {
		console.log(s);

		let r = new Set();
		{
			const rl = readline.createInterface({
				input: process.stdin
			})
			let i = 0;
			for await (const line of rl) {
				r = r.union(new Set(line.split('$').map(d => d.length + i * width)));
				let head = line.indexOf('0');
				if (head > -1) {
					if (line.indexOf('.') == -1 && ((line + line).indexOf('0$') == -1)) {
						return null;
					}
				}

				if (i == height) {
					break;
				}

				i += 1;
			}
		}
		return r;
	}

	while(1) {
		let last = await cmd('d') ?? new Set();
		for(let i = 0; i < 16; ++i) {
			let n = await cmd('r');
			if (n == null || n.isDisjointFrom(last)) {
				break;
			}
		}
	}
})();

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <clocale>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iterator>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <vector>

#if (__cplusplus >= 202302L)
#  include <utility>
#  define UNREACHABLE std::unreachable();
#else
#  define UNREACHABLE __builtin_unreachable();
#endif

int_least32_t get2char()
{
  char16_t buf;

  if (!fread(&buf, 2, 1, stdin))
    return -1;

  return buf;
}

char *read2line1()
{
  static char line[4096];
  int i = 0;
  int_least32_t c;

  while ((c = get2char()), c != -1 && c != '\n') {
    if (i < sizeof(line) - 1)
      line[i++] = c;
  }

  line[i] = 0;

  return line;
}

bool is_le()
{
  union {
    short h;
    char c[2];
  } num;

  num.h = 1;

  return num.c[0];  // undifined behavior
}

struct Pos {
  int x, y;

  constexpr Pos(int x, int y) : x(x), y(y) {}
  constexpr Pos() : x(0), y(0) {}
};

struct Dir {
  char i;

  constexpr Dir(int i) : i(i) {}
  constexpr Dir() : i(4) {}

  constexpr char to_cmd()
  {
    constexpr std::array<char, 4> cmds{'r', 'd', 'l', 'u'};

    return cmds[i];
  }

  constexpr char to_cmd_fast()
  {
    return to_cmd() + ('A' - 'a');
  }
};

constexpr bool is_cstr(int c, const char16_t *str)
{
  for (; *str != '\0'; str++)
    if (c == *str)
      return true;

  return false;
}

Pos operator+(Pos pos, Dir dir)
{
  switch (dir.i) {
    case 0:
      return Pos(pos.x + 1, pos.y + 0);
    case 1:
      return Pos(pos.x + 0, pos.y + 1);
    case 2:
      return Pos(pos.x - 1, pos.y + 0);
    case 3:
      return Pos(pos.x + 0, pos.y - 1);
  }

  UNREACHABLE
}

Dir operator-(Pos dst, Pos src)
{
  Pos off(dst.x - src.x, dst.y - src.y);

  struct H {
    static constexpr int i(int x, int y)
    {
      return (y + 1) * 3 + (x + 1);
    }
  };

  switch (H::i(off.x, off.y)) {
    case H::i(1, 0):
      return {0};
    case H::i(0, 1):
      return {1};
    case H::i(-1, 0):
      return {2};
    case H::i(0, -1):
      return {3};
  }

  fprintf(stderr, "bad offset %i %i\n", off.x, off.y);

  UNREACHABLE
}

bool operator==(Pos a, Pos b)
{
  return a.x == b.x && a.y == b.y;
}
bool operator!=(Pos a, Pos b)
{
  return !(a == b);
}
bool operator==(Dir a, Dir b)
{
  return a.i == b.i;
}
bool operator!=(Dir a, Dir b)
{
  return a.i != b.i;
}
Dir operator-(Pos dst)
{
  return dst - Pos();
}
Dir operator+(Dir dir, int n)
{
  return {(char)(((dir.i + n) % 4 + 4) % 4)};
}
Dir operator-(Dir dir, int n)
{
  return dir + -n;
}
Dir operator~(Dir dir)
{
  return dir + 2;
}

struct Cell {
  char16_t c;

  constexpr Cell() : c(u'\0') {}
  constexpr Cell(char16_t c) : c(c) {}

  operator bool()
  {
    return c != u'\0';
  }
  operator char16_t()
  {
    return c;
  }

  constexpr bool is_apple()
  {
    return c == u'$';
  }
  constexpr bool is_safe()
  {
    return c == u'.' || is_apple();
  }
  constexpr bool is_neck()
  {
    return is_cstr(c, u"╬╔═╚╗║╝");
  }

  static constexpr Cell apple()
  {
    return {u'$'};
  }
  static constexpr Cell space()
  {
    return {u'.'};
  }
  static constexpr Cell bodybase(const char16_t *charset, std::bitset<4> conns)
  {
    for (const char16_t *s = charset; *s != 0; s++)
      if (Cell(*s).connections() == conns)
        return Cell(*s);

    UNREACHABLE
  }
  static constexpr Cell neck(std::bitset<4> conns)
  {
    return bodybase(u"╬╔═╚╗║╝", conns);
  }
  static constexpr Cell body(std::bitset<4> conns)
  {
    return bodybase(u"╋┏━┗┓┃┛", conns);
  }
  static Cell neck(Dir a, Dir b)
  {
    std::bitset<4> conns{0};
    conns[a.i] = 1;
    conns[b.i] = 1;
    return neck(conns);
  }
  static Cell body(Dir a, Dir b)
  {
    std::bitset<4> conns{0};
    conns[a.i] = 1;
    conns[b.i] = 1;
    return body(conns);
  }
  static constexpr Cell neck(Cell base)
  {
    return neck(base.connections());
  }
  static constexpr Cell body(Cell base)
  {
    return body(base.connections());
  }
  static constexpr Cell neck()
  {
    return neck(std::bitset<4>(0b1111));
  }
  static constexpr Cell body()
  {
    return body(std::bitset<4>(0b1111));
  }

  constexpr std::bitset<4> connections()
  {
    switch (c) {
      case u'╬':
      case u'╋':
        return {0b1111};
      case u'╔':
      case u'┏':
        return {0b0011};
      case u'╗':
      case u'┓':
        return {0b0110};
      case u'╝':
      case u'┛':
        return {0b1100};
      case u'╚':
      case u'┗':
        return {0b1001};
      case u'║':
      case u'┃':
        return {0b1010};
      case u'═':
      case u'━':
        return {0b0101};
    }

    return {0};
  }

  constexpr bool is_connected(Dir dir)
  {
    const auto state = connections();

    return state[dir.i];
  }

  constexpr Dir walkdir(Dir dir)
  {
    const auto state = connections();

    if (state[dir.i])
      return dir;

    if (state[(dir - 1).i])
      return dir - 1;

    if (state[(dir + 1).i])
      return dir + 1;

    fprintf(stderr, "walktf! (%lc) %i\n", (int)c, (int)dir.i);

    UNREACHABLE
  }

  constexpr std::bitset<2> player()
  {
    if (c == u'0')
      return {0b01};
    if (c == u'O')
      return {0b10};

    return {0};
  }
};

bool operator==(Cell a, char16_t b)
{
  return a.c == b;
}
bool operator!=(Cell a, char16_t b)
{
  return a.c != b;
}

template<class T> class Grid {
 protected:
  int m_width, m_height;
  std::vector<T> data;

 public:
  Grid(int width, int height) : m_width(width), m_height(height)
  {
    data.reserve((m_width + 1) * m_height + 1);
    data.resize((m_width + 1) * m_height + 1);

    if constexpr (std::is_same_v<T, Cell>) {
      for (int y = 0; y < m_height; y++) {
        data[y * (m_width + 1) + m_width] = {u'\n'};
      }

      data[(m_width + 1) * m_height] = {u'\n'};
    }
  }

  void copy_from(Grid &other)
  {
    if (other.width() != width() || other.height() != height())
      UNREACHABLE

    data = other.data;
  }

  bool copy_io(FILE *io = stdin)
  {
    if (!fread(data.data(), data.size() * sizeof(typename decltype(data)::value_type), 1, io))
      return false;

    return true;
  }

  int width()
  {
    return m_width;
  }
  int height()
  {
    return m_height;
  }

  Pos norm(Pos pos)
  {
    return {(pos.x % m_width + m_width) % m_width, (pos.y % m_height + m_height) % m_height};
  }

  Pos norm(Pos pos, Pos base)
  {
    Pos off(pos.x - base.x, pos.y - base.y);

    return {base.x + off.x % m_width, base.y + off.y % m_height};
  }

  decltype(data[0]) operator[](Pos pos)
  {
    pos = norm(pos);

    return data[pos.y * (m_width + 1) + pos.x];
  }

  class iterator {
    Pos pos;
    Grid &grid;

    friend class Grid;
    iterator(Pos pos, Grid &grid) : pos(pos), grid(grid) {}

   public:
    using difference_type = std::ptrdiff_t;
    using value_type = std::pair<Pos, decltype(grid.data[0])>;

    value_type operator*()
    {
      return {pos, grid[pos]};
    }
    bool operator==(const iterator &other)
    {
      return pos == other.pos;
    }
    bool operator!=(const iterator &other)
    {
      return !(*this == other);
    }

    iterator &operator++()
    {
      if (pos.x == grid.width() - 1) {
        pos.x = 0;
        pos.y++;
        return *this;
      }

      pos.x++;
      return *this;
    }

    iterator operator++(int)
    {
      auto tmp = *this;
      ++*this;
      return tmp;
    }
  };

  iterator begin()
  {
    return {Pos(), *this};
  }

  iterator end()
  {
    return {Pos(0, m_height), *this};
  }

  void validate()
  {
    if constexpr (std::is_same_v<T, Cell>) {
      for (int y = 0; y < m_height; y++) {
        if (data[y * (m_width + 1) + m_width] != u'\n')
          throw std::runtime_error("corrupted board");
      }

      if (data[(m_width + 1) * m_height] != u'\n')
        throw std::runtime_error("corrupted board");
    }
  }
};

struct Player {
  Pos pos;
  int debt;
};

enum MoveResult {
  MRESULT_NOOP,
  MRESULT_DEAD,
  MRESULT_FOOD,
  MRESULT_CONT,
};

enum MoveStage {
  MSTAGE_FUME = 0,
  MSTAGE_FAPL = 1,
  MSTAGE_MOVE = 2,
  MSTAGE_FIN = 3,
};

struct Move {
  Dir dir;
  bool fast;
};

class Game : public Grid<Cell> {
  std::vector<Player> players;
  Grid<int> density;
  int apple_count;

  Game(int width, int height) : Grid(width, height), density(width, height) {}

  void init_state()
  {
    players.resize(0);
    apple_count = 0;

    for (auto [pos, cell] : *this) {
      if (cell.player()[0])
        players.insert(players.begin(), Player{.pos = pos, .debt = 0});
      else if (cell.player()[1])
        players.push_back(Player{.pos = pos, .debt = 0});

      if (cell.is_apple())
        apple_count++;
    }

    players.shrink_to_fit();
  }

  std::deque<Pos> snake_body(Pos pos)
  {
    if (!(*this)[pos].player().any()) {
      for (int y = 0; y < height(); y++) {
        for (int x = 0; x < width(); x++) {
          fprintf(stderr,
                  "%lc",
                  (x == pos.x - 1 && y == pos.y) ? '[' :
                  (x == pos.x + 1 && y == pos.y) ? ']' :
                                                   (int)(*this)[Pos(x, y)].c);
        }
        fprintf(stderr, "\n");
      }

      throw std::runtime_error("bad snake");
    }

    Dir dir;
    std::deque<Pos> body{pos};

    for (int i = 0; i < 4; i++) {
      if ((*this)[pos + Dir(i)].is_neck() && (*this)[pos + Dir(i)].is_connected(~Dir(i))) {
        dir = Dir(i);
        break;
      }
    }

    if (dir.i == 4)
      throw std::runtime_error("bad snake");

    for (;;) {
      pos = pos + dir;
      dir = (*this)[pos].walkdir(dir);

      body.push_back(pos);

      if (!(*this)[pos + dir].is_connected(~dir))
        break;
    }

    if (body.size() < 3)
      throw std::runtime_error("bad snake");

    return body;
  }

  void kill(Pos pos)
  {
    for (Pos segpos : snake_body(pos))
      (*this)[segpos] = ((*this)[segpos].connections() == 4 || rand() > RAND_MAX / 2) ?
                            Cell::apple() :
                            Cell::space();
  }

  static bool is_ambiguous(Pos pos, Cell neck, Grid<int> &density)
  {
    for (int i = 0; i < 4; i++)
      if (neck.is_connected(Dir(i)) && !density[pos + Dir(i)])
        return true;

    return false;
  }

  void init_snake_density()
  {
    for (auto [pos, cell] : *this)
      density[pos] = cell.player().any() ? 1 : cell.connections().count() / 2;
  }

  struct MoveState {
    Pos pos;
    int debt;
    int ate;
    std::deque<Pos> body;
    std::vector<Pos> nheads;
    Dir dir;
    bool fast;
    Grid<Cell> tmp;

    MoveState(Game &game) : tmp(game.width(), game.height()) {}
  };

  enum MoveResult move_single(MoveState &state, int stage)
  {
    return move_single(
        state.pos, state.debt, state.body, state.nheads, state.dir, stage, state.tmp, state.ate);
  }

  enum MoveResult move_single(Pos pos,
                              int &debt,
                              std::deque<Pos> &body,
                              std::vector<Pos> &nheads,
                              Dir dir,
                              int stage,
                              Grid<Cell> &tmp,
                              int &ate)
  {
    switch (stage) {
      case MSTAGE_FUME:
        while (debt >= 2 && std::distance(body.begin(), body.end()) >= 5 &&
               (*this)[*std::prev(body.end())].connections().count() < 4)
        {
          Pos tailpos = *std::prev(body.end());
          body.pop_back();

          density[tailpos]--;
          tmp[tailpos] = Cell::apple();

          debt -= 2;
        }

        return MRESULT_CONT;

      case MSTAGE_FAPL:
        for (auto [pos, cell] : tmp) {
          if (cell) {
            (*this)[pos] = cell;
            tmp[pos] = {};
          }
        }

        return MRESULT_CONT;

      case MSTAGE_MOVE: {
        Grid<int> local_density(width(), height());

        for (Pos segpos : body) {
          Cell cell = (*this)[segpos];

          local_density[segpos] = cell.player().any() ? 1 : cell.connections().count() / 2;
        }

        int i = 0;

        do {
          Pos tail = *std::prev(body.end());
          body.pop_back();
          Pos head = *body.begin();
          Pos neck = *std::next(body.begin());
          Pos nexthead = head + dir;
          Cell headval = tmp[head] ? tmp[head] : (*this)[head];
          Cell neckval = tmp[neck] ? tmp[neck] : (*this)[neck];
          Cell nextheadval = tmp[nexthead] ? tmp[nexthead] : (*this)[nexthead];
          Cell tailval = tmp[tail] ? tmp[tail] : (*this)[tail];
          Dir taildir = tail - *std::prev(body.end());

          if (!nextheadval.is_apple()) {
            tmp[tail] = local_density[tail] == 2 ?
                            (tailval.is_neck() ? Cell::neck(taildir + 1, taildir - 1) :
                                                 Cell::body(taildir + 1, taildir - 1)) :
                            Cell::space();
            neckval = tmp[neck] ? tmp[neck] : (*this)[neck];
            headval = tmp[head] ? tmp[head] : (*this)[head];
            local_density[tail]--;
            density[tail]--;
          }
          else {
            ate++;
            body.push_back(tail);
          }

          tmp[neck] = Cell::body(neckval);
          tmp[head] = headval.connections().any() ? Cell::neck(headval) :
                                                    Cell::neck(dir, neck - head);

          if (local_density[nexthead] &&
              nextheadval.connections() != Cell::body(dir + 1, dir - 1).connections())
          {
            return MRESULT_DEAD;
          }
          else if (local_density[nexthead]) {
            tmp[nexthead] = Cell::neck();
          }
          else {
            tmp[nexthead] = (*this)[pos];
            nheads.push_back(nexthead);
          }

          body.push_front(nexthead);
          local_density[nexthead]++;
          density[nexthead]++;

          if (++i > 1000) {
            std::string info;

            for (int y = 0; y < height(); y++) {
              for (int x = 0; x < width(); x++) {
                char buf[16];

                sprintf(
                    buf, "%lc", (char16_t)(tmp[Pos(x, y)] ? tmp[Pos(x, y)] : (*this)[Pos(x, y)]));

                info += buf;
              }

              info += "\n";
            }

            info += "vs: (orig)\n";

            for (int y = 0; y < height(); y++) {
              for (int x = 0; x < width(); x++) {
                char buf[16];

                sprintf(buf, "%lc", (char16_t)((*this)[Pos(x, y)]));

                info += buf;
              }

              info += "\n";
            }

            throw std::runtime_error(std::string("wtf? {\n") + info + "}\n");
          }
        } while (tmp[body[0]] != (*this)[pos] ||
                 is_ambiguous(body[1], tmp[body[1]], local_density));

        return MRESULT_CONT;
      }

      case MSTAGE_FIN:
        for (auto pos : nheads) {
          if (density[pos] > 1)
            return MRESULT_DEAD;
        }

        for (auto [pos, cell] : tmp) {
          if (cell && !(cell.is_safe() && density[pos])) {
            (*this)[pos] = cell;
          }
          tmp[pos] = {};
        }

        return ate ? MRESULT_FOOD : MRESULT_NOOP;

      default:
        UNREACHABLE
    }
  }

 public:
  static Game from_io()
  {
    int width, height;

    setvbuf(stdout, NULL, _IONBF, 0);
    printf("utf16%s\n", is_le() ? "le" : "be");

    const char *ln;
    if (sscanf(ln = read2line1(), "%i", &width) != 1) {
      fprintf(stderr, "line read(%s)\n", ln);
      throw std::runtime_error("failed to read width");
    }

    if (sscanf(read2line1(), "%i", &height) != 1)
      throw std::runtime_error("failed to read height");

    Game game(width, height);

    if (!fread(game.data.data(),
               game.data.size() * sizeof(decltype(game.data)::value_type),
               1,
               stdin))
      throw std::runtime_error("failed to read board");

    game.validate();
    game.init_state();

    return game;
  }

  Pos player_pos(int i = 0)
  {
    return players[i].pos;
  }

  int player_length(int i = 0)
  {
    return snake_body(players[i].pos).size();
  }

  int avail_space(int i = 0)
  {
    Grid<bool> seen(width(), height());
    Grid<bool> gsnake(width(), height());
    std::vector<Pos> queue{players[i].pos};
    seen[queue[0]] = true;
    std::vector<Pos> queue_next;
    int amount = 0;

    if (!(*this)[queue[0]].player().any())
      return amount;

    for (auto pos : snake_body(queue[0]))
      gsnake[pos] = true;

    while (queue.size()) {
      for (auto pos : queue) {
        for (int i = 0; i < 4; i++) {
          Dir dir = Dir(i);
          Pos npos = norm(pos + dir);

          if ((*this)[pos].connections()[dir.i])
            continue;
          if (seen[npos])
            continue;
          if (!((*this)[npos].is_safe() ||
                (gsnake[pos] &&
                 (*this)[npos].connections() == Cell::body(dir + 1, dir - 1).connections())))
            continue;

          if ((*this)[npos].is_safe())
            amount++;

          queue_next.push_back(npos);
          seen[npos] = true;
        }
      }

      queue = queue_next;
      queue_next = {};
    }

    return amount;
  }

  Pos closest_apple(Pos base)
  {
    Pos apple = base;
    unsigned int dist = -1;

    for (auto [pos, cell] : *this) {
      pos = norm(pos, base);
      unsigned int ndist = abs(pos.x - base.x) + abs(pos.y - base.y);

      if (cell.is_apple() && ndist < dist) {
        apple = pos;
        dist = ndist;
      }
    }

    return apple;
  }

  template<class F> void closest_dirs(Pos base, Pos target, F on_dir)
  {
    for (int i = 0; i < 4; i++) {
      Pos off{target.x - base.x, target.y - base.y};
      off.x = off.x > 0 ? 1 : off.x < 0 ? -1 : 0;
      off.y = off.y > 0 ? 1 : off.y < 0 ? -1 : 0;

      Pos doff = Pos() + Dir(i);

      if (off.x && doff.x == off.x || off.y && doff.y == off.y) {
        on_dir(Dir(i));
      }
    }
  }

  template<class T> void rand_moves(T &moves)
  {
    for (int pi = moves.size(); pi < player_count(); pi++) {
      Move move = {rand() % 4, (bool)(rand() % 2)};
      moves.push_back(move);
    }
  }

  int player_count()
  {
    return players.size();
  }

  template<class Moves> int move(Moves &moves)
  {
    std::vector<bool> alive;
    alive.resize(players.size(), true);

    for (int i = 0; i < players.size(); i++) {
      auto body = snake_body(players[i].pos);

      if (moves[i].dir == body[1] - body[0]) {
        moves[i].dir = body[0] - body[1];
      }

      if (body.size() <= 5)
        moves[i].fast = false;

      if (moves[i].fast)
        players[i].debt++;
    }

    int body_size = 0;

    for (int mi = 0; mi < 2; mi++) {
      init_snake_density();

      struct MStateExtra {
        MoveState ms;
        int stage = 0;

        MStateExtra(Game &game) : ms(game) {}
      };

      std::vector<std::optional<MStateExtra>> mstates;
      mstates.resize(players.size(), {});
      int count = 0;

      for (int i = 0; i < players.size(); i++) {
        if ((!alive[i]) || (!(mi || moves[i].fast)))
          continue;

        auto &mstate = mstates[i].emplace(*this);
        mstate.ms.pos = players[i].pos;
        mstate.ms.debt = players[i].debt;
        mstate.ms.body = snake_body(players[i].pos);
        mstate.ms.dir = moves[i].dir;
        mstate.ms.fast = moves[i].fast;

        count++;
      }

      while (count) {
        for (int i = 0; i < mstates.size(); i++) {
          if (!mstates[i])
            continue;

          auto &state = *mstates[i];

          int result = move_single(state.ms, state.stage);

          if (result == MRESULT_CONT) {
            state.stage++;
          }
          else {
            if (result == MRESULT_DEAD) {
              kill(state.ms.pos);
              alive[i] = false;
            }

            if (result == MRESULT_DEAD && i == 0)
              return 0;

            if (i == 0)
              body_size = state.ms.body.size();

            players[i].pos = state.ms.body[0];
            players[i].debt = state.ms.debt;

            count--;
            mstates[i] = {};
          }
        }
      }
    }

    {
      int i = 0;
      int removed = 0;

      players.erase(std::remove_if(players.begin(),
                                   players.end(),
                                   [&](const Player &pl) { return !alive[i++]; }),
                    players.end());
    }

    return body_size * 2 - players[0].debt;
  }

  int move_io(Move move)
  {
    printf("%c", move.fast ? move.dir.to_cmd_fast() : move.dir.to_cmd());

    Grid<Cell> next_state(width(), height());
    if (!next_state.copy_io())
      return 0;

    std::vector<bool> alive;
    alive.resize(players.size(), true);

    int err = 0;

    for (auto [it, i] = std::pair{players.begin(), (int)0}; it != players.end(); it++, i++) {
      auto player = *it;

      if (next_state[player.pos].is_safe()) {
        alive[i] = false;
        continue;
      }

      MoveState mstate(*this);
      mstate.pos = player.pos;
      mstate.debt = player.debt;
      mstate.body = snake_body(player.pos);
      mstate.dir = next_state[player.pos].walkdir(mstate.body[0] - mstate.body[1]);

      Pos nextpos = player.pos;

      while (next_state[nextpos].is_connected(mstate.dir)) {
        nextpos = nextpos + mstate.dir;
      }

      Game snap = *this;

      do {
        do {
          if ((err = move_single(mstate, MSTAGE_FUME) != MRESULT_CONT))
            break;
          if ((err = move_single(mstate, MSTAGE_MOVE) != MRESULT_CONT))
            break;
        } while (0);

        if (mstate.body[0] == nextpos && !err) {
          break;
        }

        err = 0;

        Dir dir = mstate.dir;
        mstate = {*this};
        mstate.pos = player.pos;
        mstate.debt = player.debt + 1;
        mstate.body = snake_body(player.pos);
        mstate.dir = dir;

        Grid<bool> is_snake(width(), height());

        for (Pos pos : mstate.body) {
          is_snake[pos] = true;
        }

        for (auto [pos, cell] : *this) {
          if (!(cell.is_safe() || is_snake[pos]))
            (*this)[pos] = Cell::space();
        }

        do {
          init_snake_density();

          if ((err = move_single(mstate, MSTAGE_FUME) != MRESULT_CONT))
            break;
          if ((err = move_single(mstate, MSTAGE_FAPL) != MRESULT_CONT))
            break;
          if ((err = move_single(mstate, MSTAGE_MOVE) != MRESULT_CONT))
            break;
          if ((err = move_single(mstate, MSTAGE_FIN) == MRESULT_DEAD))
            break;

          mstate.pos = mstate.body[0];

          if ((err = move_single(mstate, MSTAGE_FUME) != MRESULT_CONT))
            break;
          if ((err = move_single(mstate, MSTAGE_MOVE) != MRESULT_CONT))
            break;
        } while (0);

        if (err) {
          break;
        }

        if ((err = mstate.body[0] != nextpos))
          break;
      } while (0);

      if (err) {
        std::string info;
        Grid<Cell> gsnake(width(), height());

        for (auto pos : mstate.body) {
          gsnake[pos] = mstate.tmp[pos] ? mstate.tmp[pos] : (*this)[pos];
        }

        for (int y = 0; y < height(); y++) {
          for (int x = 0; x < width(); x++) {
            char buf[16];

            sprintf(buf, "%lc", (char16_t)(gsnake[Pos(x, y)] ? gsnake[Pos(x, y)] : Cell::space()));

            info += buf;
          }

          info += "\n";
        }

        fprintf(stderr,
                "worm.cpp: STATE DESYNC at snake (%i,%i) -> (%i,%i) {\n%s}\n",
                player.pos.x,
                player.pos.y,
                nextpos.x,
                nextpos.y,
                info.data());
        copy_from(next_state);
        validate();
        init_state();

        return 1;
      }

      *this = snap;

      players[i].debt = mstate.debt;
      players[i].pos = norm(nextpos);
    }

    {
      int i = 0;

      players.erase(std::remove_if(players.begin(),
                                   players.end(),
                                   [&](const Player &pl) { return !alive[i++]; }),
                    players.end());
    }

    copy_from(next_state);
    validate();

    return alive[0] ? 1 : 0;
  }
};

int main()
{
  setlocale(LC_ALL, "");
  char buf[65536];
  Game game = Game::from_io();
  while (1) {
    struct MoveInfo {
      Move move;
      double score;
      double total;
    };

    std::vector<MoveInfo> moves;

    for (int i = 0; i < 8; i++) {
      MoveInfo move;
      move.move.dir = {i % 4};
      move.move.fast = i / 4;
      move.score = 0;
      move.total = 0;

      moves.push_back(move);
    }

    Game vgame = game;
    Game vgame2 = game;

    Pos pos = game.player_pos();
    Pos apple = game.closest_apple(pos);
    int cur_length = game.player_length();

    std::bitset<4> adirs{0};
    game.closest_dirs(pos, apple, [&](Dir dir) { adirs[dir.i] = true; });

    for (auto &move : moves) {
      int max_fullh = 5;
      int max_onlyf = 25;

      for (int i = 0; i < max_onlyf; i++) {
        vgame = game;

        int mcount = 0;
        int max_mc = 5;
        double exp = 64.0;
        double extent;
        int res;

        {
          std::vector<Move> vmoves;

          vmoves.push_back(move.move);

          for (int pi = 0; pi < vgame.player_count() - 1; pi++)
            vmoves.push_back({rand() % 4, (bool)(rand() % 2)});

          res = vgame.move(vmoves);

          if (!(res)) {
            move.score = 0;
            move.total = 1;
            break;
          }
        }

        for (int mi = 0; i < max_fullh && mi < max_mc && res; mi++) {
          std::vector<Move> vmoves;

          vgame.rand_moves(vmoves);

          int nres;

          for (int mj = 0; mj < 8; mj++,
                   vmoves[0].dir = vmoves[0].dir + 1,
                   vmoves[0].fast = vmoves[0].dir.i ? vmoves[0].fast : !vmoves[0].fast)
          {
            vgame2 = vgame;

            nres = vgame2.move(vmoves);

            if (nres) {
              vgame = vgame2;
              break;
            }
          }

          mcount++;
          res = nres;
        }

        extent = vgame.avail_space();

        move.score += (move.move.fast ? std::min(cur_length, res) : res) * extent;
        move.total += 1.0;
      }

      if (adirs[move.move.dir.i])
        move.total *= 0.8;
    }

    auto move = *std::max_element(moves.begin(), moves.end(), [&](const auto &a, const auto &b) {
      return a.score / a.total < b.score / b.total;
    });

    if (!game.move_io(move.move)) {
      fprintf(stderr, "i am dead.\n");
      return 0;
    }
  }
}