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

const int MAXN = 1e5;

vector <pair <int, int>> g[MAXN + 5];
bool is_f[MAXN + 5];
bool used[MAXN + 5];

vector <int> dnc(int l, int r, int q) {
    int m = (l + r) / 2;
    if (l == r) {
        return {l};
    }
    int ql = find_portals(l, m);
    int qr = q - ql;
    vector <int> ansl;
    vector <int> ansr;
    if (ql) {
        ansl = dnc(l, m, ql);
    }
    if (qr) {
        ansr = dnc(m + 1, r, qr);
    }
    for (auto x : ansr) {
        ansl.push_back(x);
    }
    return ansl;
}

std::vector<int> portals(int n, int k) {
    return dnc(1, n, k);
}

std::pair<int, int> minimal_danger(int n, std::vector<std::pair<int, std::pair<int, int>>> paths, std::vector<int> p, std::vector<int> f) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        is_f[i] = false;
        used[i] = false;
    }
    for (auto path : paths) {
        int w = path.first, u = path.second.first, v = path.second.second;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    priority_queue <array <ll, 3>, vector <array <ll, 3>>, greater <array <ll, 3>>> pq;
    for (auto x : f) is_f[x] = true;
    for (auto x : p) pq.push({0, x, x});
    while (!pq.empty()) {
        auto [dist, u, st] = pq.top(); pq.pop();
        if (used[u]) continue;
        used[u] = true;
        if (is_f[u]) {
            return {st, u};
        }
        for (auto [v, w] : g[u]) {
            if (used[v]) continue;
            pq.push({dist + w, v, st});
        }
    }
}

std::pair<int, int> find_end_portal(int L) {
    int lx = 1, rx = L, ly = 1, ry = L;
    while (lx < rx || ly < ry) {
        int mx = (lx + rx) / 2;
        int my = (ly + ry) / 2;
        string s = throw_eye({mx, my});
        if (s.find('E') != string::npos) {
            lx = mx + 1;
        }
        else if (s.find('W') != string::npos) {
            rx = mx - 1;
        }
        if (s.find('N') != string::npos) {
            ly = my + 1;
        }
        else if (s.find('S') != string::npos) {
            ry = my + 1;
        }
    }
    return {lx, ly};
}
