#include <bits/stdc++.h>
#include "minecraft.h"
using namespace std;

vector <int> v;

void f(int l=0, int r=0, int k=0) {
    if (l+k==r) {
        for (int i=l;i<r;i+=1) v.push_back(i);
        return;
    }
    int m=(l+r)/2;
    int k1=find_portals(l, m-1);
    if (k1) f(l, m, k1);
    if (k-k1) f(m, r, k-k1);
}

vector<int> portals(int n, int k) {
    f(1,  n+1, k);
    return v;
}


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) {
    bool m[n+1]{};
    bool used[n+1]{};
    for (int e:fortresses) m[e]=1;
    vector <pair <int, int>> g[n+1];
    for (pair<int, pair<int, int>> e:paths) {
        g[e.second.first].push_back({e.second.second, e.first});
        g[e.second.second].push_back({e.second.first, e.first});
    }
    priority_queue <pair <int, pair <int, int>>, vector <pair <int, pair <int, int>>>, greater <pair <int, pair <int, int>>>> q;
    for (int e:portals) q.push({0, {e, e}});
    while (!q.empty()) {
        pair <int, pair <int, int>> p=q.top();
        q.pop();
        if (used[p.second.second]==0) {
            used[p.second.second]=1;
            if (m[p.second.second]) {
                return p.second;
            }
            for (pair <int, int> e:g[p.second.second]) {
                if (used[e.first]==0) {
                    q.push({p.first+e.second, {p.second.first, e.first}});
                }
            }
        }
    }
    return make_pair(0, 0);
}

std::pair<int, int> find_end_portal(int l) {
    int ri=1, li=l+1, rj=1, lj=l+1;
    map <string, pair <bool, bool>> m {
        {"NW", {0, 0}},
        {"N", {0, 2}},
        {"NE", {0, 1}},
        {"SW", {1, 0}},
        {"S", {1, 2}},
        {"SE", {1, 1}},
        {"W", {2, 0}},
        {"E", {2, 1}},
        {"NONE", {2, 2}}
    };
    while (li+1<ri||lj+1<rj) {
        pair <bool, bool> p=m[throw_eye({(li+ri)/2, (lj+rj)/2})];
        if (p.first==1) ri=(li+ri)/2;
        if (p.first==2) ri=(li+ri)/2, li=(li+ri)/2+1;
        if (p.first==0) li=(li+ri)/2;
        if (p.second==1) rj=(lj+rj)/2;
        if (p.second==2) rj=(lj+rj)/2, lj=(lj+rj)/2+1;
        if (p.second==0) lj=(lj+rj)/2;
    }
    return {ri, rj};
}