#include <iostream>
 
#pragma mark - Tape
 
constexpr int Blank = -1;
 
template<int... xs>
class Tape {
public:
    using type = Tape<xs...>;
    constexpr static int length = sizeof...(xs);
};
 
#pragma mark - Print
 
template<class T>
void print(T);
 
template<>
void print(Tape<>) {
    std::cout << std::endl;
}
 
template<int x, int... xs>
void print(Tape<x, xs...>) {
    if (x == Blank) {
        std::cout << "_ ";
    } else {
        std::cout << x << " ";
    }
    print(Tape<xs...>());
}
 
#pragma mark - Concatenate
 
template<class, class>
class Concatenate;
 
template<int... xs, int... ys>
class Concatenate<Tape<xs...>, Tape<ys...>> {
public:
    using type = Tape<xs..., ys...>;
};
 
#pragma mark - Invert
 
template<class>
class Invert;
 
template<>
class Invert<Tape<>> {
public:
    using type = Tape<>;
};
 
template<int x, int... xs>
class Invert<Tape<x, xs...>> {
public:
    using type = typename Concatenate<
        typename Invert<Tape<xs...>>::type,
        Tape<x>
    >::type;
};
 
#pragma mark - Read
 
template<int, class>
class Read;
 
template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
    using type = typename std::conditional<
        (n == 0),
        std::integral_constant<int, x>,
        Read<n - 1, Tape<xs...>>
    >::type::type;
};
 
#pragma mark - N first and N last
 
template<int, class>
class NLast;
 
template<int n, int x, int... xs>
class NLast<n, Tape<x, xs...>> {
public:
    using type = typename std::conditional<
        (n == sizeof...(xs)),
        Tape<xs...>,
        NLast<n, Tape<xs...>>
    >::type::type;
};
 
template<int, class>
class NFirst;
 
template<int n, int... xs>
class NFirst<n, Tape<xs...>> {
public:
    using type = typename Invert<
        typename NLast<
            n, typename Invert<Tape<xs...>>::type
        >::type
    >::type;
};
 
#pragma mark - Write
 
template<int, int, class>
class Write;
 
template<int pos, int x, int... xs>
class Write<pos, x, Tape<xs...>> {
public:
    using type = typename Concatenate<
        typename Concatenate<
            typename NFirst<pos, Tape<xs...>>::type,
            Tape<x>
        >::type,
        typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type
    >::type;
};
 
#pragma mark - Move
 
template<int, class>
class Hold;
 
template<int pos, int... xs>
class Hold<pos, Tape<xs...>> {
public:
    constexpr static int position = pos;
    using tape = Tape<xs...>;
};
 
template<int, class>
class Left;
 
template<int pos, int... xs>
class Left<pos, Tape<xs...>> {
public:
    constexpr static int position = typename std::conditional<
        (pos > 0),
        std::integral_constant<int, pos - 1>,
        std::integral_constant<int, 0>
    >::type();
 
    using tape = typename std::conditional<
        (pos > 0),
        Tape<xs...>,
        Tape<Blank, xs...>
    >::type;
};
 
template<int, class>
class Right;
 
template<int pos, int... xs>
class Right<pos, Tape<xs...>> {
public:
    constexpr static int position = pos + 1;
 
    using tape = typename std::conditional<
        (pos < sizeof...(xs) - 1),
        Tape<xs...>,
        Tape<xs..., Blank>
    >::type;
};
 
#pragma mark - States
 
template <int>
class Stop {
public:
    constexpr static int write = -1;
    template<int pos, class tape> using move = Hold<pos, tape>;
    template<int x> using next = Stop<x>;
};
 
#define ADD_STATE(_state_)      \
template<int>                   \
class _state_ { };
 
#define ADD_RULE(_state_, _read_, _write_, _move_, _next_)          \
template<>                                                          \
class _state_<_read_> {                                             \
public:                                                             \
    constexpr static int write = _write_;                           \
    template<int pos, class tape> using move = _move_<pos, tape>;   \
    template<int x> using next = _next_<x>;                         \
};
 
#pragma mark - Machine
 
template<template<int> class, int, class>
class Machine;
 
template<template<int> class State, int pos, int... xs>
class Machine<State, pos, Tape<xs...>> {
    constexpr static int symbol = typename Read<pos, Tape<xs...>>::type();
    using state = State<symbol>;
 
    template<int x>
    using nextState = typename State<symbol>::template next<x>;
 
    using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type;
    using move = typename state::template move<pos, modifiedTape>;
 
