#include <vector>

using namespace std;

class Direction {
public:
    int value;
    Direction() = default;
    Direction(int _value) {
        value = _value % 4;
        if (value < 0) value += 4;
    }

    Direction next() {return value + 1;}
    Direction prev() {return value - 1;}

    bool operator==(const Direction& d) const {return d.value == value;}
    bool operator!=(const Direction& d) const {return !(d == *this);}
};

class Cell {
    int x, y;
public:
    Cell() = default;
    Cell(int _x, int _y) :
        x(_x), y(_y) {}

    Cell move(Direction dir) {
        if (dir.value == 0) x++;
        if (dir.value == 1) y++;
        if (dir.value == 2) x--;
        if (dir.value == 3) y--;
    }

    bool operator==(Cell a) {return a.x == x && a.y == y;}

    bool in(Cell& a, Cell& b) const {
        if (a == *this || b == *this) return true;
        if (a.x == b.x)
            if ((a.y - y) != (b.y - y)) return true;
        if (a.y == b.y)
            if ((a.x - x) != (b.x - x)) return true;

        return false;
    }

    Direction directionTo(Cell c) {
        if (!isLine(*this, c)) return 0;
        if (x == c.x)
            if (c.x > x) return 0;
            else return 2;
        else
            if (c.y > y) return 1;
            else return 3;
    }

    static bool isLine(Cell a, Cell b) {
        return a.x == b.x || a.y == b.y;
    }

    static bool orderedIntersect(Cell a, Cell b, Cell c, Cell d) {
        return min(a.x, b.x) <= min(c.x, d.x) &&
               max(a.x, b.x) >= max(c.x, d.x) &&
               min(a.y, b.y) >= min(c.y, d.y) &&
               max(a.y, b.y) <= max(c.y, d.y);
    }

    static bool intersect(Cell a, Cell b, Cell c, Cell d) {
        if (!isLine(a, b) || !isLine(c, d)) return false;
        if (orderedIntersect(a, b, c, d)) return true;
        if (orderedIntersect(c, d, a, b)) return true;
        return false;
    }
};

class Snake {
    vector<Cell> pos;
    Direction last;
    Direction head;
    bool alive;

    Snake():
        last(1), head(1) {
        pos.emplace_back(0, 0);
        alive = true;
    }

    Snake(vector<Cell> _pos) {
        alive = true;

        if (_pos.size() == 0) {
            death();
            return;
        }
        for (int i = 0; i < _pos.size() - 1; i++)
            for (int j = 0; j < i - 1; j++)
                if (Cell::intersect(pos[i], pos[i + 1], pos[j], pos[j + 1])) {
                    death();
                    return;
                }

        pos.push_back(_pos.front());
        last = Direction(1);

        for (auto& c : _pos) {
            if (!Cell::isLine(c, pos.back())) {
                death();
                return;
            }
            if (pos.size() >= 2 && pos.back().in(c, pos[pos.size() - 2])) pos.pop_back();
            pos.push_back(c);
        }

        last = pos[pos.size() - 2].directionTo(pos.back());
        head = last;
    }

    void move() {
        if (!isAlive()) return;
        if (last != head) {
            pos.push_back(pos.back());
            last = head;
        }
        Cell b = pos.back();
        b.move(head);

        if (into(b)) death();
        else pos.push_back(b);
    }

    bool into(const Cell& c) {
        if (!isAlive()) return false;

        for (int i = 0; i < pos.size() - 1; ++i)
            if (c.in(pos[i], pos[i + 1])) return true;

        return false;
    }

    void death() {
        if (!isAlive()) return;
        pos.clear();
        alive = false;
    }

    void turn_left() {head = last.next();}
    void turn_right() {head = last.prev();}
    void turn_forward() {head = last;}

    bool isAlive() {
        return alive;
    }
};

int main() {

}