#include "navigacio.h"

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int LE = 0;
const int BAL = 1;
const int JOBB = 2;
const int BFEL = 3;
const int JFEL = 4;

void navigate(vector<bool> layout) {
    int asked = 0;
    auto go_root = [&]() {
        while (layout[LE]) layout = move(LE);
    };

    go_root();
    
    vector<vector<pair<int, int>>> g(16);
    vector<bool> exists(16);
    vector<int> offset = {1, 2, 4, 8};
    auto build = [&](auto &&self, int idx, int depth) -> int {
        int v = offset[depth] + idx;
        exists[v] = 1;
        if (layout[JOBB]) {
            g[v].emplace_back(v+1, 0);
        }
        if (layout[BAL]) {
            g[v].emplace_back(v-1, 0);
        }
        if (depth != 3) {
            bool bal = layout[BFEL];
            bool jobb = layout[JFEL];

            if (bal) {
                layout = move(BFEL);
                int nv = self(self, 2*idx, depth+1);
                g[v].emplace_back(nv, 1);
                g[nv].emplace_back(v, 1);
                layout = move(LE);
            }
            if (jobb) {
                layout = move(JFEL);
                int nv = self(self, 2*idx+1, depth+1);
                g[v].emplace_back(nv, 1);
                g[nv].emplace_back(v, 1);
                layout = move(LE);
            }
        }
        return v;
    };

    build(build, 0, 0);

    auto calc_dist = [&](int source) {
        vector<int> dist(16, INF);
        dist[source] = 0;
        deque<int> q;
        q.push_back(source);
        while (!q.empty()) {
            int u = q.front();
            q.pop_front();
            for (auto [v, w] : g[u]) {
                if (dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] + 1;
                    if (w) q.push_back(v);
                    else q.push_front(v);
                }
            }
        }
        return dist;
    };

    auto smart_query = [&](auto &&self, int idx, int depth, int need, int &res) -> void {
        int v = offset[depth] + idx;
        if (v == need) {
            res = query();
            asked++;
        }
        if (depth != 3) {
            bool bal = layout[BFEL];
            bool jobb = layout[JFEL];

            if (bal) {
                layout = move(BFEL);
                self(self, 2*idx, depth+1, need, res);
                layout = move(LE);
            }
            if (jobb) {
                layout = move(JFEL);
                self(self, 2*idx+1, depth+1, need, res);
                layout = move(LE);
            }
        }
    };

    auto walk = [&](auto &&self, int idx, int depth, int need, int &found) -> void {
        int v = offset[depth] + idx;
        if (v == need) {
            found = 1;
            return;
        }
        if (depth != 3) {
            bool bal = layout[BFEL];
            bool jobb = layout[JFEL];

            if (bal) {
                layout = move(BFEL);
                self(self, 2*idx, depth+1, need, found);
                if (found) return;
                layout = move(LE);
            }
            if (jobb) {
                layout = move(JFEL);
                self(self, 2*idx+1, depth+1, need, found);
                if (found) return;
                layout = move(LE);
            }
        }
    };

    bool extra = false;
    int ml = -1, mr = -1;
    for (int i = 8; i <= 15; i++) {
        if (!exists[i]) continue;
        for (int j = i; j <= 15; j++) {
            if (!exists[j]) continue;
            auto d1 = calc_dist(i);
            auto d2 = calc_dist(j);
            set<pair<int, int>> vals;
            bool ok = true;
            for (int k = 8; k <= 15; k++) {
                if (!exists[k]) continue;
                if (vals.count({d1[k], d2[k]})) ok = false;
                vals.insert({d1[k], d2[k]});
            }
            if (ok) {
                ml = i;
                mr = j;
                break;
            }
        }
    }

    int m;
    bool fallback = false;
    if (ml != -1) {
        auto d1 = calc_dist(ml);
        auto d2 = calc_dist(mr);
        int x, y;
        smart_query(smart_query, 0, 0, ml, x);
        smart_query(smart_query, 0, 0, mr, y);
        if ((x <= 20 || y <= 20)) {
            fallback = true;
        } else {
            int cnt = 0, nxt = 0;
            for (int i = 8; i <= 15; i++) {
                if (!exists[i]) continue;
                int m1 = x - d1[i];
                int m2 = y - d2[i];
                if (m1 == m2) {
                    nxt = i;
                    cnt++;
                    m = m1;
                }
            }
            assert(cnt == 1);
            int found = 0;
            walk(walk, 0, 0, nxt, found);
        }
    } else {
        fallback = true;
    }

    if (fallback) m = query();

    while (true) {
        if (m == 0) return;
        bool bal = layout[BFEL];
        bool jobb = layout[JFEL];
        if (bal && !jobb) {
            layout = move(BFEL);
            m--;
        } else if (!bal && jobb) {
            layout = move(JFEL);
            m--;
        } else {
            if (m == 1) {
                layout = move(BFEL);
                asked++;
                if (query() != 0) move(JOBB);
                return;
            }
            vector<bool> lb = move(BFEL);
            vector<bool> lj = move(JOBB);
            int c1 = 0;
            c1 += lb[BFEL];
            c1 += lb[JFEL];
            int c2 = 0;
            c2 += lj[BFEL];
            c2 += lj[JFEL];
            if (c1 <= 1 && c2 <= 1) {
                int x = query();
                asked++;
                if (x == m-1) {
                    if (lj[BFEL]) layout = move(BFEL);
                    else layout = move(JFEL);
                } else {
                    layout = move(BAL);
                    if (lb[BFEL]) layout = move(BFEL);
                    else layout = move(JFEL);
                }
            } else {
                int D1 = (c2 == 2) ? BAL : JOBB;
                int D2 = (c2 == 2) ? JFEL : BFEL;
                int D3 = (c2 == 2) ? BFEL : JFEL;
                if (c2 == 1) layout = move(BAL);
                layout = move(D2);
                int x = query();
                asked++;
                int y = m-2;
                assert(x-y >= 0 && x-y <= 3);
                int z = x-y;
                if (z == 0) {

                } else if (z == 1) {
                    layout = move(D1);
                } else if (z == 2) {
                    layout = move(D1);
                    layout = move(D1);
                } else {
                    layout = move(LE);
                    layout = move(D1);
                    layout = move(D3);
                }
            }
            m -= 2;
        }
    }
}