    constexpr static int nextPos = move::position;
    using nextTape = typename move::tape;
 
public:
    using step = Machine<nextState, nextPos, nextTape>;
};
 
#pragma mark - Run
 
template<class>
class Run;
 
template<template<int> class State, int pos, int... xs>
class Run<Machine<State, pos, Tape<xs...>>> {
    using step = typename Machine<State, pos, Tape<xs...>>::step;
 
public:
    using type = typename std::conditional<
        std::is_same<State<0>, Stop<0>>::value,
        Tape<xs...>,
        Run<step>
    >::type::type;
};
 
ADD_STATE(S0);
ADD_STATE(S1);
ADD_STATE(S2);
 
ADD_RULE(S0, Blank, Blank, Left, S1);
ADD_RULE(S0, 0, 0, Right, S0);
ADD_RULE(S0, 1, 1, Right, S0);
 
ADD_RULE(S1, Blank, 1, Right, S2);
ADD_RULE(S1, 0, 1, Left, S2);
ADD_RULE(S1, 1, 0, Left, S1);
 
ADD_RULE(S2, Blank, Blank, Hold, Stop);
ADD_RULE(S2, 0, 0, Right, S2);
ADD_RULE(S2, 1, 1, Right, S2);
 
using tape = Tape<Blank, 1, 1, 0, Blank>;
using result = Run<Machine<S0, tape::length - 1, tape>>::type;
 
