#include "minecraft.h"
#include <vector>
#include <cmath>
#define all(a) a.begin(), a.end()
using namespace std;
vector<int> portals(int l, int r, int K)
{
    // cerr << l << " " << r << " " << K << "\n";
    if (l == r && K == 1)
        return {l};
    if (l == r - 1)
    {
        if (K == 2)
            return {l, l + 1};
        if (find_portals(l, l))
            return {l};
        return {r};
    }
    vector<int> ans;
    int last = l;
    for (int i = log2(r - l - 1); i >= 0 && K > 0 && last + (1 << i) <= r; --i)
    {
        int ch = find_portals(last, last + (1 << i));
        // cerr << last + (1 << i) << " " << ch << "\n";
        if (ch > 0)
        {
            auto ports = portals(last, last + (1 << i), ch);
            ans.insert(ans.begin(), all(ports));
        }
        last = last + (1 << i) + 1;
        K -= ch;
    }
    int ch = K;
    if (K > 0)
    {
        auto ports = portals(last, r, ch);
        ans.insert(ans.begin(), all(ports));
    }
    return ans;
}
std::vector<int> portals(int N, int K)
{
    return portals(1, N, K);
}

std::pair<int, int> minimal_danger(int N, std::vector<std::pair<int, std::pair<int, int>>> paths, std::vector<int> portals, std::vector<int> fortresses)
{
    return {0, 0};
}

std::pair<int, int> find_end_portal(int L)
{
    return {1, 1};
}