int main() {
    print(tape());
    print(result());
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgoKI3ByYWdtYSBtYXJrIC0gVGFwZQoKY29uc3RleHByIGludCBCbGFuayA9IC0xOwoKdGVtcGxhdGU8aW50Li4uIHhzPgpjbGFzcyBUYXBlIHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IFRhcGU8eHMuLi4+OwogICAgY29uc3RleHByIHN0YXRpYyBpbnQgbGVuZ3RoID0gc2l6ZW9mLi4uKHhzKTsKfTsKCiNwcmFnbWEgbWFyayAtIFByaW50Cgp0ZW1wbGF0ZTxjbGFzcyBUPgp2b2lkIHByaW50KFQpOwoKdGVtcGxhdGU8Pgp2b2lkIHByaW50KFRhcGU8PikgewogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKfQoKdGVtcGxhdGU8aW50IHgsIGludC4uLiB4cz4Kdm9pZCBwcmludChUYXBlPHgsIHhzLi4uPikgewogICAgaWYgKHggPT0gQmxhbmspIHsKICAgICAgICBzdGQ6OmNvdXQgPDwgIl8gIjsKICAgIH0gZWxzZSB7CiAgICAgICAgc3RkOjpjb3V0IDw8IHggPDwgIiAiOwogICAgfQogICAgcHJpbnQoVGFwZTx4cy4uLj4oKSk7Cn0KCiNwcmFnbWEgbWFyayAtIENvbmNhdGVuYXRlCgp0ZW1wbGF0ZTxjbGFzcywgY2xhc3M+CmNsYXNzIENvbmNhdGVuYXRlOwoKdGVtcGxhdGU8aW50Li4uIHhzLCBpbnQuLi4geXM+CmNsYXNzIENvbmNhdGVuYXRlPFRhcGU8eHMuLi4+LCBUYXBlPHlzLi4uPj4gewpwdWJsaWM6CiAgICB1c2luZyB0eXBlID0gVGFwZTx4cy4uLiwgeXMuLi4+Owp9OwoKI3ByYWdtYSBtYXJrIC0gSW52ZXJ0Cgp0ZW1wbGF0ZTxjbGFzcz4KY2xhc3MgSW52ZXJ0OwoKdGVtcGxhdGU8PgpjbGFzcyBJbnZlcnQ8VGFwZTw+PiB7CnB1YmxpYzoKICAgIHVzaW5nIHR5cGUgPSBUYXBlPD47Cn07Cgp0ZW1wbGF0ZTxpbnQgeCwgaW50Li4uIHhzPgpjbGFzcyBJbnZlcnQ8VGFwZTx4LCB4cy4uLj4+IHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IHR5cGVuYW1lIENvbmNhdGVuYXRlPAogICAgICAgIHR5cGVuYW1lIEludmVydDxUYXBlPHhzLi4uPj46OnR5cGUsCiAgICAgICAgVGFwZTx4PgogICAgPjo6dHlwZTsKfTsKCiNwcmFnbWEgbWFyayAtIFJlYWQKCnRlbXBsYXRlPGludCwgY2xhc3M+CmNsYXNzIFJlYWQ7Cgp0ZW1wbGF0ZTxpbnQgbiwgaW50IHgsIGludC4uLiB4cz4KY2xhc3MgUmVhZDxuLCBUYXBlPHgsIHhzLi4uPj4gewpwdWJsaWM6CiAgICB1c2luZyB0eXBlID0gdHlwZW5hbWUgc3RkOjpjb25kaXRpb25hbDwKICAgICAgICAobiA9PSAwKSwKICAgICAgICBzdGQ6OmludGVncmFsX2NvbnN0YW50PGludCwgeD4sCiAgICAgICAgUmVhZDxuIC0gMSwgVGFwZTx4cy4uLj4+CiAgICA+Ojp0eXBlOjp0eXBlOwp9OwoKI3ByYWdtYSBtYXJrIC0gTiBmaXJzdCBhbmQgTiBsYXN0Cgp0ZW1wbGF0ZTxpbnQsIGNsYXNzPgpjbGFzcyBOTGFzdDsKCnRlbXBsYXRlPGludCBuLCBpbnQgeCwgaW50Li4uIHhzPgpjbGFzcyBOTGFzdDxuLCBUYXBlPHgsIHhzLi4uPj4gewpwdWJsaWM6CiAgICB1c2luZyB0eXBlID0gdHlwZW5hbWUgc3RkOjpjb25kaXRpb25hbDwKICAgICAgICAobiA9PSBzaXplb2YuLi4oeHMpKSwKICAgICAgICBUYXBlPHhzLi4uPiwKICAgICAgICBOTGFzdDxuLCBUYXBlPHhzLi4uPj4KICAgID46OnR5cGU6OnR5cGU7Cn07Cgp0ZW1wbGF0ZTxpbnQsIGNsYXNzPgpjbGFzcyBORmlyc3Q7Cgp0ZW1wbGF0ZTxpbnQgbiwgaW50Li4uIHhzPgpjbGFzcyBORmlyc3Q8biwgVGFwZTx4cy4uLj4+IHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IHR5cGVuYW1lIEludmVydDwKICAgICAgICB0eXBlbmFtZSBOTGFzdDwKICAgICAgICAgICAgbiwgdHlwZW5hbWUgSW52ZXJ0PFRhcGU8eHMuLi4+Pjo6dHlwZQogICAgICAgID46OnR5cGUKICAgID46OnR5cGU7Cn07CgojcHJhZ21hIG1hcmsgLSBXcml0ZQoKdGVtcGxhdGU8aW50LCBpbnQsIGNsYXNzPgpjbGFzcyBXcml0ZTsKCnRlbXBsYXRlPGludCBwb3MsIGludCB4LCBpbnQuLi4geHM+CmNsYXNzIFdyaXRlPHBvcywgeCwgVGFwZTx4cy4uLj4+IHsKcHVibGljOgogICAgdXNpbmcgdHlwZSA9IHR5cGVuYW1lIENvbmNhdGVuYXRlPAogICAgICAgIHR5cGVuYW1lIENvbmNhdGVuYXRlPAogICAgICAgICAgICB0eXBlbmFtZSBORmlyc3Q8cG9zLCBUYXBlPHhzLi4uPj46OnR5cGUsCiAgICAgICAgICAgIFRhcGU8eD4KICAgICAgICA+Ojp0eXBlLAogICAgICAgIHR5cGVuYW1lIE5MYXN0PChzaXplb2YuLi4oeHMpIC0gcG9zIC0gMSksIFRhcGU8eHMuLi4+Pjo6dHlwZQogICAgPjo6dHlwZTsKfTsKCiNwcmFnbWEgbWFyayAtIE1vdmUKCnRlbXBsYXRlPGludCwgY2xhc3M+CmNsYXNzIEhvbGQ7Cgp0ZW1wbGF0ZTxpbnQgcG9zLCBpbnQuLi4geHM+CmNsYXNzIEhvbGQ8cG9zLCBUYXBlPHhzLi4uPj4gewpwdWJsaWM6CiAgICBjb25zdGV4cHIgc3RhdGljIGludCBwb3NpdGlvbiA9IHBvczsKICAgIHVzaW5nIHRhcGUgPSBUYXBlPHhzLi4uPjsKfTsKCnRlbXBsYXRlPGludCwgY2xhc3M+CmNsYXNzIExlZnQ7Cgp0ZW1wbGF0ZTxpbnQgcG9zLCBpbnQuLi4geHM+CmNsYXNzIExlZnQ8cG9zLCBUYXBlPHhzLi4uPj4gewpwdWJsaWM6CiAgICBjb25zdGV4cHIgc3RhdGljIGludCBwb3NpdGlvbiA9IHR5cGVuYW1lIHN0ZDo6Y29uZGl0aW9uYWw8CiAgICAgICAgKHBvcyA+IDApLAogICAgICAgIHN0ZDo6aW50ZWdyYWxfY29uc3RhbnQ8aW50LCBwb3MgLSAxPiwKICAgICAgICBzdGQ6OmludGVncmFsX2NvbnN0YW50PGludCwgMD4KICAgID46OnR5cGUoKTsKCiAgICB1c2luZyB0YXBlID0gdHlwZW5hbWUgc3RkOjpjb25kaXRpb25hbDwKICAgICAgICAocG9zID4gMCksCiAgICAgICAgVGFwZTx4cy4uLj4sCiAgICAgICAgVGFwZTxCbGFuaywgeHMuLi4+CiAgICA+Ojp0eXBlOwp9OwoKdGVtcGxhdGU8aW50LCBjbGFzcz4KY2xhc3MgUmlnaHQ7Cgp0ZW1wbGF0ZTxpbnQgcG9zLCBpbnQuLi4geHM+CmNsYXNzIFJpZ2h0PHBvcywgVGFwZTx4cy4uLj4+IHsKcHVibGljOgogICAgY29uc3RleHByIHN0YXRpYyBpbnQgcG9zaXRpb24gPSBwb3MgKyAxOwoKICAgIHVzaW5nIHRhcGUgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsPAogICAgICAgIChwb3MgPCBzaXplb2YuLi4oeHMpIC0gMSksCiAgICAgICAgVGFwZTx4cy4uLj4sCiAgICAgICAgVGFwZTx4cy4uLiwgQmxhbms+CiAgICA+Ojp0eXBlOwp9OwoKI3ByYWdtYSBtYXJrIC0gU3RhdGVzCgp0ZW1wbGF0ZSA8aW50PgpjbGFzcyBTdG9wIHsKcHVibGljOgogICAgY29uc3RleHByIHN0YXRpYyBpbnQgd3JpdGUgPSAtMTsKICAgIHRlbXBsYXRlPGludCBwb3MsIGNsYXNzIHRhcGU+IHVzaW5nIG1vdmUgPSBIb2xkPHBvcywgdGFwZT47CiAgICB0ZW1wbGF0ZTxpbnQgeD4gdXNpbmcgbmV4dCA9IFN0b3A8eD47Cn07CgojZGVmaW5lIEFERF9TVEFURShfc3RhdGVfKSAgICAgIFwKdGVtcGxhdGU8aW50PiAgICAgICAgICAgICAgICAgICBcCmNsYXNzIF9zdGF0ZV8geyB9OwoKI2RlZmluZSBBRERfUlVMRShfc3RhdGVfLCBfcmVhZF8sIF93cml0ZV8sIF9tb3ZlXywgX25leHRfKSAgICAgICAgICBcCnRlbXBsYXRlPD4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgXApjbGFzcyBfc3RhdGVfPF9yZWFkXz4geyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFwKcHVibGljOiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBcCiAgICBjb25zdGV4cHIgc3RhdGljIGludCB3cml0ZSA9IF93cml0ZV87ICAgICAgICAgICAgICAgICAgICAgICAgICAgXAogICAgdGVtcGxhdGU8aW50IHBvcywgY2xhc3MgdGFwZT4gdXNpbmcgbW92ZSA9IF9tb3ZlXzxwb3MsIHRhcGU+OyAgIFwKICAgIHRlbXBsYXRlPGludCB4PiB1c2luZyBuZXh0ID0gX25leHRfPHg+OyAgICAgICAgICAgICAgICAgICAgICAgICBcCn07CgojcHJhZ21hIG1hcmsgLSBNYWNoaW5lCgp0ZW1wbGF0ZTx0ZW1wbGF0ZTxpbnQ+IGNsYXNzLCBpbnQsIGNsYXNzPgpjbGFzcyBNYWNoaW5lOwoKdGVtcGxhdGU8dGVtcGxhdGU8aW50PiBjbGFzcyBTdGF0ZSwgaW50IHBvcywgaW50Li4uIHhzPgpjbGFzcyBNYWNoaW5lPFN0YXRlLCBwb3MsIFRhcGU8eHMuLi4+PiB7CiAgICBjb25zdGV4cHIgc3RhdGljIGludCBzeW1ib2wgPSB0eXBlbmFtZSBSZWFkPHBvcywgVGFwZTx4cy4uLj4+Ojp0eXBlKCk7CiAgICB1c2luZyBzdGF0ZSA9IFN0YXRlPHN5bWJvbD47CgogICAgdGVtcGxhdGU8aW50IHg+CiAgICB1c2luZyBuZXh0U3RhdGUgPSB0eXBlbmFtZSBTdGF0ZTxzeW1ib2w+Ojp0ZW1wbGF0ZSBuZXh0PHg+OwoKICAgIHVzaW5nIG1vZGlmaWVkVGFwZSA9IHR5cGVuYW1lIFdyaXRlPHBvcywgc3RhdGU6OndyaXRlLCBUYXBlPHhzLi4uPj46OnR5cGU7CiAgICB1c2luZyBtb3ZlID0gdHlwZW5hbWUgc3RhdGU6OnRlbXBsYXRlIG1vdmU8cG9zLCBtb2RpZmllZFRhcGU+OwoKICAgIGNvbnN0ZXhwciBzdGF0aWMgaW50IG5leHRQb3MgPSBtb3ZlOjpwb3NpdGlvbjsKICAgIHVzaW5nIG5leHRUYXBlID0gdHlwZW5hbWUgbW92ZTo6dGFwZTsKCnB1YmxpYzoKICAgIHVzaW5nIHN0ZXAgPSBNYWNoaW5lPG5leHRTdGF0ZSwgbmV4dFBvcywgbmV4dFRhcGU+Owp9OwoKI3ByYWdtYSBtYXJrIC0gUnVuCgp0ZW1wbGF0ZTxjbGFzcz4KY2xhc3MgUnVuOwoKdGVtcGxhdGU8dGVtcGxhdGU8aW50PiBjbGFzcyBTdGF0ZSwgaW50IHBvcywgaW50Li4uIHhzPgpjbGFzcyBSdW48TWFjaGluZTxTdGF0ZSwgcG9zLCBUYXBlPHhzLi4uPj4+IHsKICAgIHVzaW5nIHN0ZXAgPSB0eXBlbmFtZSBNYWNoaW5lPFN0YXRlLCBwb3MsIFRhcGU8eHMuLi4+Pjo6c3RlcDsKCnB1YmxpYzoKICAgIHVzaW5nIHR5cGUgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsPAogICAgICAgIHN0ZDo6aXNfc2FtZTxTdGF0ZTwwPiwgU3RvcDwwPj46OnZhbHVlLAogICAgICAgIFRhcGU8eHMuLi4+LAogICAgICAgIFJ1bjxzdGVwPgogICAgPjo6dHlwZTo6dHlwZTsKfTsKCkFERF9TVEFURShTMCk7CkFERF9TVEFURShTMSk7CkFERF9TVEFURShTMik7CgpBRERfUlVMRShTMCwgQmxhbmssIEJsYW5rLCBMZWZ0LCBTMSk7CkFERF9SVUxFKFMwLCAwLCAwLCBSaWdodCwgUzApOwpBRERfUlVMRShTMCwgMSwgMSwgUmlnaHQsIFMwKTsKCkFERF9SVUxFKFMxLCBCbGFuaywgMSwgUmlnaHQsIFMyKTsKQUREX1JVTEUoUzEsIDAsIDEsIExlZnQsIFMyKTsKQUREX1JVTEUoUzEsIDEsIDAsIExlZnQsIFMxKTsKCkFERF9SVUxFKFMyLCBCbGFuaywgQmxhbmssIEhvbGQsIFN0b3ApOwpBRERfUlVMRShTMiwgMCwgMCwgUmlnaHQsIFMyKTsKQUREX1JVTEUoUzIsIDEsIDEsIFJpZ2h0LCBTMik7Cgp1c2luZyB0YXBlID0gVGFwZTxCbGFuaywgMSwgMSwgMCwgQmxhbms+Owp1c2luZyByZXN1bHQgPSBSdW48TWFjaGluZTxTMCwgdGFwZTo6bGVuZ3RoIC0gMSwgdGFwZT4+Ojp0eXBlOwoKaW50IG1haW4oKSB7CiAgICBwcmludCh0YXBlKCkpOwogICAgcHJpbnQocmVzdWx0KCkpOwogICAgcmV0dXJuIDA7Cn0K